Submission #653012

#	Time	Username	Problem	Language	Result	Execution time	Memory
653012		vladutpiele	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	212 KiB

segments

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int nmax = 500000;

int n;
int v[nmax + 5], sume[nmax + 5];

struct elem
{
    int maxSeg; /// in cate segmente impart prefixul [1 ... i]
    int maxPrv; /// capatul stanga al ultimului segment
};

elem dp[nmax + 5];

void update(int a,int b)
{
    if(dp[a].maxSeg < dp[b].maxSeg)
    {
        dp[a] = dp[b];
    }
    else
    {
        if(dp[a].maxSeg == dp[b].maxSeg && dp[a].maxPrv < dp[b].maxPrv)
        {
            dp[a] = dp[b];
        }
    }
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i];
        sume[i] = sume[i - 1] + v[i];
    }
    dp[1].maxSeg = 1;
    dp[1].maxPrv = 1;
    for(int i = 1; i <= n; i ++)
    {
        update(i, i - 1);
        int st = i + 1, dr = n;
        int pozmin = n + 1;
        while(st <= dr)
        {
            int mid = (st + dr) >> 1;
            int S = sume[mid] - sume[i];
            if(S >= sume[i] - sume[dp[i].maxPrv - 1])
            {
                pozmin = mid;
                dr = mid - 1;
            }
            else
            {
                st = mid + 1;
            }
        }
        if(pozmin <= n)
        {
            dp[n + 1].maxSeg = dp[i].maxSeg + 1;
            dp[n + 1].maxSeg = i + 1;
            update(pozmin, n + 1);
        }
    }
    cout << dp[n].maxSeg << '\n';
    return 0;
}

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