Submission #585385

#	Time	Username	Problem	Language	Result	Execution time	Memory
585385		GusterGoose27	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	101 ms	340 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN1 = 100;
const int MAXN2 = 2e3;
bool dp[MAXN1+1][MAXN1+1];
int n, a, b;
int vals[MAXN2];
ll cur = 0;
int bit;
int dist[MAXN2+1];
const int inf = 1e9;

bool works(ll sum) { // tested, CONFIRMED
	ll sumshift = (sum >> bit);
	ll curshift = (cur >> bit);
	return ((curshift&sumshift) == sumshift);
}

bool possible1() { // tested, CONFIRMED
	for (int i = n; i >= 0; i--) {
		for (int j = 0; j <= n; j++) {
			dp[i][j] = 0;
			if (i == n) {
				dp[i][j] = (j == 0);
				continue;
			}
			if (j == 0) {
				continue;
			}
			ll s = 0;
			for (int next = i+1; next <= n; next++) {
				s += vals[next-1];
				if (dp[next][j-1] && works(s)) {
					dp[i][j] = 1;
					break;
				}
			}
		}
	}
	for (int i = a; i <= b; i++)
		if (dp[0][i]) return 1;
	return 0;
}

bool possible2() {
	dist[n] = 0;
	for (int i = n-1; i >= 0; i--) {
		dist[i] = inf;
		ll s = 0;
		for (int j = i+1; j <= n; j++) {
			s += vals[j-1];
			if (works(s)) dist[i] = min(dist[i], dist[j]+1);
		}
	}
	return (dist[0] <= b);
}

bool possible() {
	if (a > 1) return possible1();
	return possible2();
}

int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> vals[i];
		cur += vals[i];
	}
	bit = floor(log2(cur));
	cur = 0;
	while (bit >= 0) {
		if (!possible()) { // possible to avoid
			cur += (1ULL << bit);
		}
		bit--;
	}
	cout << cur << "\n";
}

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