Submission #1285687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285687		Faisal_Saqib	Bigger segments (IZhO19_segments)	C++20	0 / 100	1 ms	572 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];
ll mi[N],sm[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    int n;
    cin>>n;
    // cin>>a[i]
    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=0;
    for(int i=1;i<=n;i++)
    {
        mi[i]=inf;
        sm[i]=inf;
    //     dp[i][1]=pre[i];
    }
    mi[1]=1;
    sm[1]=pre[1];
    for(int j=2;j<=n;j++)
    {
        // cout<<"Shown for "<<j<<endl;
        int s=j-1,e=n+1;
        while(s+1<e)
        {
            int mid=(s+e)/2;
            if(pre[mid]-pre[mi[j-1]] >= sm[j-1])
            {
                e=mid;
            }
            else
            {
                s=mid;
            }
        }
        if(e!=(n+1))
        {
            mi[j]=e;
            s=mi[j-1],e=n+1;
            while(s+1<e)
            {
                int mid=(s+e)/2;
                if(pre[e]-pre[mid] >= pre[mid]-pre[mi[j-1]]+sm[j-1])
                {
                    s=mid;
                }
                else
                {
                    e=mid;
                }
            }
            sm[j]=pre[e]-pre[s];
        }
        // 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;
        //         }
        //     }
        //     ll mi=inf;
        //     if(dp[i][j]<inf)
        //     {
        //         // cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
        //         ans=max(ans,(ll)j);
        //         if(mi==inf)mi=i;
        //         if(dp[mi][j]>dp[i][j])
        //         {
        //             cout<<"Masla"<<endl;
        //             // cout<<
        //         }
        //         // cout<<dp[i][j]<<' ';
        //     }
        // }
        if(mi[j]<inf)
        {
            ans=max(ans,(ll)j);
        }
        else
        {
            break;
        }
        // cout<<endl;
    }
    cout<<ans<<endl;
}

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