제출 #543667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543667		Sohsoh84	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	142 ms	4308 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 2e3 + 10;
const ll LOG = 50;

ll A[MAXN], n, a, b;
bool dp[MAXN][MAXN];
int dp2[MAXN];

inline bool check2(ll mask) {
	for (int i = 1; i <= n; i++) {
		dp2[i] = MAXN;
		ll s = 0;
		for (int j = i; j > 0; j--) {
			s += A[j];
			if (!(s & mask))
				dp2[i] = min(dp2[i], dp2[j - 1] + 1);
		}
	}

	return dp2[n] <= b;
}

inline bool check(ll mask) {
	if (a == 1) return check2(mask);

	memset(dp, false, sizeof dp);
	dp[0][0] = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {	
			ll s = 0;
			for (int k = i; k > 0; k--) {
				s += A[k];
				if (!(s & mask))
					dp[i][j] |= dp[k - 1][j - 1];
			}
		}
	}

	return count(dp[n] + a, dp[n] + b + 1, true);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) cin >> A[i];

	ll ans = 0, mask = 0;
	for (int i = LOG - 1; i >= 0; i--) {
		mask ^= (1ll << i);
		if (!check(mask)) {
			mask ^= (1ll << i);
			ans ^= (1ll << i);
		}
	}

	cout << ans << endl;
	return 0;
}

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