Submission #248791

#	Time	Username	Problem	Language	Result	Execution time	Memory
248791		sahil_k	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	190 ms	508 KiB

sculpture

#include <iostream>
using namespace std;
int n, a, b;
long long cost[2100];
int dp1[2100];
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 {
		return true;
	}
}
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;
}
/*
6 1 3
8 1 2 1 5 4
*/

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