oj.uz

Submission #405552

# Submission time Handle Problem Language Result Execution time Memory
405552 2021-05-16T14:23:23 Z sad Cigle (COI21_cigle) C++14
13 / 100
 269 ms 255332 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;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
*/

Compilation message

cigle.cpp: In function 'int main()':
cigle.cpp:72:17: warning: unused variable 'last' [-Wunused-variable]
   72 |             int last=dp[r-1][m].se;
      |                 ^~~~
cigle.cpp:73:17: warning: unused variable 'mx' [-Wunused-variable]
   73 |             int mx=dp[r-1][m].fi;
      |                 ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Incorrect 1 ms 972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Incorrect 1 ms 972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 255264 KB Output is correct
2 Correct 269 ms 255204 KB Output is correct
3 Correct 235 ms 255252 KB Output is correct
4 Correct 231 ms 255300 KB Output is correct
5 Correct 237 ms 255268 KB Output is correct
6 Correct 264 ms 255248 KB Output is correct
7 Correct 234 ms 255200 KB Output is correct
8 Correct 242 ms 255240 KB Output is correct
9 Correct 237 ms 255332 KB Output is correct
10 Correct 237 ms 255300 KB Output is correct
11 Correct 234 ms 255248 KB Output is correct
12 Correct 233 ms 255300 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Incorrect 1 ms 972 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Incorrect 1 ms 972 KB Output isn't correct
8 Halted 0 ms 0 KB -