Submission #685595

#	Time	Username	Problem	Language	Result	Execution time	Memory
685595		speedyArda	Divide and conquer (IZhO14_divide)	C++14	100 / 100	119 ms	7780 KiB

divide

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
ll maxi[MAXN], pref[MAXN], prefgold[MAXN];
struct camps 
{
    ll x = 0, g = 0, d = 0;
    
} in[MAXN];


int main() 
{
    int n;
    cin >> n;
    in[0].x = in[0].g = in[0].d = 0;
    ll curr = 0;
    //mini[0] = 1e18;
    pref[0] = 0;
    prefgold[0] = 0;
    for(int i = 1; i <= n; i++) {
        cin >> in[i].x >> in[i].g >> in[i].d;
        curr = in[i].d - (in[i].x - in[i-1].x);
       // mini[i] = min(mini[i - 1], curr);
        pref[i] = curr + pref[i - 1];
        prefgold[i] = in[i].g + prefgold[i - 1];
    }
    maxi[n] = pref[n];
    for(int i = n - 1; i >= 0; i--)
    {
        maxi[i] = maxi[i + 1];

        maxi[i] = max(maxi[i+1], pref[i]);
    }
   // for(int i = 1; i <= n; i++)
        //cout << maxi[i] << " ";
   // cout << "\n";
    //ll l = 1, r = 1e9;
    ll ans = 0;
    for(int beg = 1; beg <= n; beg++)
    {
        int l = beg, r = n;
        while(l <= r)
        {
            int m = (l + r) / 2;

            ll ch = maxi[m] - pref[beg];
            if(ch + in[beg].d >= 0)
            {
                ans = max(ans, prefgold[m] - prefgold[beg - 1]);
                l = m + 1;
            } else
                r = m - 1;
        }
    }
   

    cout << ans << "\n";
}

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