oj.uz

Submission #405561

# Submission time Handle Problem Language Result Execution time Memory
405561 2021-05-16T14:30:18 Z sad Cigle (COI21_cigle) C++14
22 / 100
 249 ms 253344 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;const int N=510,M=5009;
pair<int,int>dp[N][N];int a[N],fr[M],rw[N][N][N],prf[M];
pair<int,int>mxdp[N][N];
int main()
{
    cin>>n;int ans=0;
    for(int i=1;i<n+1;i++)cin>>a[i];
    for(int i=2;i<n;i++)
    {
        int sm=0;
        for(int j=i+1;j<n+1;j++)
        {
            if(j!=i+1)
            {
                sm+=a[j-1];
                fr[sm]=1;
            }

            int s=0,rs=0;
            for(int q=i-1;q>-1;q--)
            {
                if(q!=i-1)
                {
                    s+=a[q+2];
                    if(fr[s])
                        rs++;
                }
                rw[q][i][j]=rs;
            }

        }
        for(int j=n;j>i;j--)
        {
            if(j!=i+1)
            {
                fr[sm]=0;
                sm-=a[j-1];
            }
        }

    }
    for(int m=1;m<=n-1;m++)
    {/*
        memset(prf,-1,sizeof prf);
        int re=0;
        for(int i=m;i>0;i--)
        {
            re+=a[i];
            prf[re]=i;
        }
        re=0;
        dp[m][m]={0,n+1};
        mxdp[m][1]={dp[m][1].fi,1};
        for(int i=2;i<m;i++)
        {
            if(dp[m][i].fi>mxdp[m][i-1].fi)
            {
                mxdp[m][i]={dp[m][i].fi,i};continue;
            }
            mxdp[m][i]=mxdp[m][i-1];
        }
        dp[m+1][m]=mxdp[m][m-1];ans=max(ans,dp[m+1][m].fi);*/
        for(int r=m+1;r<n+1;r++)
        {
            /*re+=a[r-1];
            int last=dp[r-1][m].se;
            int mx=dp[r-1][m].fi;
            if(prf[re]==-1||prf[re]-2<0)
            {
                dp[r][m]=dp[r-1][m];
                ans=max(ans,mx);continue;
            }*/
            for(int l=0;l<m;l++)
                dp[r][m].fi=max(dp[r][m].fi,dp[m][l].fi+rw[l][m][r]);
            ans=max(ans,dp[r][m].fi);
            /*
            if(last+2<=prf[re])
            {
                dp[r][m]={mx+1,last};
                ans=max(ans,dp[r][m].fi);continue;
            }
            pair<int,int>z=mxdp[m][prf[re]-2];
            z.fi+=rw[prf[re]-2][m][r];
            if(z.fi>mx)
            {
                dp[r][m]=z;
                ans=max(ans,z.fi);continue;
            }
            dp[r][m]=dp[r-1][m];
            ans=max(ans,mx);
            continue;*/
        }
    }
    cout<<ans;

}
/*
10
2 3 2 1 1 5 5 2 5 1
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 4 ms 7116 KB Output is correct
11 Correct 4 ms 7116 KB Output is correct
12 Correct 4 ms 7116 KB Output is correct
13 Correct 4 ms 7116 KB Output is correct
14 Correct 4 ms 7116 KB Output is correct
15 Correct 5 ms 7116 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Incorrect 4 ms 7116 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 253220 KB Output is correct
2 Correct 217 ms 253184 KB Output is correct
3 Correct 228 ms 253336 KB Output is correct
4 Correct 227 ms 253264 KB Output is correct
5 Correct 218 ms 253252 KB Output is correct
6 Correct 225 ms 253284 KB Output is correct
7 Correct 224 ms 253172 KB Output is correct
8 Correct 224 ms 253272 KB Output is correct
9 Correct 222 ms 253344 KB Output is correct
10 Correct 220 ms 253260 KB Output is correct
11 Correct 220 ms 253232 KB Output is correct
12 Correct 249 ms 253288 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 4 ms 7116 KB Output is correct
11 Correct 4 ms 7116 KB Output is correct
12 Correct 4 ms 7116 KB Output is correct
13 Correct 4 ms 7116 KB Output is correct
14 Correct 4 ms 7116 KB Output is correct
15 Correct 5 ms 7116 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Incorrect 4 ms 7116 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 4 ms 7116 KB Output is correct
11 Correct 4 ms 7116 KB Output is correct
12 Correct 4 ms 7116 KB Output is correct
13 Correct 4 ms 7116 KB Output is correct
14 Correct 4 ms 7116 KB Output is correct
15 Correct 5 ms 7116 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Incorrect 4 ms 7116 KB Output isn't correct
18 Halted 0 ms 0 KB -