Submission #1002835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1002835	2024-06-19T20:25:28 Z	PagodePaiva	Cigle (COI21_cigle)	C++17	48 / 100	263 ms	7384 KB

cigle

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 510;
const int inf = 1e9;
const int M = 1e7;

int n;
int dp[N][N][2];
int v[N];
int mark[M];

const int debug = 0;

int main(){
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> v[i];
	for(int i = 1;i <= n;i++){
		dp[1][i][0] = 0;
		dp[1][i][1] = -inf;
	}		
	for(int i = 1;i < n;i++){
		for(int j = i;j < n;j++){
			//
			int t = 0;
			int l = i, r = j;
			vector <int> bons;
			t += v[i];
			for(int k = i+1;k <= j;k++){
				bons.push_back(t);
				mark[t] = 1;
				t += v[k];
			}
			int res = 0;
			dp[r+1][r+1][1] = max(dp[r+1][r+1][1], dp[l][r][0]);
			t -= v[r+1];
			for(int k = j+2;k <= n;k++){
				if(t >= 0 and mark[t] == 1){
					res++;
				}
				t -= v[k];
				dp[r+1][k][1] = max(dp[r+1][k][1], dp[l][r][0]+res);
			}
			for(auto x : bons){
				mark[x] = 0;
			}
			bons.clear();
			//
			t = 0;
			t += v[r];
			for(int k = r-1;k >= i;k--){
				bons.push_back(t);
				mark[t] = 1;
				t += v[k];
			}
			if(debug and l == 3 and r == 4){
				for(auto x : bons){
					cout << x << ' ';
				}
				cout << endl;
			}
			res = 0;
			t = v[r+1];
			if(debug and l == 3 and r == 4) cout << t << ' ';
			dp[r+1][r+1][0] = max(dp[r+1][r+1][0], dp[l][r][1] + res);
			for(int k = r+2;k <= n;k++){
				if(t < M){
					if(mark[t] == 1){
						res++;
					}
				}
				t += v[k];
				if(debug and l == 3 and r == 4 and k == 6){
					cout << res << endl;
				}
				dp[r+1][k][0] = max(dp[r+1][k][0], dp[l][r][1]+res);
			}
			for(auto x : bons) mark[x] = 0;
				bons.clear();
		}
	}
	int res = 0;
	for(int i = 0;i <= n;i++){
		res = max(res, dp[i][n][0]);
		res = max(res, dp[i][n][1]);
	}
	cout << res << endl;
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	604 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	604 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	3 ms	776 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	3 ms	1464 KB	Output is correct
17	Correct	2 ms	860 KB	Output is correct
18	Correct	3 ms	1020 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	2 ms	860 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	2212 KB	Output is correct
2	Correct	189 ms	2396 KB	Output is correct
3	Correct	192 ms	2396 KB	Output is correct
4	Correct	201 ms	2448 KB	Output is correct
5	Correct	197 ms	2256 KB	Output is correct
6	Correct	262 ms	2396 KB	Output is correct
7	Correct	263 ms	2396 KB	Output is correct
8	Correct	255 ms	2644 KB	Output is correct
9	Correct	254 ms	2432 KB	Output is correct
10	Correct	243 ms	2436 KB	Output is correct
11	Correct	256 ms	2396 KB	Output is correct
12	Correct	211 ms	2396 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	604 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	3 ms	776 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	3 ms	1464 KB	Output is correct
17	Correct	2 ms	860 KB	Output is correct
18	Correct	3 ms	1020 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	2 ms	860 KB	Output is correct
21	Correct	202 ms	2212 KB	Output is correct
22	Correct	189 ms	2396 KB	Output is correct
23	Correct	192 ms	2396 KB	Output is correct
24	Correct	201 ms	2448 KB	Output is correct
25	Correct	197 ms	2256 KB	Output is correct
26	Correct	262 ms	2396 KB	Output is correct
27	Correct	263 ms	2396 KB	Output is correct
28	Correct	255 ms	2644 KB	Output is correct
29	Correct	254 ms	2432 KB	Output is correct
30	Correct	243 ms	2436 KB	Output is correct
31	Correct	256 ms	2396 KB	Output is correct
32	Correct	211 ms	2396 KB	Output is correct
33	Correct	194 ms	2436 KB	Output is correct
34	Correct	190 ms	2648 KB	Output is correct
35	Correct	207 ms	2396 KB	Output is correct
36	Correct	197 ms	2392 KB	Output is correct
37	Correct	249 ms	2392 KB	Output is correct
38	Correct	263 ms	2448 KB	Output is correct
39	Correct	225 ms	2396 KB	Output is correct
40	Correct	218 ms	7384 KB	Output is correct
41	Correct	242 ms	5212 KB	Output is correct
42	Correct	201 ms	2392 KB	Output is correct
43	Correct	220 ms	7256 KB	Output is correct
44	Correct	208 ms	3928 KB	Output is correct
45	Correct	195 ms	3164 KB	Output is correct
46	Correct	214 ms	3160 KB	Output is correct
47	Correct	196 ms	2904 KB	Output is correct
48	Correct	210 ms	5672 KB	Output is correct
49	Correct	194 ms	3160 KB	Output is correct

Subtask #5
0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	0 ms	604 KB	Output is correct
9	Correct	0 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	3 ms	776 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	3 ms	1464 KB	Output is correct
17	Correct	2 ms	860 KB	Output is correct
18	Correct	3 ms	1020 KB	Output is correct
19	Correct	2 ms	860 KB	Output is correct
20	Correct	2 ms	860 KB	Output is correct
21	Correct	202 ms	2212 KB	Output is correct
22	Correct	189 ms	2396 KB	Output is correct
23	Correct	192 ms	2396 KB	Output is correct
24	Correct	201 ms	2448 KB	Output is correct
25	Correct	197 ms	2256 KB	Output is correct
26	Correct	262 ms	2396 KB	Output is correct
27	Correct	263 ms	2396 KB	Output is correct
28	Correct	255 ms	2644 KB	Output is correct
29	Correct	254 ms	2432 KB	Output is correct
30	Correct	243 ms	2436 KB	Output is correct
31	Correct	256 ms	2396 KB	Output is correct
32	Correct	211 ms	2396 KB	Output is correct
33	Correct	194 ms	2436 KB	Output is correct
34	Correct	190 ms	2648 KB	Output is correct
35	Correct	207 ms	2396 KB	Output is correct
36	Correct	197 ms	2392 KB	Output is correct
37	Correct	249 ms	2392 KB	Output is correct
38	Correct	263 ms	2448 KB	Output is correct
39	Correct	225 ms	2396 KB	Output is correct
40	Correct	218 ms	7384 KB	Output is correct
41	Correct	242 ms	5212 KB	Output is correct
42	Correct	201 ms	2392 KB	Output is correct
43	Correct	220 ms	7256 KB	Output is correct
44	Correct	208 ms	3928 KB	Output is correct
45	Correct	195 ms	3164 KB	Output is correct
46	Correct	214 ms	3160 KB	Output is correct
47	Correct	196 ms	2904 KB	Output is correct
48	Correct	210 ms	5672 KB	Output is correct
49	Correct	194 ms	3160 KB	Output is correct
50	Runtime error	2 ms	600 KB	Execution killed with signal 11
51	Halted	0 ms	0 KB	-

Submission #1002835

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 11.0 / 11.0

Subtask #3 13.0 / 13.0

Subtask #4 15.0 / 15.0

Subtask #5 0 / 52.0

Subtask #1
9.0 / 9.0

Subtask #2
11.0 / 11.0

Subtask #3
13.0 / 13.0

Subtask #4
15.0 / 15.0

Subtask #5
0 / 52.0