Submission #765620

#	Time	Username	Problem	Language	Result	Execution time	Memory
765620		HD1	Divide and conquer (IZhO14_divide)	C++14	17 / 100	1 ms	340 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;
    s.push_back({0,{0,0}});
    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].ss.ff;
        energy[i]=energy[i-1]+s[i].ss.ss;
    }
    ll ans=0;
    ll j=0;
    for(ll i=1; i<=n; i++){
        while(j+1<=n and s[j+1].ff-s[i].ff<=energy[j+1]-energy[i-1]){
            j++;
        }
        ll go=gold[j]-gold[i-1];
        ans=max(ans,go);
    }
    cout<<ans<<endl;

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

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