Submission #332988

#	Time	Username	Problem	Language	Result	Execution time	Memory
332988		Cantfindme	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	123 ms	640 KiB

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 = 43;
const int maxn = 2010;
const int INF = INT_MAX/2;

int n,A,B;
int pref[maxn];
int aa[maxn];
int dp1[110][110]; //after x items, j groups: works on not.
int dp2[2010]; //after x items: minimum number of groups 
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]);
		if ((sum & curbm) == 0) res = max(res, cap(i+1,groups+1));
	}
	return dp1[x][groups] = res;
}

int cap2(int x) {
	if (dp2[x] != -1) return dp2[x];
	if (x >= n) return 0;
	
	int res = INF;
	for (int i = x; i < n;i++) {
		int sum = pref[i] - (x == 0?0: pref[x - 1]);
		if ((sum & curbm) == 0) res = min(res, cap2(i+1) + 1);
	}
	
	return dp2[x] = res;
}

int32_t main() {
	FAST
	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 = (1ll << maxb) - 1;
			curbm ^= (ans ^ (1ll << b));
						
			memset(dp1,-1,sizeof dp1);
			if (cap(0,0)) ans ^= (1ll << b); //If you can limit all groups to have bm that doesn't have (1<<b) then ans can also not have (1<<b)
		}
	} else { //a can only be = 1;
		for (int b = maxb-1; b >= 0; b--) {
			curbm = (1ll << maxb) - 1;
			curbm ^= (ans ^ (1ll << b)); //All of the bits that cannot be on.
			
			memset(dp2,-1,sizeof dp2);
			if (cap2(0) <= B) ans ^= (1ll << b); 
		}
	}
	cout << ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29