Submission #332438

#	Time	Username	Problem	Language	Result	Execution time	Memory
332438		nvmdava	Divide and conquer (IZhO14_divide)	C++17	100 / 100	43 ms	10344 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 100'005;
const ll MOD = 1'000'000'007;
const int INF = 0x3f3f3f3f;

ll x[N], g[N], d[N];
ll p1[N], p2[N];
ll w1[N], w2[N];

vector<pair<ll, ll>> v; 
ll ans = 0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i = 1; i <= n; ++i){
        cin>>x[i]>>g[i]>>d[i];
        p2[i] = p1[i + 1] = p1[i] + d[i];
        w2[i] = w1[i + 1] = w1[i] + g[i];
    }
    for(int i = 1; i <= n; ++i){
        p2[i] -= x[i];
        p1[i] -= x[i];
    }

    for(int i = n; i >= 1; --i){
        if(v.empty() || v.back().ff < p2[i])
            v.push_back({p2[i], w2[i]});

        ans = max(ans, lower_bound(v.begin(), v.end(), p1[i], [](const pair<ll, ll>& lhs, const int& rhs){
            return lhs.ff < rhs;
        }) -> ss - w1[i]);
    }

    cout<<ans;
}

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