Submission #1285721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285721		Faisal_Saqib	Bigger segments (IZhO19_segments)	C++20	13 / 100	1 ms	584 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+100;
int a[N];
ll pre[N];
pair<int,int> dp[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pre[i]=a[i]+pre[i-1];
        dp[i]={1,-pre[i]};
    }
    dp[0]={1,0};
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i],{dp[i-1].first,dp[i-1].second-a[i]});
        // find j such dp[i].second <= pre[j]-pre[i]
        // cout<<"for "<<i<<' '<<dp[i].first<<' '<<dp[i].second<<endl;;
        int s=i,e=n+1;
        while(s+1<e)
        {
            int mid=(s+e)/2;
            if(-pre[mid]+pre[i] <= dp[i].second)
            {
                e=mid;
            }
            else
            {
                s=mid;
            }
        }
        if(e<(n+1))
        {
            // cout<<"Update "<<e<<' '<<dp[e].first<<' '<<dp[e].second<<endl;
            // cout<<dp[i].first+1<<' '<<pre[i]-pre[e]<<endl;
            dp[e]=max(dp[e],{dp[i].first+1,-pre[e]+pre[i]});
        }
    }
    cout<<dp[n].first<<endl;
}

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