Submission #759865

#	Time	Username	Problem	Language	Result	Execution time	Memory
759865		Trunkty	Divide and conquer (IZhO14_divide)	C++14	100 / 100	28 ms	11004 KiB

divide

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,ans;
int x[100005],g[100005],preg[100005],d[100005];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> x[i] >> g[i] >> d[i];
        preg[i] = preg[i-1]+g[i];
    }
    vector<vector<int>>v;
    x[0] = x[1];
    int curr=0;
    for(int i=1;i<=n;i++){
        curr -= (x[i]-x[i-1]);
        if(v.size()==0 or v.back()[0]>curr){
            v.push_back({curr,i});
        }
        curr += d[i];
        int low=0,high=v.size()-1;
        while(low!=high){
            int mid = (low+high)/2;
            if(v[mid][0]>curr){
                low = mid+1;
            }
            else{
                high = mid;
            }
        }
        ans = max(ans,preg[i]-preg[v[low][1]-1]);
    }
    cout << ans << "\n";
    return 0;
}

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