Submission #330269

---

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>
#include <numeric>

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 tmp[kN];
ll end_to_start;

ll f(ll x) {
  ll cost = 0;
  for (int i = 0; i < N; i++) {
    tmp[i] = B[i];
  }

  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]);
  }

  return cost;
}

ll solve() {
  ll ans = 1LL<<59;
  end_to_start = min(A[N-1], L - A[N-1]);
  const ll sum_b = accumulate(B, B+N, 0LL);
  ll lb = -sum_b, ub = sum_b;

  for (int z = 0; z < 100; z++) {
    ll lhs = (lb+lb+ub) / 3LL;
    ll rhs = (lb+ub+ub) / 3LL;

    ll lv = f(lhs);
    ll rv = f(rhs);
    ans = min(ans, min(lv, rv));

    if (lv < rv) {
      ub = rhs;
    }
    else {
      lb = lhs;
    }
  }

  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