Submission #463892

#	Time	Username	Problem	Language	Result	Execution time	Memory
463892		Hamed5001	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	181 ms	452 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mxN = 2e3+10;
int dp[mxN][mxN];
int N, A, B;
int Y[mxN];
ll msk, ans;

bool check() {
	if (A == 1) {
		vector<int> d(mxN, 1e9);
		queue<int> q;
		q.push(0);
		d[0] = 0;
		while(q.size()) {
			int i = q.front();
			q.pop();
			ll sum = 0;
			for (int j = i+1; j <= N; ++j) {
				sum += Y[j];
				if (d[j] == 1e9 && !(sum & msk)) {
					d[j] = d[i] + 1;
					q.push(j);
				}
			}
		}
		return d[N] <= B;
	}

	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) {
		for (int cnt = 1; cnt <= N; ++cnt) {
			if (dp[i][cnt]) {
				ll sum = 0;
				for (int j = i+1; j <= N; ++j) {
					sum += Y[j];
					if (!(msk & sum))
						dp[j][cnt+1] = 1;
				}
			}
		}
	}
	for (int i = A; i <= B; ++i) {
		if (dp[N][i])
			return 1;
	}
	return 0;
}

void solve() {
	cin >> N >> A >> B;
	for (int i = 1; i <= N; ++i)
		cin >> Y[i];

	for (int bit = 50; bit >= 0; --bit) {
		msk |= (1LL << bit);
		if (!check()) 
			msk ^= (1LL << bit), ans |= (1LL << bit);
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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