제출 #585379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585379		GusterGoose27	Bali Sculptures (APIO15_sculpture)	C++11	21 / 100	14 ms	340 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN1 = 100;
bool dp[MAXN1+1][MAXN1+1];
int n, a, b;
int vals[MAXN1];
ll cur = 0;
int bit;

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

bool possible() {
	for (int i = n; i >= 0; i--) {
		for (int j = 0; j <= n; j++) {
			dp[i][j] = 0;
			if (i == n) {
				dp[i][j] = 1;
				continue;
			}
			if (j > n-i) {
				dp[i][j] = dp[i][n-i];
				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;
}

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: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29