Submission #104581

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104581	2019-04-08T08:56:10 Z	YottaByte	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	438 ms	16888 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(dp[mask] != -1) {
		return;
	}
	
	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]);
	}
	
	int st = 0;
	for(int i = n - 1; i > 0; i--) {
		if(mask >> i & 1) {
			st = i + 1;
			break;
		}
	}
	
	for(int i = st; i < n; i++) {
		if(mask >> i & 1); else {
			calc(1 << i | mask);
		}
	}
}

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

Compilation message

sculpture.cpp:48: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	18 ms	16768 KB	Output is correct
2	Correct	16 ms	16768 KB	Output is correct
3	Correct	16 ms	16768 KB	Output is correct
4	Correct	15 ms	16740 KB	Output is correct
5	Correct	16 ms	16768 KB	Output is correct
6	Correct	21 ms	16768 KB	Output is correct
7	Correct	18 ms	16768 KB	Output is correct
8	Correct	87 ms	16768 KB	Output is correct
9	Correct	81 ms	16768 KB	Output is correct
10	Correct	84 ms	16772 KB	Output is correct
11	Correct	84 ms	16768 KB	Output is correct
12	Correct	80 ms	16768 KB	Output is correct
13	Correct	180 ms	16768 KB	Output is correct
14	Correct	17 ms	16740 KB	Output is correct
15	Incorrect	16 ms	16768 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	16768 KB	Output is correct
2	Correct	17 ms	16868 KB	Output is correct
3	Correct	17 ms	16768 KB	Output is correct
4	Correct	15 ms	16768 KB	Output is correct
5	Correct	18 ms	16768 KB	Output is correct
6	Correct	17 ms	16768 KB	Output is correct
7	Correct	19 ms	16768 KB	Output is correct
8	Correct	86 ms	16768 KB	Output is correct
9	Correct	79 ms	16768 KB	Output is correct
10	Correct	91 ms	16768 KB	Output is correct
11	Correct	75 ms	16768 KB	Output is correct
12	Correct	86 ms	16768 KB	Output is correct
13	Correct	198 ms	16768 KB	Output is correct
14	Correct	15 ms	16764 KB	Output is correct
15	Incorrect	15 ms	16768 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	16760 KB	Output is correct
2	Correct	16 ms	16768 KB	Output is correct
3	Correct	16 ms	16768 KB	Output is correct
4	Correct	15 ms	16768 KB	Output is correct
5	Correct	16 ms	16740 KB	Output is correct
6	Correct	19 ms	16768 KB	Output is correct
7	Correct	19 ms	16768 KB	Output is correct
8	Correct	80 ms	16768 KB	Output is correct
9	Correct	86 ms	16768 KB	Output is correct
10	Correct	95 ms	16776 KB	Output is correct
11	Correct	86 ms	16768 KB	Output is correct
12	Correct	82 ms	16768 KB	Output is correct
13	Correct	193 ms	16768 KB	Output is correct
14	Correct	397 ms	16888 KB	Output is correct
15	Incorrect	19 ms	16760 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	16768 KB	Output is correct
2	Correct	18 ms	16768 KB	Output is correct
3	Correct	20 ms	16768 KB	Output is correct
4	Correct	15 ms	16768 KB	Output is correct
5	Correct	17 ms	16768 KB	Output is correct
6	Correct	18 ms	16768 KB	Output is correct
7	Correct	18 ms	16768 KB	Output is correct
8	Correct	86 ms	16768 KB	Output is correct
9	Correct	87 ms	16888 KB	Output is correct
10	Correct	79 ms	16768 KB	Output is correct
11	Correct	107 ms	16768 KB	Output is correct
12	Correct	75 ms	16768 KB	Output is correct
13	Correct	182 ms	16768 KB	Output is correct
14	Correct	16 ms	16768 KB	Output is correct
15	Incorrect	17 ms	16768 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	16768 KB	Output is correct
2	Correct	16 ms	16740 KB	Output is correct
3	Correct	16 ms	16768 KB	Output is correct
4	Correct	16 ms	16768 KB	Output is correct
5	Correct	15 ms	16768 KB	Output is correct
6	Correct	17 ms	16768 KB	Output is correct
7	Correct	17 ms	16768 KB	Output is correct
8	Correct	77 ms	16768 KB	Output is correct
9	Correct	92 ms	16768 KB	Output is correct
10	Correct	67 ms	16684 KB	Output is correct
11	Correct	90 ms	16768 KB	Output is correct
12	Correct	83 ms	16760 KB	Output is correct
13	Correct	231 ms	16768 KB	Output is correct
14	Correct	16 ms	16768 KB	Output is correct
15	Correct	15 ms	16768 KB	Output is correct
16	Correct	17 ms	16768 KB	Output is correct
17	Correct	51 ms	16768 KB	Output is correct
18	Correct	86 ms	16812 KB	Output is correct
19	Correct	83 ms	16772 KB	Output is correct
20	Correct	190 ms	16804 KB	Output is correct
21	Correct	189 ms	16888 KB	Output is correct
22	Correct	80 ms	16768 KB	Output is correct
23	Correct	224 ms	16768 KB	Output is correct
24	Correct	438 ms	16768 KB	Output is correct
25	Incorrect	15 ms	16740 KB	Output isn't correct
26	Halted	0 ms	0 KB	-