Submission #1028304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028304		andrewp	Divide and conquer (IZhO14_divide)	C++14	100 / 100	26 ms	6316 KiB

divide

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

#define ll int64_t
#define ar array

const int mxN=1e5+4;
ll n, x[mxN], g[mxN], e[mxN];
ll srch[mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> x[i] >> g[i] >> e[i];
    }
    for(int i=1; i<=n+3; ++i) {
        srch[i]=(ll)(-1e12);
    }
    for(int i=1; i<=n; ++i) {
        e[i]+=e[i-1];
        g[i]+=g[i-1];//umesto fenw
    }
    for(int i=n; i>=1; --i) srch[i]=max(srch[i+1], e[i]-x[i]);
    ll ans=0;
    for(int i=1; i<=n; ++i) {
        int lb=i, rb=n, slv=0;
        while(lb<=rb) {
            int mb=(lb+rb)/2;
            if(srch[mb]>=e[i-1]-x[i]) {
                lb=mb+1;
                slv=mb;
            }
            else {
                rb=mb-1;
            }
        }
        ans=max(ans, g[slv]-g[i-1]);
    }
    cout << ans << "\n";
	return 0;
}

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