# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
405546 |
2021-05-16T14:17:29 Z |
sad |
Cigle (COI21_cigle) |
C++14 |
|
0 ms |
0 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];mx=max(mx,dp[m+1][m].fi);
for(int r=m+2;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;
}/*
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:69:33: error: 'mx' was not declared in this scope; did you mean 'm'?
69 | dp[m+1][m]=mxdp[m][m-1];mx=max(mx,dp[m+1][m].fi);
| ^~
| m
cigle.cpp:72:17: warning: unused variable 'last' [-Wunused-variable]
72 | int last=dp[r-1][m].se;
| ^~~~