Submission #765574

#	Time	Username	Problem	Language	Result	Execution time	Memory
765574		HD1	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1069 ms	3400 KiB

divide

//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
const ll MAX=1e5+10;
const ll mod=1e9+7;
const ll inf=1e18+7;
vector<pair<ll,ii>>s;
ll gold[MAX], energy[MAX];
void solve(){
    ll n;
    cin>>n;
    for(ll i=0; i<n; i++){
        ll x, g, e;
        cin>>x>>g>>e;
        s.push_back({x,{g,e}});
    }
    sort(s.begin(),s.end());
    for(ll i=1; i<=n; i++){
        gold[i]=gold[i-1]+s[i-1].ss.ff;
        energy[i]=energy[i-1]+s[i-1].ss.ss;
    }
    ll ans=0;
    for(ll i=1; i<=n; i++){
        for(ll j=i; j<=n; j++){
            ll eg=energy[j]-energy[i-1];
            ll go=gold[j]-gold[i-1];
            ll distance=s[j-1].ff-s[i-1].ff;
            if(distance<=eg){
                ans=max(ans, go);
            }
        }
    }
    cout<<ans<<endl;

}
int main(){
    fastio;
    solve();
    return 0;
}

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