Submission #1130510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130510		am_aadvik	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	115 ms	472 KiB

sculpture

#include <iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<math.h>
#define int long long
const int inf = 1e17;
const int maxn = 300005;
const int mod = (int)1e9 + 7;
using namespace std;

int n, a, b;
vector<int> arr;

bool minp(int mask) {
	vector<int> dp(n + 1, inf);
	dp[n] = 0;
	for (int i = n - 1; i >= 0; --i) {
		int sum = arr[i];
		for (int j = i; j < n; ++j) {
			if((sum & mask) == sum)
				dp[i] = min(dp[i], 1 + dp[j + 1]);
			if (j < (n - 1)) sum += arr[j + 1];
		}
	}
	return (dp[0] <= b);
}

bool rangep(int mask) {
	vector<vector<bool>> dp(n + 1, vector<bool>(b + 1, 0));
	dp[n][0] = 1;
	for (int i = n - 1; i >= 0; --i)
		for (int j = 1; j <= b; ++j) {
			int sum = arr[i];
			for (int l = i; l < n; ++l) {
				if ((sum & mask) == sum)
					dp[i][j] = (dp[i][j] || dp[l + 1][j - 1]);
				if (j < (n - 1)) sum += arr[l + 1];
			}
		}
	bool ans = 0;
	for (int i = a; i <= b; ++i) ans |= dp[0][i];
	return ans;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> a >> b;
	arr.resize(n);
	for (int i = 0; i < n; ++i) cin >> arr[i];

	int res = ((1ll << 50ll) - 1ll);
	for (int i = 49; i >= 0; --i) {
		int nw = res - (1ll << i);
		bool cur = 0;
		if (a == 1) cur = minp(nw);
		else cur = rangep(nw);
		if (cur) res = nw;
	}
	cout << res;
}

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