Submission #102970

#	Time	Username	Problem	Language	Result	Execution time	Memory
102970		brcode	Divide and conquer (IZhO14_divide)	C++14	17 / 100	144 ms	5728 KiB

divide

#include <iostream>

using namespace std;
const long long MAXN = 1e5+5;
long long pos[MAXN];
long long d[MAXN];
long long g[MAXN];
int main(){
    long long n;
    cin>>n;
    for(long long i=1;i<=n;i++){
        cin>>pos[i]>>g[i]>>d[i];
    }
    long long l = 1;
    long long r = 1;
    long long ans = g[1];
    long long holdlen = d[1];
    long long holdgold = g[1];
    
    while(l<=r && (r<=n)){
       // cout<<holdgold<<" "<<holdlen<<" "<<l<<" "<<r<<endl;
        if(l == r){
            ans = max(ans,g[r]);
            r++;
            holdlen+=d[r];
            holdgold+=g[r];
            continue;
        }
        if(pos[r]-pos[l]>holdlen){
            
            holdlen-=d[l];
            holdgold-=g[l];
            l++;
            
            continue;
        }else{
            ans = max(ans,holdgold);
            r++;
            holdlen+=d[r];
            holdgold+=g[r];
        }
    }
    ans = max(ans,holdgold);
    cout<<ans<<endl;
}

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