Submission #1285661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285661		Faisal_Saqib	Bigger segments (IZhO19_segments)	C++20	37 / 100	109 ms	71232 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l first
#define r second
const int N=3e3+5;
int a[N];
ll pre[N];
ll dp[N][N],mn[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]=pre[i-1]+a[i];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            dp[i][j]=-1e9;
        }
    }
    dp[0][0]=0;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        dp[i][i]=1;
        mn[i]=1e9;
        // cout<<"If we fix "<<i<<endl;
        for(int j=1;j<=i;j++)
        {
            // k is a range
            // as k increases pre[i-j-k] decreases
            // find minimum k that satisfy the condition
            int s=-1,e=i-j+1;
            while(s+1<e)
            {
                int mid=(s+e)/2;
                if(pre[i-j-mid]>=2*pre[i-j]-pre[i])
                {
                    e=mid;
                }
                else
                {
                    s=mid;
                }
            }
            if(e!=(i-j+1))
            {
                dp[i][j]=max(dp[i][j],dp[i-j][e]+1);
            }
            else
            {
                // no k this dp is null
            }
            e=mn[i-j];
            if(e!=1e9 and pre[i-j-e]>=2*pre[i-j]-pre[i])
            {
                dp[i][j]=max(dp[i][j],dp[i-j][e]+1);
            }
            if(dp[i][j]>0 and mn[i]==1e9)
            {
                mn[i]=j;
            }
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans<<endl;
}

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