Submission #1285678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285678		Faisal_Saqib	Bigger segments (IZhO19_segments)	C++20	27 / 100	28 ms	4420 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l first
#define r second
const int N=1e3+100;
const ll inf=1e17;
ll 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]=inf;
        }
    }
    ll ans=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][1]=pre[i];
    }
    for(int j=2;j<=n;j++)
    {
        for(int i=j;i<=n;i++)
        {
            dp[i][j]=dp[i-1][j]+a[i];
            for(int ip=i-1;ip>=0;ip--)
            {
                if(pre[i]-pre[ip] >= dp[ip][j-1])
                {
                    // cout<<"For "<<i<<' '<<j<<" found "<<ip<<' '<<dp[ip][j-1]<<endl;
                    dp[i][j]=min(dp[i][j],pre[i]-pre[ip]);
                    break;
                }
            }
            if(dp[i][j]<inf)
            {
                // cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
                ans=max(ans,(ll)j);
            }
        }
    }
    cout<<ans<<endl;
}

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