Submission #104588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104588	2019-04-08T09:48:12 Z	YottaByte	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	193 ms	16964 KB

sculpture

#include <iostream>
#include <string.h>
using namespace std;

#define int long long
#define pc __builtin_popcount

const int N = 21, inf = 1e18;

int n, a, b, ans = inf, ar[N], dp[1 << N];

void calc(int mask) {
	if(a <= pc(mask) + 1 && pc(mask) + 1 <= b) {
		int sum = 0, temp = 0;
		for(int i = 0; i < n; i++) {
			sum += ar[i];
			if(mask >> i & 1) {
				temp |= sum;
				sum = 0;
			}
		}
		
		temp |= sum;
		dp[mask] = temp;
		
		ans = min(ans, dp[mask]);
	}
}

main() {
	cin >> n >> a >> b;
	
	for(int i = 0; i < n; i++) {
		cin >> ar[i];
	}
	
	for(int i = 0; i < (1 << N); i++) {
		calc(i);
	}
	
	cout << ans << endl;
}

Compilation message

sculpture.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	640 KB	Output is correct
2	Correct	17 ms	1664 KB	Output is correct
3	Correct	14 ms	384 KB	Output is correct
4	Correct	20 ms	640 KB	Output is correct
5	Correct	20 ms	384 KB	Output is correct
6	Correct	149 ms	16732 KB	Output is correct
7	Correct	14 ms	640 KB	Output is correct
8	Correct	14 ms	640 KB	Output is correct
9	Correct	20 ms	768 KB	Output is correct
10	Correct	13 ms	640 KB	Output is correct
11	Correct	18 ms	384 KB	Output is correct
12	Correct	15 ms	808 KB	Output is correct
13	Correct	159 ms	16760 KB	Output is correct
14	Correct	14 ms	640 KB	Output is correct
15	Incorrect	26 ms	6648 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	640 KB	Output is correct
2	Correct	19 ms	1536 KB	Output is correct
3	Correct	20 ms	256 KB	Output is correct
4	Correct	13 ms	640 KB	Output is correct
5	Correct	13 ms	384 KB	Output is correct
6	Correct	149 ms	16760 KB	Output is correct
7	Correct	14 ms	640 KB	Output is correct
8	Correct	13 ms	640 KB	Output is correct
9	Correct	15 ms	640 KB	Output is correct
10	Correct	18 ms	640 KB	Output is correct
11	Correct	21 ms	256 KB	Output is correct
12	Correct	18 ms	640 KB	Output is correct
13	Correct	177 ms	16888 KB	Output is correct
14	Correct	20 ms	640 KB	Output is correct
15	Incorrect	20 ms	6656 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	640 KB	Output is correct
2	Correct	15 ms	1536 KB	Output is correct
3	Correct	15 ms	256 KB	Output is correct
4	Correct	14 ms	640 KB	Output is correct
5	Correct	14 ms	256 KB	Output is correct
6	Correct	166 ms	16740 KB	Output is correct
7	Correct	15 ms	640 KB	Output is correct
8	Correct	23 ms	640 KB	Output is correct
9	Correct	22 ms	640 KB	Output is correct
10	Correct	20 ms	640 KB	Output is correct
11	Correct	17 ms	384 KB	Output is correct
12	Correct	15 ms	640 KB	Output is correct
13	Correct	176 ms	16760 KB	Output is correct
14	Correct	165 ms	16760 KB	Output is correct
15	Incorrect	32 ms	13560 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	768 KB	Output is correct
2	Correct	15 ms	1664 KB	Output is correct
3	Correct	14 ms	384 KB	Output is correct
4	Correct	17 ms	640 KB	Output is correct
5	Correct	13 ms	384 KB	Output is correct
6	Correct	151 ms	16748 KB	Output is correct
7	Correct	17 ms	640 KB	Output is correct
8	Correct	14 ms	640 KB	Output is correct
9	Correct	16 ms	640 KB	Output is correct
10	Correct	15 ms	688 KB	Output is correct
11	Correct	19 ms	252 KB	Output is correct
12	Correct	14 ms	640 KB	Output is correct
13	Correct	193 ms	16760 KB	Output is correct
14	Correct	20 ms	640 KB	Output is correct
15	Incorrect	23 ms	6784 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	612 KB	Output is correct
2	Correct	15 ms	1484 KB	Output is correct
3	Correct	17 ms	384 KB	Output is correct
4	Correct	15 ms	768 KB	Output is correct
5	Correct	14 ms	384 KB	Output is correct
6	Correct	144 ms	16680 KB	Output is correct
7	Correct	13 ms	640 KB	Output is correct
8	Correct	13 ms	640 KB	Output is correct
9	Correct	14 ms	712 KB	Output is correct
10	Correct	22 ms	640 KB	Output is correct
11	Correct	15 ms	384 KB	Output is correct
12	Correct	13 ms	640 KB	Output is correct
13	Correct	160 ms	16964 KB	Output is correct
14	Correct	14 ms	640 KB	Output is correct
15	Correct	15 ms	1588 KB	Output is correct
16	Correct	121 ms	16740 KB	Output is correct
17	Correct	17 ms	640 KB	Output is correct
18	Correct	32 ms	10360 KB	Output is correct
19	Correct	15 ms	384 KB	Output is correct
20	Correct	137 ms	16740 KB	Output is correct
21	Correct	159 ms	16760 KB	Output is correct
22	Correct	13 ms	640 KB	Output is correct
23	Correct	164 ms	16712 KB	Output is correct
24	Correct	170 ms	16800 KB	Output is correct
25	Incorrect	33 ms	13560 KB	Output isn't correct
26	Halted	0 ms	0 KB	-