Submission #175741

#	Time	Username	Problem	Language	Result	Execution time	Memory
175741		_Enkognit	Bigger segments (IZhO19_segments)	C++14	100 / 100	119 ms	24824 KiB

segments

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pll pair<ll,ll>
#define y1 Enkognit
#define fi first
#define se second
#define pld pair<ld,ld>

using namespace std;

const ll MOD=1000000007;

ll l, r, n, m, k, x, y, a[1000001], bst[1000001], pr[1000001];
pll dp[1000001];
ll tt[1000001];
vector <ll> an;

ll binpow(ll h,ll r)
{
    ll l=1;
    while (r)
    {
        if (r&1) l*=h,l%=MOD;
        h*=h;
        h%=MOD;
        r/=2;
    }
    return l;
}


int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) {cin >> a[i];pr[i]=pr[i-1]+a[i];}
    ll lr=0;
    for (ll i = 1; i <= n; i++)
    {
        lr=max(lr,bst[i]);
        dp[i]=mp(pr[i]-pr[lr],dp[lr].se+1);
        if (pr[n]-pr[i]>=dp[i].fi)
        {
            ll l=i+1, r=n;
            while (l<r)
            {
                ll w=(l+r)/2;
                if (pr[w]-pr[i]>=dp[i].fi) r=w; else l=w+1;
            }
            bst[l]=max(bst[l],i);
        }
    }
    cout << dp[n].se;
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27