Submission #1285660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285660		Faisal_Saqib	Bigger segments (IZhO19_segments)	C++20	27 / 100	18 ms	4488 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l first
#define r second
const int N=1e3+100;
int a[N];
ll pre[N];
ll dp[N][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;
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k<=(i-j);k++)
            {
                // if(pre[i-j-k]>=2*pre[i-j]-pre[i])
                if(pre[i]-pre[i-j] >= pre[i-j]-pre[i-j-k])
                {
                    // if(i==3 and j==1)
                    // {
                    //     cout<<pre[i]-pre[i-j]<<' '<<pre[i-j]-pre[i-j-k]<<endl;
                    //     cout<<i-j<<' '<<k<<' '<<dp[i-j][k]<<endl;
                    // }
                    dp[i][j]=max(dp[i][j],dp[i-j][k]+1);
                }
            }
            // if(dp[i][j]==4)
            // {
            //     cout<<i<<' '<<j<<endl;
            // }
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans<<endl;
}

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