Submission #1185861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185861		FaresSTH	Divide and conquer (IZhO14_divide)	C++20	17 / 100	0 ms	328 KiB

divide

#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    vector<array<int,3>>a(n);
    for(auto&i:a)cin>>i[0]>>i[1]>>i[2];
    sort(a.begin(),a.end());
    ll pg[n],pe[n];
    pg[0]=a[0][1];
    pe[0]=a[0][2];
    for(int i=1;i<n;i++){
        pg[i]=pg[i-1]+a[i][1];
        pe[i]=pe[i-1]+a[i][2];
    }
    int l[n],p=0;
    l[0]=0;

    for(int i=1;i<n;i++){
        while(p<i&&pe[i]-(p?pe[p-1]:0)<a[i][0]-a[p][0])p++;
        l[i]=p;
    }
    int r[n];
    r[n-1]=n-1;
    p=n-1;

    for(int i=n-2;i>=0;i--){
        while(p>i&&pe[p]-(i?pe[i-1]:0)<a[p][0]-a[i][0])p--;
        r[i]=p;
    }
    ll res=1;

    for(int i=0;i<n;i++){
        res=max({res,pg[i]-(l[i]?pg[l[i]-1]:0),pg[r[i]]-(i?pg[i-1]:0)});
    }
    cout<<res;
}

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