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
AC × 2
AC × 5
TLE × 17
AC × 5
WA × 2
TLE × 35
AC × 6
WA × 4
TLE × 52
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