# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
405555 |
2021-05-16T14:24:35 Z |
sad |
Cigle (COI21_cigle) |
C++14 |
|
286 ms |
255300 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
*/
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;
| ^~
# |
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 |
- |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
255212 KB |
Output is correct |
2 |
Correct |
228 ms |
255188 KB |
Output is correct |
3 |
Correct |
231 ms |
255292 KB |
Output is correct |
4 |
Correct |
231 ms |
255300 KB |
Output is correct |
5 |
Correct |
230 ms |
255256 KB |
Output is correct |
6 |
Correct |
227 ms |
255280 KB |
Output is correct |
7 |
Correct |
227 ms |
255208 KB |
Output is correct |
8 |
Correct |
233 ms |
255200 KB |
Output is correct |
9 |
Correct |
237 ms |
255280 KB |
Output is correct |
10 |
Correct |
238 ms |
255192 KB |
Output is correct |
11 |
Correct |
286 ms |
255296 KB |
Output is correct |
12 |
Correct |
225 ms |
255224 KB |
Output is correct |
# |
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 |
- |
# |
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 |
- |