Submission #1344450

#TimeUsernameProblemLanguageResultExecution timeMemory
1344450WarinchaiDivide and conquer (IZhO14_divide)C++20
100 / 100
30 ms6816 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int x[100005],g[100005],d[100005];
int sumg[100005];
int sumd[100005];
int l[100005];
int n;
int inf=1e18;
vector<pair<int,int>>v;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>g[i]>>d[i];
        sumd[i]=sumd[i-1]+d[i];
        sumg[i]=sumg[i-1]+g[i];
    }
    int ans=0;
    pair<int,int>mn={inf,inf};
    for(int i=1;i<=n;i++)v.push_back({sumd[i-1]-x[i],i});
    sort(v.begin(),v.end());
    l[0]=inf;
    for(int i=1;i<=v.size();i++){
        l[i]=min(l[i-1],v[i-1].second);
    }
    for(int i=1;i<=n;i++){
        int val=sumd[i]-x[i];
        int id=upper_bound(v.begin(),v.end(),make_pair(val,inf))-v.begin();
        int ll=l[id];
        if(ll<=i){
            ans=max(ans,sumg[i]-sumg[ll-1]);
        }
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...