Submission #5251240

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int N, T[20000], A[20000], B[20000];

bool check(int X){
    vector<int> L2R[20000];
    for(int i=0; i<N; i++){
        int d = (A[i] - X) / B[i];
        int64_t l = max(0, T[i]-d), r = min(N-1, T[i]+d);
        L2R[l].push_back(r);
    }
    priority_queue<int, vector<int>, greater<int>> R;
    for(int i=0; i<N; i++){
        for(int r : L2R[i]) R.push(r);
        if(R.size() == 0) return false;
        int r = R.top(); R.pop();
        if(r < i) return false;
    }
    return true;
}

int main(){
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> T[i] >> A[i] >> B[i];
        T[i]--;
    }

    int64_t ok = -1e9-1, ng = *min_element(A, A+N) + 1;
    while(ng-ok>1){
        int64_t mid = (ok+ng)/2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
    return 0;
}

Submission Info

Judge Result