제출 #673995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
673995		Ahmed57	금 캐기 (IZhO14_divide)	C++14	100 / 100	39 ms	8008 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+1][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++){
        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: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52