Submission #672279

#	Time	Username	Problem	Language	Result	Execution time	Memory
672279		prarie	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	215 ms	460 KiB

sculpture

#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compress(v) sort(all(v)), (v).erase(unique(all((v))), v.end())
#define pb push_back
#define eb emplace_back
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
 
template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }
template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

int main() {
	fastio;
	int N, A, B;
	cin >> N >> A >> B;
	vector<int> Y(N);
	for (auto &y : Y) {
		cin >> y;
	}

	auto check = [&](ll R) -> bool {
		if (A == 1) {
			vector<int> dp(N + 1, int(1e9));
			dp[0] = 0;
			for (int i = 0; i < N; i++) {
				ll sum = 0;
				for (int j = i; j >= 0; j--) {
					sum += Y[j];
					if (!(sum & (~R))) {
						dp[i + 1] = min(dp[i + 1], dp[j] + 1);
					}
				}
			}
			return dp[N] <= B;
		}

		vector<vector<int>> dp(N + 1, vector<int>(N + 1));
		dp[0][0] = 1;
		for (int i = 0; i < N; i++) {
			ll sum = 0;
			for (int j = i; j >= 0; j--) {
				sum += Y[j];
				for (int g = 0; g < N; g++) {
					if (!(sum & (~R)) && dp[j][g]) {
						dp[i + 1][g + 1] = 1;
					}
				}
			}
		}

		for (int g = A; g <= B; g++) {
			if (dp[N][g]) {
				return true;
			}
		}
		return false;
	};

	ll ans = 0;
	for (int b = 60; b >= 0; b--) {
		ll R = ans | ((1LL << b) - 1);
		if (!check(R)) {
			ans |= (1LL << b);
		}
	}

	cout << ans << endl;
}

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