Submission #330258

---

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;

typedef long long ll;

const int kN = 100002;

int N;
ll L;

ll A[kN];
ll B[kN];
ll C[kN];

ll S[kN];
ll T[kN];

ll solve() {
  if (N > 5000) return -1LL;

  memset(S, 0, sizeof S);
  memset(T, 0, sizeof T);

  S[0] = B[0];
  T[0] = C[0];
  for (int i = 1; i < N; i++) {
    S[i] = S[i-1] + B[i];
    T[i] = T[i-1] + C[i];
  }

  ll ans = 1LL<<59;
  ll end_to_start = min(A[N-1], L - A[N-1]);

  for (int z = 0; z < N-1; z++) {
    ll x = T[z] - S[z];
    ll cost = 0;
    vector<ll> tmp;
    tmp.assign(B, B+N);

    cost += abs(x) * end_to_start;
    tmp[0] += x;
    tmp[N-1] -= x;

    for (int i = 0; i < N; i++) {
      ll delta = tmp[i] - C[i];
      tmp[i] -= delta;
      tmp[i+1] += delta;
      cost += abs(delta) * (A[i+1] - A[i]);
    }

    ans = min(ans, cost);
  }

  return ans;
}

int main() {
  while (cin>>N>>L) {
    for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i] >> C[i];
    }
    ll ans = solve();
    cout << ans << endl;
  }

  return 0;
}

Submission Info

Judge Result