Submission #7607881

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T> void chmin(T& x, T y) { if (x > y) x = y; }
int main() {
    int N, L; cin >> N >> L;
    vector<int> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i];
    vector<int> human, goal;
    for (int i = 0; i < N; i++) {
        int t = abs(B[i] - C[i]);
        vector<int> &to = B[i] > C[i] ? human : goal;
        while (t--) to.push_back(A[i]);
    }
    int M = human.size();
    auto calc = [&](int i) {
        Int a = 0;
        for (int j = 0; j < M; j++) {
            int h = human[j];
            int g = goal[(i + j) % M];
            a += min({ abs(h - g), abs(h - g - L), abs(h - g + L) });
        }
        return a;
    };
    int left = 0, right = M - 1;
    while (right - left > 2) {
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;
        if (calc(mid1) <= calc(mid2)) {
            right = mid2;
        } else {
            left = mid1;
        }
    }
    Int ans = 1e18;
    chmin(ans, calc(0));
    chmin(ans, calc(left));
    chmin(ans, calc(left + 1));
    chmin(ans, calc(right));
    chmin(ans, calc(M - 1));
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result