Submission #583191

#	Time	Username	Problem	Language	Result	Execution time	Memory
583191		Justin1	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	38 ms	340 KiB

sculpture

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

ll n,m,k,x,y,z;
ll a,b;
bool dp[105][105];
ll ar[105];

bool check(ll x) {
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) dp[i][j] = 0;
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) { //pos
		for (int j = 1; j <= n; j++) { //groups
			for (int k = 1; k <= i; k++) { //start pos
				if (dp[k-1][j-1] && ((ar[i] - ar[k-1]) | x) == x)
					dp[i][j] = 1;
			}
		}
	}
	for (int i = a; i <= b; i++) if (dp[n][i]) return 1;
	return 0;
}

signed main() {
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) cin >> ar[i];
	for (int i = 1; i <= n; i++) ar[i] += ar[i-1];
	ll ans = 0;
	for (int i = 0; i <= 60; i++) ans |= (1ll << i);
	for (int i = 60; i >= 0; i--) if (check(ans ^ (1ll << i))) ans ^= 1ll << i;
	cout << ans << "\n";
}

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