답안 #332957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332957	2020-12-04T04:23:44 Z	Cantfindme	Bali Sculptures (APIO15_sculpture)	C++17	37 / 100	591 ms	620 KB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);

const int maxb = 42;
const int maxn = 2010;
int n,A,B;
int pref[maxn];
int aa[maxn];
int dp1[110][110];
int dp2[2010];
int curbm;

int cap(int x, int groups) {
	if (dp1[x][groups] != -1) return dp1[x][groups];
	if (groups > B) return 0;
	if (x == n) {
		if (groups >= A and groups <= B) return 1;
		else return 0;
	}
	
	int res = 0;
	for (int i = x; i < n;i++) {
		int sum = pref[i] - (x == 0?0: pref[x - 1]);
		
		bool works = true;
		for (int b = 0; b < maxb and works; b++) {
			if (sum & (1 << b) and !(curbm & (1 << b))) works = false;
		}
		if (works) res = max(res, cap(i+1,groups+1));
	}
	return dp1[x][groups] = res;
}

int32_t main() {
	cin >> n >> A >> B;
	for (int i =0;i<n;i++) cin >> aa[i];
	for (int i =0;i<n;i++) {
		pref[i] = (i==0?0:pref[i-1]) + aa[i];
	}
	
	int ans = (1ll << maxb)-1;
	if (n <= 100) { //a can be > 1
		//Greedy
		for (int b = maxb-1; b >= 0; b--) {
			curbm = ans ^ (1ll << b);
			//cout << "HI: " << b << " " << curbm << "\n";
			memset(dp1,-1,sizeof dp1);
			if (cap(0,0)) ans = curbm; //If you can limit all groups to have sum < (1<<b), ans can not have (1<<b) 
			//cout << "NEW: " << curbm << " " << ans << "\n\n";
		}
	} else { //a can only be = 1;
		
	}
	cout << ans;
}

Subtask #1

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	1 ms	512 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	2 ms	492 KB	Output is correct
20	Correct	2 ms	492 KB	Output is correct
21	Correct	3 ms	364 KB	Output is correct
22	Correct	3 ms	492 KB	Output is correct
23	Correct	3 ms	492 KB	Output is correct
24	Correct	2 ms	492 KB	Output is correct
25	Correct	3 ms	492 KB	Output is correct
26	Correct	4 ms	492 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	1 ms	364 KB	Output is correct
29	Correct	1 ms	492 KB	Output is correct
30	Incorrect	2 ms	492 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	3 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	2 ms	492 KB	Output is correct
20	Correct	15 ms	492 KB	Output is correct
21	Correct	4 ms	492 KB	Output is correct
22	Correct	3 ms	492 KB	Output is correct
23	Correct	3 ms	492 KB	Output is correct
24	Correct	2 ms	492 KB	Output is correct
25	Correct	3 ms	492 KB	Output is correct
26	Correct	4 ms	492 KB	Output is correct
27	Correct	5 ms	492 KB	Output is correct
28	Correct	6 ms	512 KB	Output is correct
29	Correct	10 ms	492 KB	Output is correct
30	Correct	28 ms	492 KB	Output is correct
31	Correct	46 ms	492 KB	Output is correct
32	Correct	35 ms	492 KB	Output is correct
33	Correct	4 ms	492 KB	Output is correct
34	Correct	46 ms	492 KB	Output is correct
35	Correct	42 ms	492 KB	Output is correct
36	Correct	29 ms	500 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	236 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	5 ms	492 KB	Output is correct
15	Correct	6 ms	492 KB	Output is correct
16	Correct	10 ms	492 KB	Output is correct
17	Correct	27 ms	492 KB	Output is correct
18	Correct	44 ms	492 KB	Output is correct
19	Correct	37 ms	492 KB	Output is correct
20	Correct	4 ms	492 KB	Output is correct
21	Correct	45 ms	492 KB	Output is correct
22	Correct	42 ms	492 KB	Output is correct
23	Correct	29 ms	492 KB	Output is correct
24	Correct	56 ms	492 KB	Output is correct
25	Correct	59 ms	492 KB	Output is correct
26	Correct	171 ms	492 KB	Output is correct
27	Correct	396 ms	492 KB	Output is correct
28	Correct	591 ms	620 KB	Output is correct
29	Correct	372 ms	492 KB	Output is correct
30	Correct	12 ms	492 KB	Output is correct
31	Correct	504 ms	492 KB	Output is correct
32	Correct	546 ms	492 KB	Output is correct

Subtask #4

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	3 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	2 ms	492 KB	Output is correct
20	Correct	2 ms	492 KB	Output is correct
21	Correct	3 ms	492 KB	Output is correct
22	Correct	3 ms	492 KB	Output is correct
23	Correct	3 ms	492 KB	Output is correct
24	Correct	2 ms	492 KB	Output is correct
25	Correct	3 ms	492 KB	Output is correct
26	Correct	4 ms	492 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	1 ms	512 KB	Output is correct
29	Correct	1 ms	492 KB	Output is correct
30	Incorrect	2 ms	492 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	492 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	492 KB	Output is correct
17	Incorrect	2 ms	492 KB	Output isn't correct
18	Halted	0 ms	0 KB	-