Submission #87777

#	Time	Username	Problem	Language	Result	Execution time	Memory
87777		KCSC	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	158 ms	2340 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

const int DIM = 2005;

int dp1[DIM]; long long psm[DIM];
bool dp2[DIM][DIM];

bool solve(long long val, int n, int a, int b) {
	long long aux = ((1LL << 50) - 1) ^ val;
	if (a == 1) {
		dp1[0] = 0;	
		for (int i = 1; i <= n; ++i) {
			dp1[i] = b + 1;
			for (int j = i; j >= 1; --j) {
				if (!((psm[i] - psm[j - 1]) & aux)) {
					dp1[i] = min(dp1[i], dp1[j - 1] + 1); } } }
		return dp1[n] <= b; }
	else {
		dp2[0][0] = true;
		for (int k = 1; k <= b; ++k) {	
			for (int i = 1; i <= n; ++i) {
				dp2[k][i] = false;	
				for (int j = i; j >= 1; --j) {
					if (!((psm[i] - psm[j - 1]) & aux)) {
						dp2[k][i] |= dp2[k - 1][j - 1]; } } } }
		for (int k = a; k <= b; ++k) {
			if (dp2[k][n]) { 
				return true; } }
		return false; } }

int main(void) {
#ifdef HOME
	freopen("sculpture.in", "r", stdin);
	freopen("sculpture.out", "w", stdout);
#endif
	int n, a, b; cin >> n >> a >> b;	
	for (int i = 1; i <= n; ++i) {
		cin >> psm[i]; psm[i] += psm[i - 1]; }
	long long ans = 0;
	for (long long i = (1LL << 49); i; i >>= 1) {
		if (!solve(ans ^ (i - 1), n, a, b)) {
			ans ^= i; } }
	cout << ans;
	return 0; }

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