Submission #279634

#	Time	Username	Problem	Language	Result	Execution time	Memory
279634		srvlt	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	981 ms	512 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 103, k0 = 41;
int n, a, b, dp[n0][n0];
ll v[n0], p[n0];

int check(ll x) {
	memset(& dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 1; i <= b; i++)
		for (int j = i; j <= n; j++)
			for (int k = 0; k < j; k++)
				if (((p[j] - p[k]) & x) == p[j] - p[k])
					dp[i][j] |= dp[i - 1][k];
	for (int i = a; i <= b; i++)
		if (dp[i][n]) return 1;
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		p[i] = p[i - 1] + v[i];
	}
	ll cur = (1ll << k0) - 1;
	for (int i = k0 - 1; i >= 0; i--)
		if (check(cur ^ (1ll << i)))
			cur ^= 1ll << i;
	cout << cur;
}

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