# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
405569 |
2021-05-16T14:36:37 Z |
sad |
Cigle (COI21_cigle) |
C++14 |
|
1000 ms |
269996 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=500*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+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:72:17: warning: unused variable 'last' [-Wunused-variable]
72 | int last=dp[r-1][m].se;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
10644 KB |
Output is correct |
2 |
Correct |
27 ms |
10704 KB |
Output is correct |
3 |
Correct |
28 ms |
10676 KB |
Output is correct |
4 |
Correct |
26 ms |
10680 KB |
Output is correct |
5 |
Correct |
27 ms |
10648 KB |
Output is correct |
6 |
Correct |
28 ms |
10700 KB |
Output is correct |
7 |
Correct |
28 ms |
10828 KB |
Output is correct |
8 |
Correct |
28 ms |
10852 KB |
Output is correct |
9 |
Correct |
29 ms |
10776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
10644 KB |
Output is correct |
2 |
Correct |
27 ms |
10704 KB |
Output is correct |
3 |
Correct |
28 ms |
10676 KB |
Output is correct |
4 |
Correct |
26 ms |
10680 KB |
Output is correct |
5 |
Correct |
27 ms |
10648 KB |
Output is correct |
6 |
Correct |
28 ms |
10700 KB |
Output is correct |
7 |
Correct |
28 ms |
10828 KB |
Output is correct |
8 |
Correct |
28 ms |
10852 KB |
Output is correct |
9 |
Correct |
29 ms |
10776 KB |
Output is correct |
10 |
Correct |
108 ms |
17296 KB |
Output is correct |
11 |
Correct |
112 ms |
17220 KB |
Output is correct |
12 |
Correct |
93 ms |
17300 KB |
Output is correct |
13 |
Correct |
99 ms |
17296 KB |
Output is correct |
14 |
Correct |
93 ms |
17220 KB |
Output is correct |
15 |
Correct |
102 ms |
17256 KB |
Output is correct |
16 |
Correct |
110 ms |
18004 KB |
Output is correct |
17 |
Correct |
96 ms |
17452 KB |
Output is correct |
18 |
Correct |
97 ms |
17436 KB |
Output is correct |
19 |
Correct |
119 ms |
17480 KB |
Output is correct |
20 |
Correct |
117 ms |
17540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
713 ms |
265072 KB |
Output is correct |
2 |
Correct |
687 ms |
265096 KB |
Output is correct |
3 |
Correct |
798 ms |
265028 KB |
Output is correct |
4 |
Correct |
728 ms |
265000 KB |
Output is correct |
5 |
Correct |
719 ms |
265028 KB |
Output is correct |
6 |
Correct |
731 ms |
265104 KB |
Output is correct |
7 |
Correct |
698 ms |
265092 KB |
Output is correct |
8 |
Correct |
678 ms |
265080 KB |
Output is correct |
9 |
Correct |
715 ms |
265000 KB |
Output is correct |
10 |
Correct |
739 ms |
265104 KB |
Output is correct |
11 |
Correct |
733 ms |
265028 KB |
Output is correct |
12 |
Correct |
694 ms |
265080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
10644 KB |
Output is correct |
2 |
Correct |
27 ms |
10704 KB |
Output is correct |
3 |
Correct |
28 ms |
10676 KB |
Output is correct |
4 |
Correct |
26 ms |
10680 KB |
Output is correct |
5 |
Correct |
27 ms |
10648 KB |
Output is correct |
6 |
Correct |
28 ms |
10700 KB |
Output is correct |
7 |
Correct |
28 ms |
10828 KB |
Output is correct |
8 |
Correct |
28 ms |
10852 KB |
Output is correct |
9 |
Correct |
29 ms |
10776 KB |
Output is correct |
10 |
Correct |
108 ms |
17296 KB |
Output is correct |
11 |
Correct |
112 ms |
17220 KB |
Output is correct |
12 |
Correct |
93 ms |
17300 KB |
Output is correct |
13 |
Correct |
99 ms |
17296 KB |
Output is correct |
14 |
Correct |
93 ms |
17220 KB |
Output is correct |
15 |
Correct |
102 ms |
17256 KB |
Output is correct |
16 |
Correct |
110 ms |
18004 KB |
Output is correct |
17 |
Correct |
96 ms |
17452 KB |
Output is correct |
18 |
Correct |
97 ms |
17436 KB |
Output is correct |
19 |
Correct |
119 ms |
17480 KB |
Output is correct |
20 |
Correct |
117 ms |
17540 KB |
Output is correct |
21 |
Correct |
713 ms |
265072 KB |
Output is correct |
22 |
Correct |
687 ms |
265096 KB |
Output is correct |
23 |
Correct |
798 ms |
265028 KB |
Output is correct |
24 |
Correct |
728 ms |
265000 KB |
Output is correct |
25 |
Correct |
719 ms |
265028 KB |
Output is correct |
26 |
Correct |
731 ms |
265104 KB |
Output is correct |
27 |
Correct |
698 ms |
265092 KB |
Output is correct |
28 |
Correct |
678 ms |
265080 KB |
Output is correct |
29 |
Correct |
715 ms |
265000 KB |
Output is correct |
30 |
Correct |
739 ms |
265104 KB |
Output is correct |
31 |
Correct |
733 ms |
265028 KB |
Output is correct |
32 |
Correct |
694 ms |
265080 KB |
Output is correct |
33 |
Correct |
763 ms |
265140 KB |
Output is correct |
34 |
Correct |
711 ms |
265084 KB |
Output is correct |
35 |
Correct |
754 ms |
265092 KB |
Output is correct |
36 |
Correct |
669 ms |
265028 KB |
Output is correct |
37 |
Correct |
688 ms |
265048 KB |
Output is correct |
38 |
Correct |
710 ms |
265144 KB |
Output is correct |
39 |
Correct |
679 ms |
265168 KB |
Output is correct |
40 |
Correct |
724 ms |
269996 KB |
Output is correct |
41 |
Correct |
752 ms |
268156 KB |
Output is correct |
42 |
Correct |
750 ms |
265256 KB |
Output is correct |
43 |
Correct |
770 ms |
269900 KB |
Output is correct |
44 |
Correct |
714 ms |
266480 KB |
Output is correct |
45 |
Correct |
737 ms |
265812 KB |
Output is correct |
46 |
Correct |
723 ms |
265868 KB |
Output is correct |
47 |
Correct |
770 ms |
265676 KB |
Output is correct |
48 |
Correct |
712 ms |
268284 KB |
Output is correct |
49 |
Correct |
752 ms |
265824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
10644 KB |
Output is correct |
2 |
Correct |
27 ms |
10704 KB |
Output is correct |
3 |
Correct |
28 ms |
10676 KB |
Output is correct |
4 |
Correct |
26 ms |
10680 KB |
Output is correct |
5 |
Correct |
27 ms |
10648 KB |
Output is correct |
6 |
Correct |
28 ms |
10700 KB |
Output is correct |
7 |
Correct |
28 ms |
10828 KB |
Output is correct |
8 |
Correct |
28 ms |
10852 KB |
Output is correct |
9 |
Correct |
29 ms |
10776 KB |
Output is correct |
10 |
Correct |
108 ms |
17296 KB |
Output is correct |
11 |
Correct |
112 ms |
17220 KB |
Output is correct |
12 |
Correct |
93 ms |
17300 KB |
Output is correct |
13 |
Correct |
99 ms |
17296 KB |
Output is correct |
14 |
Correct |
93 ms |
17220 KB |
Output is correct |
15 |
Correct |
102 ms |
17256 KB |
Output is correct |
16 |
Correct |
110 ms |
18004 KB |
Output is correct |
17 |
Correct |
96 ms |
17452 KB |
Output is correct |
18 |
Correct |
97 ms |
17436 KB |
Output is correct |
19 |
Correct |
119 ms |
17480 KB |
Output is correct |
20 |
Correct |
117 ms |
17540 KB |
Output is correct |
21 |
Correct |
713 ms |
265072 KB |
Output is correct |
22 |
Correct |
687 ms |
265096 KB |
Output is correct |
23 |
Correct |
798 ms |
265028 KB |
Output is correct |
24 |
Correct |
728 ms |
265000 KB |
Output is correct |
25 |
Correct |
719 ms |
265028 KB |
Output is correct |
26 |
Correct |
731 ms |
265104 KB |
Output is correct |
27 |
Correct |
698 ms |
265092 KB |
Output is correct |
28 |
Correct |
678 ms |
265080 KB |
Output is correct |
29 |
Correct |
715 ms |
265000 KB |
Output is correct |
30 |
Correct |
739 ms |
265104 KB |
Output is correct |
31 |
Correct |
733 ms |
265028 KB |
Output is correct |
32 |
Correct |
694 ms |
265080 KB |
Output is correct |
33 |
Correct |
763 ms |
265140 KB |
Output is correct |
34 |
Correct |
711 ms |
265084 KB |
Output is correct |
35 |
Correct |
754 ms |
265092 KB |
Output is correct |
36 |
Correct |
669 ms |
265028 KB |
Output is correct |
37 |
Correct |
688 ms |
265048 KB |
Output is correct |
38 |
Correct |
710 ms |
265144 KB |
Output is correct |
39 |
Correct |
679 ms |
265168 KB |
Output is correct |
40 |
Correct |
724 ms |
269996 KB |
Output is correct |
41 |
Correct |
752 ms |
268156 KB |
Output is correct |
42 |
Correct |
750 ms |
265256 KB |
Output is correct |
43 |
Correct |
770 ms |
269900 KB |
Output is correct |
44 |
Correct |
714 ms |
266480 KB |
Output is correct |
45 |
Correct |
737 ms |
265812 KB |
Output is correct |
46 |
Correct |
723 ms |
265868 KB |
Output is correct |
47 |
Correct |
770 ms |
265676 KB |
Output is correct |
48 |
Correct |
712 ms |
268284 KB |
Output is correct |
49 |
Correct |
752 ms |
265824 KB |
Output is correct |
50 |
Execution timed out |
1108 ms |
205412 KB |
Time limit exceeded |
51 |
Halted |
0 ms |
0 KB |
- |