Submission #1061141

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define INF 1145141919

int N, L;
int A[100000], B[100000];

int d(int a, int b) {
  if (a > b) swap(a, b);
  return min(abs(A[b] - A[a]), abs(A[a]+L - A[b]));
}

int main() {
  cin >> N >> L;
  for (int i=0; i<N; i++) {
    int b, c;
    cin >> A[i] >> b >> c;
    B[i] = c-b;
  }
  long long m = 0;
  while (true) {
    int s = INF, sa = -1, sb = -1;
    for (int i=0; i<N; i++) {
      if (B[i] > 0) {
        int l = (i-1+N)%N, r = (i+1)%N;
        while (B[l] >= 0) l = (l-1+N)%N;
        while (B[r] >= 0) r = (r+1)%N;
        if (d(i,l) > d(i,r)) swap(l, r);
        if (s > d(i, l)) {
          s = d(i, l);
          sa = i, sb = l;
        }
      }
    }
    if (sa == -1) break;
    int g = min(B[sa], -B[sb]);
    m += (long long)d(sa, sb) * (long long)g;
    B[sa] -= g, B[sb] += g;
  }
  cout << m << "\n";
  return 0;
}

Submission Info

Judge Result