Submission #324794
Source Code Expand
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstring> #include <cstdio> using namespace std; //#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) const int INF = 1<<28; typedef pair<int,int> P; struct edge { int to, cap, cost, rev; }; int V; const int MAX_V = 100002; vector<edge> G[MAX_V]; int h[MAX_V]; int dist[MAX_V]; int prevv[MAX_V], preve[MAX_V]; void add_edge(int from, int to, int cap, int cost) { G[from].push_back((edge){to, cap, cost, (int)G[to].size()}); G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1}); } int min_cost_flow(int s, int t, int f) { int res = 0; fill(h, h + V, 0); while (f > 0) { priority_queue<P, vector<P>, greater<P> > que; que.push(P(0, s)); fill(dist, dist + V, INF); dist[s] = 0; while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) { continue; } for (int i = 0; i < G[v].size(); i++) { edge& e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(P(dist[e.to], e.to)); } } } if (dist[t] == INF) { return -1; } for (int v = 0; v < V; v++) h[v] += dist[v]; int d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d * h[t]; for (int v = t; v != s; v = prevv[v]) { edge& e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } int main() { int N, L; while (cin>>N>>L) { // int source = (N*2), sink = (N*2)+1; int source = N, sink = N+1; V = sink+1; // refresh V for (int i = 0; i < MAX_V; i++) G[i].clear(); int bsum = 0; int prv = -1, prv_a = -1; for (int i = 0; i < N; i++) { int a, b, c; cin >> a >> b >> c; add_edge(source, i, b, 0); if (c > 0) { add_edge(i, sink, c, 0); } if (prv != -1) { add_edge(prv, i, INF, (a - prv_a)); add_edge(i, prv, INF, (a - prv_a)); } bsum += b; prv = i; prv_a = a; } add_edge(N-1, 0, INF, min(prv_a, L - prv_a)); add_edge(0, N-1, INF, min(prv_a, L - prv_a)); cout << min_cost_flow(source, sink, bsum) << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - タクシー |
User | brly |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 2872 Byte |
Status | WA |
Exec Time | 2036 ms |
Memory | 23816 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 15 | 0 / 30 | 0 / 55 | ||||||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample-01.txt, subtask0-sample-02.txt |
Subtask1 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Subtask3 | subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample-01.txt | AC | 27 ms | 3112 KB |
subtask0-sample-02.txt | AC | 26 ms | 3232 KB |
subtask1-01.txt | AC | 27 ms | 3116 KB |
subtask1-02.txt | AC | 28 ms | 3104 KB |
subtask1-03.txt | TLE | 2030 ms | 4264 KB |
subtask1-04.txt | TLE | 2031 ms | 4260 KB |
subtask1-05.txt | TLE | 2030 ms | 4268 KB |
subtask1-06.txt | AC | 35 ms | 4004 KB |
subtask1-07.txt | TLE | 2030 ms | 4256 KB |
subtask1-08.txt | TLE | 2031 ms | 4268 KB |
subtask1-09.txt | TLE | 2031 ms | 4136 KB |
subtask1-10.txt | TLE | 2032 ms | 4208 KB |
subtask1-11.txt | TLE | 2030 ms | 4132 KB |
subtask1-12.txt | TLE | 2031 ms | 4252 KB |
subtask1-13.txt | TLE | 2031 ms | 4140 KB |
subtask1-14.txt | TLE | 2034 ms | 4248 KB |
subtask1-15.txt | TLE | 2031 ms | 4264 KB |
subtask1-16.txt | TLE | 2031 ms | 4252 KB |
subtask1-17.txt | TLE | 2033 ms | 4260 KB |
subtask1-18.txt | TLE | 2031 ms | 4128 KB |
subtask1-19.txt | TLE | 2031 ms | 4244 KB |
subtask1-20.txt | TLE | 2031 ms | 4264 KB |
subtask2-01.txt | TLE | 2030 ms | 4264 KB |
subtask2-02.txt | TLE | 2031 ms | 4256 KB |
subtask2-03.txt | WA | 259 ms | 4128 KB |
subtask2-04.txt | TLE | 2032 ms | 4260 KB |
subtask2-05.txt | TLE | 2030 ms | 4264 KB |
subtask2-06.txt | WA | 870 ms | 4008 KB |
subtask2-07.txt | TLE | 2031 ms | 4260 KB |
subtask2-08.txt | TLE | 2030 ms | 4336 KB |
subtask2-09.txt | TLE | 2031 ms | 4332 KB |
subtask2-10.txt | TLE | 2031 ms | 4268 KB |
subtask2-11.txt | TLE | 2032 ms | 4268 KB |
subtask2-12.txt | TLE | 2031 ms | 4264 KB |
subtask2-13.txt | TLE | 2030 ms | 4264 KB |
subtask2-14.txt | TLE | 2032 ms | 4260 KB |
subtask2-15.txt | TLE | 2032 ms | 4264 KB |
subtask2-16.txt | TLE | 2031 ms | 4260 KB |
subtask2-17.txt | TLE | 2031 ms | 4260 KB |
subtask2-18.txt | TLE | 2030 ms | 4260 KB |
subtask2-19.txt | TLE | 2031 ms | 4216 KB |
subtask2-20.txt | TLE | 2036 ms | 4308 KB |
subtask3-01.txt | TLE | 2031 ms | 7332 KB |
subtask3-02.txt | WA | 134 ms | 11912 KB |
subtask3-03.txt | TLE | 2033 ms | 23784 KB |
subtask3-04.txt | TLE | 2033 ms | 21144 KB |
subtask3-05.txt | TLE | 2034 ms | 23700 KB |
subtask3-06.txt | TLE | 2033 ms | 23816 KB |
subtask3-07.txt | TLE | 2035 ms | 23752 KB |
subtask3-08.txt | TLE | 2033 ms | 23752 KB |
subtask3-09.txt | TLE | 2034 ms | 22412 KB |
subtask3-10.txt | TLE | 2034 ms | 23792 KB |
subtask3-11.txt | AC | 562 ms | 20496 KB |
subtask3-12.txt | TLE | 2034 ms | 23748 KB |
subtask3-13.txt | TLE | 2032 ms | 23688 KB |
subtask3-14.txt | TLE | 2033 ms | 23688 KB |
subtask3-15.txt | TLE | 2033 ms | 23692 KB |
subtask3-16.txt | TLE | 2033 ms | 23704 KB |
subtask3-17.txt | TLE | 2033 ms | 23756 KB |
subtask3-18.txt | WA | 243 ms | 20096 KB |
subtask3-19.txt | TLE | 2033 ms | 23756 KB |
subtask3-20.txt | TLE | 2035 ms | 23700 KB |