Submission #598118

#	Time	Username	Problem	Language	Result	Execution time	Memory
598118		daisy2	Bigger segments (IZhO19_segments)	C++14	100 / 100	89 ms	21088 KiB

segments

#include<bits/stdc++.h>
#include<vector>
#define endl '\n'
using namespace std;
long long n,dp[500005],a,pr[500005],s[500005];
vector<long long> sum;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    sum.push_back(0);
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        pr[i]=pr[i-1]+a;
        sum.push_back(pr[i]);
        s[i]=1000000000000000;
    }
    dp[1]=1;
    s[1]=pr[1];
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i],dp[i-1]);
        s[i]=min(s[i],s[i-1]+pr[i]-pr[i-1]);

        long long in = lower_bound(sum.begin(),sum.end(),pr[i]+s[i])- sum.begin();

        if(dp[in]==dp[i]+1)
        {
            s[in]=min(s[in],pr[in]-pr[i]);
        }
        else if(dp[in]<dp[i]+1)
        {
            dp[in]=dp[i]+1;
            s[in]=pr[in]-pr[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