Submission #36484

#	Time	Username	Problem	Language	Result	Execution time	Memory
36484		UncleGrandpa925	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	509 ms	2232 KiB

sculpture

/*input
6 1 3
8 1 2 1 5 4
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 2005
#define bit(x,y) ((x>>y)&1LL)

int n, A, B;
int a[N], sum[N];

int getSum(int l, int r) {
	return sum[r] - sum[l - 1];
}

bool valid(int curMask, int lim) {
	return ((curMask & lim) == 0 ? 1 : 0);
}

namespace sub4 {
bool dp[105][105];
bool check(int mask) {
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++) dp[i][1] = valid(getSum(1, i), mask);
	for (int k = 2; k <= B; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				if (dp[j - 1][k - 1] == false) continue;
				if (!valid(getSum(j, i), mask)) continue;
				dp[i][k] = true; break;
			}
		}
	}
	for (int i = A; i <= B; i++) if (dp[n][i]) return true;
	return false;
}

void solve() {
	int mask = 0; int ret = 0;
	for (int i = 60; i >= 0; i--) {
		mask ^= (1LL << i);
		if (!check(mask)) mask ^= (1LL << i), ret ^= (1LL << i);
		assert(check(mask));
	}
	cout << ret << endl;
}

}

namespace sub5 {
int dp[2005];

bool check(int mask) {
	for (int i = 0; i < 2005; i ++) dp[i] = 1e9;
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (!valid(getSum(j, i), mask)) continue;
			dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
	return (dp[n] <= B);
}

void solve() {
	int mask = 0; int ret = 0;
	for (int i = 60; i >= 0; i--) {
		mask ^= (1LL << i);
		if (!check(mask)) mask ^= (1LL << i), ret ^= (1LL << i);
		assert(check(mask));
	}
	cout << ret << endl;
}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef in1code
	freopen("1test.inp", "r", stdin);
#endif
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
	if (n <= 100) {
		sub4::solve();
		return 0;
	}
	sub5::solve();
}

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