Submission #336156

#	Time	Username	Problem	Language	Result	Execution time	Memory
336156		kkk	Bigger segments (IZhO19_segments)	C++14	100 / 100	80 ms	12524 KiB

segments

#include<iostream>
#define endl '\n'
using namespace std;
long long a[1000006],dp[1000006],pos[10000006];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,i,c,le,ri,r,mid;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>c;
        a[i]=a[i-1]+c;
    }
    for(i=1;i<=n;i++)
    {
        if(pos[i]<pos[i-1])pos[i]=pos[i-1];
        dp[i]=dp[pos[i]]+1;
        r=a[i]-a[pos[i]];
        le=i+1;ri=n;
        long long ind=0;
        while(le<=ri)
        {
            mid=(le+ri)/2;
            if(r<=a[mid]-a[i])
            {
                ri=mid-1;ind=mid;
            }
            else le=mid+1;
        }
        pos[ind]=i;
    }
    cout<<dp[n]<<endl;

}

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