Submission #673987

#	Time	Username	Problem	Language	Result	Execution time	Memory
673987		Ahmed57	Divide and conquer (IZhO14_divide)	C++14	0 / 100	1 ms	340 KiB

divide

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    long long arr[n][3];
    for(int i = 1;i<=n;i++){
        long long x,g,en;
        cin>>x>>g>>en;
        arr[i][0] = x, arr[i][1] = g,arr[i][2] = en;
    }
    vector<pair<long long,long long>> v;
    long long dist = 0 , energy = 0 , gold = 0;
    for(int i = 1;i<=n;i++){
        if(i>1)dist+=arr[i][0]-arr[i-1][0];
        v.push_back({energy-dist,gold});
        energy+=arr[i][2];
        gold+=arr[i][1];
    }
    long long tab[n];
    sort(v.begin(),v.end());
    long long mi = 1e18;
    for(int i = 0;i<n;i++){
        mi = min(mi,v[i].second);
        tab[i] = mi;
    }
    long long ma = 0;
    dist = 0 , energy = 0 , gold = 0;
    for(int i = 1;i<=n;i++){
        ma = max(ma,arr[i][1]);
        energy+=arr[i][2];
        gold+=arr[i][1];
        if(i>1)dist+=arr[i][0]-arr[i-1][0];
        if(energy-dist>=0){
            ma = max(ma,gold);
        }else{
            pair<long long,long long>p = {energy-dist+1,-1};
            int it = lower_bound(v.begin(),v.end(),p)-v.begin();
            it--;
            if(it>=0){
                ma = max(ma,gold-tab[it]);
            }
        }
    }
    cout<<ma;
}

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