제출 #585376

#제출 시각아이디문제언어결과실행 시간메모리
585376GusterGoose27Bali Sculptures (APIO15_sculpture)C++11
0 / 100
2 ms276 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

bool possible() {
	for (ll i = n; i >= 0; i--) {
		for (ll 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 (ll next = i+1; next <= n; next++) {
				s += vals[next-1];
				if (dp[next][j-1] && works(s)) {
					dp[i][j] = 1;
					break;
				}
			}
		}
	}
	for (ll i = a; i <= b; i++)
		if (dp[0][i]) return 1;
	return 0;
}

int main() {
	cin >> n >> a >> b;
	for (ll 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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...