Submission #102823

#	Time	Username	Problem	Language	Result	Execution time	Memory
102823		Noam527	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	99 ms	8568 KiB

sculpture

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

int n, lo, hi;
vector<int> a;
int dp[2002][2002];
ll b = 0;

bool good(ll sum) {
	return (sum & b) == 0;
}

bool can1() {
	ll sum = 0;
	for (int i = 0; i < n; i++)
		sum += a[i], dp[i][1] = good(sum);
	for (int j = 2; j <= hi; j++) {
		for (int i = j - 1; i < n; i++) {
			dp[i][j] = 0;
			sum = 0;
			for (int k = i; !dp[i][j] && k >= j - 1; k--) {
				sum += a[k];
				if (good(sum) && dp[k - 1][j - 1]) dp[i][j] = 1;
			}
		}
	}
	for (int i = lo; i <= hi; i++)
		if (dp[n - 1][i]) return true;
	return false;
}

bool can2() {
	ll sum;
	for (int i = 0; i < n; i++) {
		dp[i][0] = md;
		sum = 0;
		for (int j = i; j > 0; j--) {
			sum += a[j];
			if (good(sum)) dp[i][0] = min(dp[i][0], dp[j - 1][0] + 1);
		}
		sum += a[0];
		if (good(sum)) dp[i][0] = 1;
	}
	return dp[n - 1][0] <= hi;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> lo >> hi;
	a.resize(n);
	ll sum = 0, add = 1, ans = 0;
	for (auto &i : a) cin >> i, sum += i;
	while (add <= sum) add *= 2;
	add /= 2;
	while (add >= 1) {
		b ^= add;
		if (lo > 1) {
			if (!can1()) {
				b ^= add;
				ans += add;
			}
		}
		else {
			if (!can2()) {
				b ^= add;
				ans += add;
			}
		}
		add /= 2;
	}
	finish(ans);
}

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