Submission #671932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671932	2022-12-14T09:41:15 Z	Dan4Life	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	552 ms	312 KB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = (int)1e2+10;
const ll LINF = (ll)1e18;
int n, A, B;
ll a[maxn], pre[maxn]; ll ans=LINF;

bool needs(ll mask, int bit){
	bool dp[110][110]; bool ok=1; 
	//if possible to make first i element, j groups, no sum has mask turned on 
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= B; j++)
			dp[i][j]=false;
	dp[0][0]=true;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= B; j++){
			for(int k = 0; k<i; k++){
				ll sum = pre[i]-pre[k]; bool skip=false;
				for(int l = bit+1; l < 40; l++){
					if(mask&(1ll<<l)) continue;
					if(sum&(1ll<<l)) skip=true;
				}
				if(sum&(1ll<<bit) or skip) continue;
				dp[i][j] |= dp[k][j-1];
			}
		}
	}
	for(int i = A; i <= B; i++) if(dp[n][i]) ok=0;
	return ok;
}

int32_t main() {
	cin >> n >> A >> B;
	for(int i = 0; i < n; i++) cin >> a[i], pre[i+1]=pre[i]+a[i];
	if(n<=100){
		ans = 0;
		for(int i = 40; i >= 0; i--)
			ans|=needs(ans|(1ll<<i),i)*(1ll<<i);
	}
	else{

	}
	cout << ans;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	2 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	3 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	2 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	2 ms	212 KB	Output is correct
26	Correct	3 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	2 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	4 ms	308 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	3 ms	212 KB	Output is correct
34	Correct	4 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	5 ms	212 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	2 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	2 ms	308 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	3 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	2 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	2 ms	212 KB	Output is correct
26	Correct	2 ms	212 KB	Output is correct
27	Correct	5 ms	308 KB	Output is correct
28	Correct	10 ms	212 KB	Output is correct
29	Correct	3 ms	212 KB	Output is correct
30	Correct	13 ms	212 KB	Output is correct
31	Correct	34 ms	212 KB	Output is correct
32	Correct	22 ms	212 KB	Output is correct
33	Correct	3 ms	212 KB	Output is correct
34	Correct	20 ms	304 KB	Output is correct
35	Correct	17 ms	212 KB	Output is correct
36	Correct	10 ms	312 KB	Output is correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	2 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	5 ms	212 KB	Output is correct
14	Correct	8 ms	304 KB	Output is correct
15	Correct	3 ms	212 KB	Output is correct
16	Correct	3 ms	304 KB	Output is correct
17	Correct	13 ms	308 KB	Output is correct
18	Correct	21 ms	304 KB	Output is correct
19	Correct	30 ms	212 KB	Output is correct
20	Correct	2 ms	212 KB	Output is correct
21	Correct	19 ms	312 KB	Output is correct
22	Correct	16 ms	304 KB	Output is correct
23	Correct	10 ms	212 KB	Output is correct
24	Correct	20 ms	212 KB	Output is correct
25	Correct	19 ms	212 KB	Output is correct
26	Correct	52 ms	212 KB	Output is correct
27	Correct	185 ms	284 KB	Output is correct
28	Correct	363 ms	292 KB	Output is correct
29	Correct	403 ms	284 KB	Output is correct
30	Correct	13 ms	308 KB	Output is correct
31	Correct	173 ms	292 KB	Output is correct
32	Correct	284 ms	292 KB	Output is correct

Subtask #4
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	2 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	3 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	3 ms	212 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	4 ms	212 KB	Output is correct
19	Correct	2 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	2 ms	212 KB	Output is correct
25	Correct	2 ms	212 KB	Output is correct
26	Correct	3 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	2 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	2 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	4 ms	212 KB	Output is correct
34	Correct	6 ms	212 KB	Output is correct
35	Correct	2 ms	212 KB	Output is correct
36	Correct	6 ms	212 KB	Output is correct
37	Correct	4 ms	304 KB	Output is correct
38	Correct	3 ms	212 KB	Output is correct
39	Correct	3 ms	212 KB	Output is correct
40	Correct	13 ms	304 KB	Output is correct
41	Correct	19 ms	212 KB	Output is correct
42	Correct	20 ms	308 KB	Output is correct
43	Correct	3 ms	212 KB	Output is correct
44	Correct	20 ms	308 KB	Output is correct
45	Correct	17 ms	304 KB	Output is correct
46	Correct	10 ms	308 KB	Output is correct
47	Correct	19 ms	212 KB	Output is correct
48	Correct	16 ms	308 KB	Output is correct
49	Correct	54 ms	284 KB	Output is correct
50	Correct	168 ms	212 KB	Output is correct
51	Correct	384 ms	288 KB	Output is correct
52	Correct	365 ms	284 KB	Output is correct
53	Correct	7 ms	212 KB	Output is correct
54	Correct	172 ms	292 KB	Output is correct
55	Correct	278 ms	212 KB	Output is correct
56	Correct	26 ms	308 KB	Output is correct
57	Correct	70 ms	212 KB	Output is correct
58	Correct	213 ms	288 KB	Output is correct
59	Correct	456 ms	284 KB	Output is correct
60	Correct	431 ms	288 KB	Output is correct
61	Correct	5 ms	212 KB	Output is correct
62	Correct	474 ms	284 KB	Output is correct
63	Correct	444 ms	284 KB	Output is correct
64	Correct	290 ms	288 KB	Output is correct
65	Correct	26 ms	212 KB	Output is correct
66	Correct	20 ms	308 KB	Output is correct
67	Correct	73 ms	288 KB	Output is correct
68	Correct	237 ms	292 KB	Output is correct
69	Correct	552 ms	288 KB	Output is correct
70	Correct	458 ms	288 KB	Output is correct
71	Correct	10 ms	212 KB	Output is correct
72	Correct	496 ms	292 KB	Output is correct
73	Correct	379 ms	288 KB	Output is correct
74	Correct	332 ms	284 KB	Output is correct

Subtask #5
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	216 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	220 KB	Output is correct
5	Correct	1 ms	216 KB	Output is correct
6	Correct	2 ms	212 KB	Output is correct
7	Correct	1 ms	216 KB	Output is correct
8	Correct	1 ms	224 KB	Output is correct
9	Correct	2 ms	224 KB	Output is correct
10	Correct	1 ms	220 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	4 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	2 ms	212 KB	Output is correct
17	Correct	1 ms	256 KB	Output is correct
18	Correct	2 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	3 ms	212 KB	Output is correct
21	Correct	4 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	5 ms	212 KB	Output is correct
24	Correct	6 ms	212 KB	Output is correct
25	Correct	4 ms	212 KB	Output is correct
26	Correct	6 ms	212 KB	Output is correct
27	Correct	22 ms	312 KB	Output is correct
28	Correct	18 ms	304 KB	Output is correct
29	Correct	19 ms	212 KB	Output is correct
30	Correct	2 ms	212 KB	Output is correct
31	Correct	21 ms	212 KB	Output is correct
32	Correct	21 ms	308 KB	Output is correct
33	Correct	11 ms	308 KB	Output is correct
34	Correct	23 ms	212 KB	Output is correct
35	Correct	28 ms	212 KB	Output is correct
36	Correct	54 ms	284 KB	Output is correct
37	Correct	164 ms	292 KB	Output is correct
38	Correct	377 ms	284 KB	Output is correct
39	Correct	351 ms	212 KB	Output is correct
40	Correct	4 ms	212 KB	Output is correct
41	Correct	171 ms	284 KB	Output is correct
42	Correct	266 ms	212 KB	Output is correct
43	Correct	23 ms	212 KB	Output is correct
44	Correct	65 ms	288 KB	Output is correct
45	Correct	206 ms	296 KB	Output is correct
46	Correct	429 ms	304 KB	Output is correct
47	Correct	400 ms	292 KB	Output is correct
48	Correct	5 ms	304 KB	Output is correct
49	Correct	416 ms	292 KB	Output is correct
50	Correct	392 ms	292 KB	Output is correct
51	Incorrect	1 ms	212 KB	Output isn't correct
52	Halted	0 ms	0 KB	-

Submission #671932

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 25.0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
25.0 / 25.0

Subtask #5
0 / 29.0