Submission #171391

#	Time	Username	Problem	Language	Result	Execution time	Memory
171391		VEGAnn	Divide and conquer (IZhO14_divide)	C++14	100 / 100	83 ms	5972 KiB

divide

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pll pair<ll, ll>
using namespace std;
typedef long long ll;
const ll OO = 1e18;
const int N = 100100;
vector<pll> vc;
vector<ll> suf;
ll ans = 0;
int n, x[N], g[N], e[N];

void calc(int l, int r){
    if (l == r){
        ans = max(ans, (ll)g[l]);
        return;
    }
    int md = (l + r) >> 1;
    calc(l, md);
    calc(md + 1, r);
    vc.clear();
    ll sm = 0, en = 0;
    for (int i = md; i >= l; i--) {
        sm += g[i];
        en += e[i];
        vc.PB(MP(en + x[i], sm));
    }
    sort(all(vc));
    suf.resize(sz(vc) + 1);
    suf[sz(vc)] = -OO;
    for (int i = sz(vc) - 1; i >= 0; i--)
        suf[i] = max(suf[i + 1], vc[i].sd);
    sm = en = 0;
    for (int i = md + 1; i <= r; i++){
        sm += g[i];
        en += e[i];
        int ps = lower_bound(all(vc), MP(-(en - ll(x[i])), -OO)) - vc.begin();
        ans = max(ans, suf[ps] + sm);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("penguins.in","r",stdin); freopen("penguins.out","w",stdout);
//    freopen("in.txt","r",stdin);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> x[i] >> g[i] >> e[i];
    calc(0, n - 1);
    cout << ans;
    return 0;
}

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