Submission #41371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41371	2018-02-17T05:55:16 Z	RockyB	Bali Sculptures (APIO15_sculpture)	C++14	46 / 100	1000 ms	218860 KB

sculpture

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)2000 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, A, B;
int a[N];

ll ans = linf;
map <ll, bool> dp[N][N];
void rec(int v = 1, int done = 0, ll cost = 0) {
	if (done > B) return;
	if (dp[v][done].count(cost)) return;
	dp[v][done][cost] = 1;
	if (v > n) {
		if (A <= done && done <= B) {
			ans = min(ans, cost);
		}
		return;
	}
	ll sum = 0;
	for (int i = v; i <= n; i++) {
		sum += a[i];
		rec(i + 1, done + 1, cost | sum);
	}
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	rec();
	cout << ans;
	ioi
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	189432 KB	Output is correct
2	Correct	160 ms	189664 KB	Output is correct
3	Correct	161 ms	189664 KB	Output is correct
4	Correct	156 ms	189664 KB	Output is correct
5	Correct	161 ms	189664 KB	Output is correct
6	Correct	165 ms	189772 KB	Output is correct
7	Correct	163 ms	189828 KB	Output is correct
8	Correct	160 ms	189828 KB	Output is correct
9	Correct	173 ms	189828 KB	Output is correct
10	Correct	160 ms	189828 KB	Output is correct
11	Correct	161 ms	189828 KB	Output is correct
12	Correct	166 ms	189844 KB	Output is correct
13	Correct	165 ms	189844 KB	Output is correct
14	Correct	167 ms	189844 KB	Output is correct
15	Correct	168 ms	189844 KB	Output is correct
16	Correct	171 ms	189844 KB	Output is correct
17	Correct	162 ms	189844 KB	Output is correct
18	Correct	161 ms	189844 KB	Output is correct
19	Correct	163 ms	189844 KB	Output is correct
20	Correct	162 ms	189932 KB	Output is correct
21	Correct	178 ms	189932 KB	Output is correct
22	Correct	166 ms	189932 KB	Output is correct
23	Correct	165 ms	189932 KB	Output is correct
24	Correct	168 ms	189932 KB	Output is correct
25	Correct	174 ms	189932 KB	Output is correct
26	Correct	162 ms	189932 KB	Output is correct
27	Correct	166 ms	189932 KB	Output is correct
28	Correct	165 ms	189932 KB	Output is correct
29	Correct	163 ms	190000 KB	Output is correct
30	Correct	163 ms	190000 KB	Output is correct
31	Correct	166 ms	190000 KB	Output is correct
32	Correct	165 ms	190000 KB	Output is correct
33	Correct	168 ms	190000 KB	Output is correct
34	Correct	171 ms	190000 KB	Output is correct
35	Correct	162 ms	190000 KB	Output is correct
36	Correct	168 ms	190000 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	190000 KB	Output is correct
2	Correct	168 ms	190000 KB	Output is correct
3	Correct	156 ms	190000 KB	Output is correct
4	Correct	157 ms	190000 KB	Output is correct
5	Correct	157 ms	190000 KB	Output is correct
6	Correct	159 ms	190000 KB	Output is correct
7	Correct	156 ms	190000 KB	Output is correct
8	Correct	165 ms	190000 KB	Output is correct
9	Correct	160 ms	190000 KB	Output is correct
10	Correct	155 ms	190000 KB	Output is correct
11	Correct	157 ms	190000 KB	Output is correct
12	Correct	158 ms	190000 KB	Output is correct
13	Correct	157 ms	190000 KB	Output is correct
14	Correct	160 ms	190000 KB	Output is correct
15	Correct	157 ms	190000 KB	Output is correct
16	Correct	160 ms	190000 KB	Output is correct
17	Correct	164 ms	190000 KB	Output is correct
18	Correct	157 ms	190000 KB	Output is correct
19	Correct	158 ms	190000 KB	Output is correct
20	Correct	164 ms	190000 KB	Output is correct
21	Correct	158 ms	190000 KB	Output is correct
22	Correct	157 ms	190000 KB	Output is correct
23	Correct	158 ms	190000 KB	Output is correct
24	Correct	159 ms	190000 KB	Output is correct
25	Correct	163 ms	190000 KB	Output is correct
26	Correct	173 ms	190000 KB	Output is correct
27	Correct	182 ms	190000 KB	Output is correct
28	Correct	163 ms	190000 KB	Output is correct
29	Correct	163 ms	190132 KB	Output is correct
30	Correct	168 ms	190444 KB	Output is correct
31	Correct	182 ms	191316 KB	Output is correct
32	Correct	166 ms	191316 KB	Output is correct
33	Correct	156 ms	191316 KB	Output is correct
34	Correct	168 ms	191316 KB	Output is correct
35	Correct	176 ms	191316 KB	Output is correct
36	Correct	184 ms	191316 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	191316 KB	Output is correct
2	Correct	155 ms	191316 KB	Output is correct
3	Correct	159 ms	191316 KB	Output is correct
4	Correct	160 ms	191316 KB	Output is correct
5	Correct	172 ms	191316 KB	Output is correct
6	Correct	159 ms	191316 KB	Output is correct
7	Correct	157 ms	191316 KB	Output is correct
8	Correct	156 ms	191316 KB	Output is correct
9	Correct	172 ms	191316 KB	Output is correct
10	Correct	180 ms	191316 KB	Output is correct
11	Correct	155 ms	191316 KB	Output is correct
12	Correct	157 ms	191316 KB	Output is correct
13	Correct	160 ms	191316 KB	Output is correct
14	Correct	160 ms	191316 KB	Output is correct
15	Correct	159 ms	191316 KB	Output is correct
16	Correct	172 ms	191316 KB	Output is correct
17	Correct	164 ms	191316 KB	Output is correct
18	Correct	181 ms	191316 KB	Output is correct
19	Correct	166 ms	191316 KB	Output is correct
20	Correct	172 ms	191316 KB	Output is correct
21	Correct	173 ms	191316 KB	Output is correct
22	Correct	178 ms	191316 KB	Output is correct
23	Correct	170 ms	191316 KB	Output is correct
24	Correct	182 ms	191652 KB	Output is correct
25	Correct	203 ms	191728 KB	Output is correct
26	Correct	323 ms	195948 KB	Output is correct
27	Correct	447 ms	200636 KB	Output is correct
28	Correct	610 ms	204416 KB	Output is correct
29	Correct	442 ms	204416 KB	Output is correct
30	Correct	158 ms	204416 KB	Output is correct
31	Correct	727 ms	205784 KB	Output is correct
32	Correct	773 ms	206780 KB	Output is correct

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	206780 KB	Output is correct
2	Correct	158 ms	206780 KB	Output is correct
3	Correct	158 ms	206780 KB	Output is correct
4	Correct	158 ms	206780 KB	Output is correct
5	Correct	158 ms	206780 KB	Output is correct
6	Correct	165 ms	206780 KB	Output is correct
7	Correct	159 ms	206780 KB	Output is correct
8	Correct	163 ms	206780 KB	Output is correct
9	Correct	156 ms	206780 KB	Output is correct
10	Correct	170 ms	206780 KB	Output is correct
11	Correct	168 ms	206780 KB	Output is correct
12	Correct	171 ms	206780 KB	Output is correct
13	Correct	160 ms	206780 KB	Output is correct
14	Correct	166 ms	206780 KB	Output is correct
15	Correct	167 ms	206780 KB	Output is correct
16	Correct	165 ms	206780 KB	Output is correct
17	Correct	162 ms	206780 KB	Output is correct
18	Correct	177 ms	206780 KB	Output is correct
19	Correct	166 ms	206780 KB	Output is correct
20	Correct	159 ms	206780 KB	Output is correct
21	Correct	156 ms	206780 KB	Output is correct
22	Correct	161 ms	206780 KB	Output is correct
23	Correct	158 ms	206780 KB	Output is correct
24	Correct	157 ms	206780 KB	Output is correct
25	Correct	176 ms	206780 KB	Output is correct
26	Correct	165 ms	206780 KB	Output is correct
27	Correct	156 ms	206780 KB	Output is correct
28	Correct	159 ms	206780 KB	Output is correct
29	Correct	173 ms	206780 KB	Output is correct
30	Correct	165 ms	206780 KB	Output is correct
31	Correct	157 ms	206780 KB	Output is correct
32	Correct	177 ms	206780 KB	Output is correct
33	Correct	163 ms	206780 KB	Output is correct
34	Correct	167 ms	206780 KB	Output is correct
35	Correct	160 ms	206780 KB	Output is correct
36	Correct	158 ms	206780 KB	Output is correct
37	Correct	158 ms	206780 KB	Output is correct
38	Correct	161 ms	206780 KB	Output is correct
39	Correct	162 ms	206780 KB	Output is correct
40	Correct	173 ms	206780 KB	Output is correct
41	Correct	184 ms	206780 KB	Output is correct
42	Correct	170 ms	206780 KB	Output is correct
43	Correct	159 ms	206780 KB	Output is correct
44	Correct	189 ms	206780 KB	Output is correct
45	Correct	187 ms	206780 KB	Output is correct
46	Correct	165 ms	206780 KB	Output is correct
47	Correct	186 ms	206780 KB	Output is correct
48	Correct	201 ms	206780 KB	Output is correct
49	Correct	312 ms	206780 KB	Output is correct
50	Correct	444 ms	206780 KB	Output is correct
51	Correct	635 ms	206780 KB	Output is correct
52	Correct	438 ms	206780 KB	Output is correct
53	Correct	156 ms	206780 KB	Output is correct
54	Correct	734 ms	206780 KB	Output is correct
55	Correct	790 ms	206780 KB	Output is correct
56	Execution timed out	1077 ms	218524 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	218524 KB	Output is correct
2	Correct	158 ms	218524 KB	Output is correct
3	Correct	156 ms	218524 KB	Output is correct
4	Correct	162 ms	218524 KB	Output is correct
5	Correct	161 ms	218524 KB	Output is correct
6	Correct	160 ms	218524 KB	Output is correct
7	Correct	158 ms	218524 KB	Output is correct
8	Correct	173 ms	218524 KB	Output is correct
9	Correct	160 ms	218524 KB	Output is correct
10	Correct	166 ms	218524 KB	Output is correct
11	Correct	170 ms	218524 KB	Output is correct
12	Correct	158 ms	218524 KB	Output is correct
13	Correct	165 ms	218524 KB	Output is correct
14	Correct	167 ms	218524 KB	Output is correct
15	Correct	162 ms	218524 KB	Output is correct
16	Correct	162 ms	218524 KB	Output is correct
17	Correct	160 ms	218524 KB	Output is correct
18	Correct	159 ms	218524 KB	Output is correct
19	Correct	165 ms	218524 KB	Output is correct
20	Correct	165 ms	218524 KB	Output is correct
21	Correct	157 ms	218524 KB	Output is correct
22	Correct	158 ms	218524 KB	Output is correct
23	Correct	163 ms	218524 KB	Output is correct
24	Correct	161 ms	218524 KB	Output is correct
25	Correct	157 ms	218524 KB	Output is correct
26	Correct	160 ms	218524 KB	Output is correct
27	Correct	171 ms	218524 KB	Output is correct
28	Correct	182 ms	218524 KB	Output is correct
29	Correct	168 ms	218524 KB	Output is correct
30	Correct	159 ms	218524 KB	Output is correct
31	Correct	173 ms	218524 KB	Output is correct
32	Correct	170 ms	218524 KB	Output is correct
33	Correct	174 ms	218524 KB	Output is correct
34	Correct	183 ms	218524 KB	Output is correct
35	Correct	207 ms	218524 KB	Output is correct
36	Correct	343 ms	218524 KB	Output is correct
37	Correct	491 ms	218524 KB	Output is correct
38	Correct	631 ms	218524 KB	Output is correct
39	Correct	460 ms	218524 KB	Output is correct
40	Correct	162 ms	218524 KB	Output is correct
41	Correct	755 ms	218524 KB	Output is correct
42	Correct	786 ms	218524 KB	Output is correct
43	Execution timed out	1101 ms	218860 KB	Time limit exceeded
44	Halted	0 ms	0 KB	-