Submission #831512

#	Time	Username	Problem	Language	Result	Execution time	Memory
831512		Cookie	Divide and conquer (IZhO14_divide)	C++14	100 / 100	41 ms	7624 KiB

divide

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const int mxn = 2e5 + 5;
const ll inf = 1e18;
struct Cool{
    int x, g, d;
    bool operator <(const Cool &b){
        return(x < b.x);
    }
};
int n;
vt<ll>comp;
Cool a[mxn + 1];
ll bit[mxn + 1], prefd[mxn + 1], prefg[mxn + 1];
void upd(int p, ll v){
    while(p <= sz(comp)){
        bit[p] = min(bit[p], v);
        p += p & (-p);
    }
}
ll get(int p){
    ll ans = inf;
    while(p){
        ans = min(ans, bit[p]);
        p -= p & (-p);
    }
    return(ans);
}

int find(ll x){
    return(lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].g >> a[i].d;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        prefd[i] = prefd[i - 1] + a[i].d;
        prefg[i] = prefg[i - 1] + a[i].g;
        comp.pb(prefd[i - 1] - a[i].x);
    }
    sort(comp.begin(), comp.end());
    for(int i = 1; i <= sz(comp); i++)bit[i] = inf;
    upd(find(prefd[0] - a[1].x), 0);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll need = prefd[i] - a[i].x;
        ans = max(ans, prefg[i] - get(find(need + 1) - 1));
        upd(find(prefd[i] - a[i + 1].x), prefg[i]);
    }
    cout << ans;
    return(0);
}

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