Submission #104567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104567	2019-04-08T05:38:01 Z	YottaByte	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	493 ms	16816 KB

sculpture

#include <iostream>
using namespace std;

#define int long long
#define pc __builtin_popcount

const int N = 21, inf = 1073741824;

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

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

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

Compilation message

sculpture.cpp:44: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	9 ms	8448 KB	Output is correct
2	Correct	11 ms	8576 KB	Output is correct
3	Correct	11 ms	8576 KB	Output is correct
4	Correct	10 ms	8576 KB	Output is correct
5	Correct	9 ms	8448 KB	Output is correct
6	Correct	18 ms	8576 KB	Output is correct
7	Correct	10 ms	8448 KB	Output is correct
8	Correct	9 ms	8576 KB	Output is correct
9	Correct	10 ms	8576 KB	Output is correct
10	Correct	10 ms	8576 KB	Output is correct
11	Correct	10 ms	8576 KB	Output is correct
12	Correct	9 ms	8576 KB	Output is correct
13	Correct	419 ms	8568 KB	Output is correct
14	Correct	11 ms	8448 KB	Output is correct
15	Incorrect	11 ms	8576 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8576 KB	Output is correct
2	Correct	10 ms	8576 KB	Output is correct
3	Correct	9 ms	8448 KB	Output is correct
4	Correct	9 ms	8448 KB	Output is correct
5	Correct	9 ms	8576 KB	Output is correct
6	Correct	13 ms	8576 KB	Output is correct
7	Correct	9 ms	8536 KB	Output is correct
8	Correct	9 ms	8576 KB	Output is correct
9	Correct	10 ms	8576 KB	Output is correct
10	Correct	10 ms	8576 KB	Output is correct
11	Correct	9 ms	8448 KB	Output is correct
12	Correct	9 ms	8576 KB	Output is correct
13	Correct	446 ms	8576 KB	Output is correct
14	Correct	9 ms	8576 KB	Output is correct
15	Incorrect	10 ms	8576 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8448 KB	Output is correct
2	Correct	9 ms	8576 KB	Output is correct
3	Correct	9 ms	8576 KB	Output is correct
4	Correct	11 ms	8576 KB	Output is correct
5	Correct	10 ms	8576 KB	Output is correct
6	Correct	17 ms	8576 KB	Output is correct
7	Correct	10 ms	8576 KB	Output is correct
8	Correct	7 ms	8448 KB	Output is correct
9	Correct	12 ms	8576 KB	Output is correct
10	Correct	8 ms	8576 KB	Output is correct
11	Correct	12 ms	8576 KB	Output is correct
12	Correct	25 ms	8556 KB	Output is correct
13	Correct	493 ms	8568 KB	Output is correct
14	Runtime error	22 ms	16816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	8576 KB	Output is correct
2	Correct	10 ms	8576 KB	Output is correct
3	Correct	10 ms	8576 KB	Output is correct
4	Correct	9 ms	8448 KB	Output is correct
5	Correct	11 ms	8576 KB	Output is correct
6	Correct	14 ms	8576 KB	Output is correct
7	Correct	11 ms	8576 KB	Output is correct
8	Correct	10 ms	8576 KB	Output is correct
9	Correct	9 ms	8576 KB	Output is correct
10	Correct	9 ms	8576 KB	Output is correct
11	Correct	9 ms	8576 KB	Output is correct
12	Correct	9 ms	8576 KB	Output is correct
13	Correct	408 ms	8696 KB	Output is correct
14	Correct	11 ms	8576 KB	Output is correct
15	Incorrect	12 ms	8704 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	8576 KB	Output is correct
2	Correct	10 ms	8576 KB	Output is correct
3	Correct	9 ms	8576 KB	Output is correct
4	Correct	10 ms	8576 KB	Output is correct
5	Correct	11 ms	8576 KB	Output is correct
6	Correct	13 ms	8576 KB	Output is correct
7	Correct	9 ms	8448 KB	Output is correct
8	Correct	9 ms	8448 KB	Output is correct
9	Correct	10 ms	8576 KB	Output is correct
10	Correct	8 ms	8576 KB	Output is correct
11	Correct	10 ms	8576 KB	Output is correct
12	Correct	11 ms	8572 KB	Output is correct
13	Correct	480 ms	8668 KB	Output is correct
14	Correct	10 ms	8568 KB	Output is correct
15	Incorrect	10 ms	8576 KB	Output isn't correct
16	Halted	0 ms	0 KB	-