제출 #463887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
463887		Hamed5001	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1086 ms	16196 KiB

sculpture

#include <bits/stdc++.h>

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

int fun2(int idx, int grp) {
	if (grp > B)
		return 0;
	if (idx == N)
		return (A <= grp && grp <= B);

	int &ret = dp2[idx][grp];
	if (~ret) return ret;

	ret = 0;
	ll sum = 0;
	for (int i = idx; i < N; ++i) {
		sum += Y[i];
		if (!(sum & msk))
			ret |= fun2(i+1, grp+1);
	}

	return ret;
}

bool check2() {
	memset(dp2, -1, sizeof dp2);
	return fun2(0, 0);
}

// void solve1() {
// 	for (int bit = 50; bit >= 0; --bit) {
// 		msk |= (1 << bit);
// 		if (!check1())
// 			msk ^= (1 << bit), ans |= (1 << bit);
// 	}
// }

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

void solve() {
	cin >> N >> A >> B;
	for (int i = 0; i < N; ++i)
		cin >> Y[i];
	// if (A == 1) {
	// 	solve1();
	// }
	// else {
		solve2();
	// }
}

int main() {

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

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