Submission #125677

#	Time	Username	Problem	Language	Result	Execution time	Memory
125677		minh_star	Divide and conquer (IZhO14_divide)	C++14	100 / 100	56 ms	7236 KiB

divide

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
long long x[maxn], g[maxn], r[maxn];
typedef pair<long long, int> ii;
ii a[maxn];
int n;
void readinp(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> x[i] >> g[i] >> r[i];
    }
    for (int i = 1; i <= n; i++){
        r[i] = r[i-1] + r[i];
        g[i] = g[i-1] + g[i];
    }
}
void process(){
    for (int i = 1; i <= n; i++){
        a[i].first = r[i-1] - x[i];
        a[i].second = i;
    }
    sort(a+1, a+1+n);
    a[0].second = n + 1;
    for (int i = 1; i <= n; i++){
        a[i].second = min (a[i].second, a[i - 1].second);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++){
        long long w = r[i] - x[i];
        int l = 1;
        int r = n;
        int res = 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (a[mid].first <= w){
                l = mid + 1;
                res = a[mid].second;
            }
            else{
                r = mid - 1;
            }
        }
        ans = max(ans, g[i] - g[res - 1]);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    readinp();
    process();
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52