제출 #1285665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285665		Faisal_Saqib	Bigger segments (IZhO19_segments)	C++20	0 / 100	1 ms	560 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],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]=i;
        // cout<<"If we fix "<<i<<endl;
        // for(int j=1;j<=i;j++)
        for(int j=i-1;j>=1;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);
            // }
            int e=mn[i-j];
            if(pre[i-j-e]>=2*pre[i-j]-pre[i])
            {
                dp[i][j]=max(dp[i][j],dp[i-j][e]+1);
            }
            else
            {
              dp[i][j]=max(dp[i][j],dp[i-j][e]);
            }
            if(dp[i][j]>0)
            {
                mn[i]=j;
            }
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans<<endl;
}

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