제출 #248799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248799		sahil_k	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	191 ms	504 KiB

sculpture

#include <iostream>
using namespace std;
int n, a, b;
long long cost[2100];
int dp1[2100];
bool dp2[110][110];
bool check (long long x) {
	if (a == 1) {
		for (int i=1; i<=n; i++) {
			dp1[i] = 1e9;
			long long cur = 0;
			for (int j=i-1; j>=0; j--) {
				cur += cost[j+1];
				if ((cur & x) == cur) {
					dp1[i] = min(dp1[i], dp1[j]+1);
				}
			}
		}
		return dp1[n] <= b;
	} else {
		dp2[0][0] = true;
		for (int i=1; i<=n; i++) {
			for (int k=1; k<=i; k++) {
				dp2[i][k] = false;
				long long cur = 0;
				for (int j=i-1; j>=0; j--) {
					cur += cost[j+1];
					if ((cur & x) == cur) {
						if (dp2[j][k-1]) dp2[i][k] = true;
					}
				}
			}
		}
		for (int i=a; i<=b; i++) {
			if (dp2[n][i]) return true;
		}
		return false;
	}
}
int main () {
	cin >> n >> a >> b;
	for (int i=1; i<=n; i++) {
		cin >> cost[i];
	}
	long long l = 0, r = (1ll<<50)-1, m;
	long long ans;
	while (l <= r) {
		m = (l+r)/2;
		if (check(m)) {
			ans = m;
			r = m-1;
		} else {
			l = m+1;
		}
	}
	cout << ans << endl;
}

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