Submission #766512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
766512	2023-06-25T18:01:33 Z	1ne	Bali Sculptures (APIO15_sculpture)	C++14	9 / 100	1000 ms	59088 KB

sculpture

#include<bits/stdc++.h>
using namespace std; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,a,b;cin>>n>>a>>b;
	vector<long long>arr(n);
	for (long long i = 0;i<n;++i){
		cin>>arr[i];
	}
	vector<long long>pref(n + 1,0);
	for (int i = 0;i<n;++i){
		pref[i + 1] = pref[i] + arr[i];
	}
	auto query = [&](int u,int v){
	  return pref[v + 1] - pref[u];
	};
	long long cur = 0;
	auto check = [&](long long v){
		vector<vector<int>>dp(n + 1);
		dp[0].push_back(0);
		for (int i = 0;i<n;++i){
			for (int x = i;x<n;++x){
				if (query(i,x) & v){
					continue;
				}
				for (auto y:dp[i]){
					if (y + 1 <= b)
						dp[x + 1].push_back(y + 1);
				}
			}
		}
		for (auto x:dp[n]){
			if (x >= a && x <= b)return 1;
		}
		return 0;
	};
	long long ans = 0;
	for (long long i = 43;i>=0;--i){
		if (check((cur ^ (1LL<<i)))){
			cur ^= (1LL<<i);
		}
		else{
			ans ^= (1LL<<i);
		}	
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1

9.0 / 9.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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	528 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	116 ms	7944 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	3 ms	540 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	19 ms	1396 KB	Output is correct
22	Correct	19 ms	1504 KB	Output is correct
23	Correct	19 ms	1556 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	24 ms	1540 KB	Output is correct
26	Correct	137 ms	7784 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	6 ms	1420 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	46 ms	7748 KB	Output is correct
34	Correct	45 ms	7920 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	69 ms	7936 KB	Output is correct

Subtask #2

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 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	0 ms	212 KB	Output is correct
6	Correct	3 ms	528 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	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	110 ms	7928 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 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	0 ms	212 KB	Output is correct
19	Correct	3 ms	528 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	19 ms	1540 KB	Output is correct
22	Correct	19 ms	1504 KB	Output is correct
23	Correct	18 ms	1400 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	19 ms	1524 KB	Output is correct
26	Correct	104 ms	7748 KB	Output is correct
27	Correct	236 ms	15220 KB	Output is correct
28	Execution timed out	1069 ms	59056 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.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	3 ms	528 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	113 ms	7892 KB	Output is correct
14	Correct	257 ms	15244 KB	Output is correct
15	Execution timed out	1081 ms	59088 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #4

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	0 ms	212 KB	Output is correct
6	Correct	3 ms	668 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	106 ms	8032 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	284 KB	Output is correct
19	Correct	4 ms	528 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	19 ms	1404 KB	Output is correct
22	Correct	18 ms	1388 KB	Output is correct
23	Correct	18 ms	1512 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	19 ms	1504 KB	Output is correct
26	Correct	106 ms	7720 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	6 ms	1396 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	45 ms	7768 KB	Output is correct
34	Correct	48 ms	7964 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	67 ms	7996 KB	Output is correct
37	Correct	242 ms	15252 KB	Output is correct
38	Execution timed out	1080 ms	59076 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.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	1 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	3 ms	528 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 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	340 KB	Output is correct
13	Correct	122 ms	7940 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	6 ms	1396 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	46 ms	7680 KB	Output is correct
21	Correct	40 ms	7940 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	69 ms	7912 KB	Output is correct
24	Correct	247 ms	15244 KB	Output is correct
25	Execution timed out	1079 ms	59004 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-