#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};
dp[m][0]={0,1};
for(int i=1;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];
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]-1<0)
{
dp[r][m]=dp[r-1][m];
ans=max(ans,dp[r][m].fi);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];
//if(r==n&&m==8)cout<<z.fi<<endl;
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,dp[r][m].fi);
continue;
}
}
cout<<ans;
}
/*
10
2 3 2 1 1 5 5 2 5 1
*/
# |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
1100 KB |
Output is correct |
9 |
Correct |
1 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
1100 KB |
Output is correct |
9 |
Correct |
1 ms |
972 KB |
Output is correct |
10 |
Correct |
4 ms |
7500 KB |
Output is correct |
11 |
Correct |
7 ms |
7500 KB |
Output is correct |
12 |
Correct |
5 ms |
7500 KB |
Output is correct |
13 |
Correct |
4 ms |
7500 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
4 ms |
7520 KB |
Output is correct |
16 |
Incorrect |
5 ms |
8524 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
255212 KB |
Output is correct |
2 |
Correct |
162 ms |
255300 KB |
Output is correct |
3 |
Correct |
194 ms |
255300 KB |
Output is correct |
4 |
Correct |
164 ms |
255252 KB |
Output is correct |
5 |
Correct |
162 ms |
255300 KB |
Output is correct |
6 |
Correct |
167 ms |
255288 KB |
Output is correct |
7 |
Correct |
174 ms |
255296 KB |
Output is correct |
8 |
Correct |
162 ms |
255300 KB |
Output is correct |
9 |
Correct |
160 ms |
255216 KB |
Output is correct |
10 |
Correct |
179 ms |
255260 KB |
Output is correct |
11 |
Correct |
197 ms |
255300 KB |
Output is correct |
12 |
Correct |
165 ms |
255312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
1100 KB |
Output is correct |
9 |
Correct |
1 ms |
972 KB |
Output is correct |
10 |
Correct |
4 ms |
7500 KB |
Output is correct |
11 |
Correct |
7 ms |
7500 KB |
Output is correct |
12 |
Correct |
5 ms |
7500 KB |
Output is correct |
13 |
Correct |
4 ms |
7500 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
4 ms |
7520 KB |
Output is correct |
16 |
Incorrect |
5 ms |
8524 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
Correct |
1 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
1100 KB |
Output is correct |
9 |
Correct |
1 ms |
972 KB |
Output is correct |
10 |
Correct |
4 ms |
7500 KB |
Output is correct |
11 |
Correct |
7 ms |
7500 KB |
Output is correct |
12 |
Correct |
5 ms |
7500 KB |
Output is correct |
13 |
Correct |
4 ms |
7500 KB |
Output is correct |
14 |
Correct |
4 ms |
7500 KB |
Output is correct |
15 |
Correct |
4 ms |
7520 KB |
Output is correct |
16 |
Incorrect |
5 ms |
8524 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |