Submission #1185866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185866		FaresSTH	Divide and conquer (IZhO14_divide)	C++20	48 / 100	1094 ms	1608 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];
    }
    ll res=1;

    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(pe[j]-(i?pe[i-1]:0)>=a[j][0]-a[i][0])res=max(res,pg[j]-(i?pg[i-1]:0));
        }
    }
    cout<<res;
}

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