Submission #321566

#	Time	Username	Problem	Language	Result	Execution time	Memory
321566		minoum	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	246 ms	640 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 105, N = 2000 + 10;
ll n, a, b, d[N], y[N], prs[N];
bool dp[MAXN][MAXN];

bool slv1(ll mask){
	for(int i = 0; i < MAXN; i++)
		for(int j = 0; j < MAXN; j++) dp[i][j] = false;
	dp[0][0] = true;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= b; j++)
			for(int k = 1; k <= i; k++)
				dp[i][j] |= (dp[k - 1][j - 1] && (((prs[i] - prs[k - 1]) | mask) <= mask));
	bool can = false;
	for(int i = a; i <= b; i++) can |= dp[n][i];
	return can;
}

bool slv2(ll mask){
	for(int i = 0; i < N; i++) d[i] = (ll)INT_MAX;
	d[0] = 0;
	for(int i = 1; i <= n; i++)
		for(int k = 1; k <= i; k++)
			if(((prs[i] - prs[k - 1]) | mask) <= mask)
				d[i] = min(d[i], d[k - 1] + 1ll);
	if(d[n] <= b) return true;
	return false;
}


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> a >> b;
	for(int i = 1; i <= n; i++) cin >> y[i];
	for(int i = 1; i <= n; i++) prs[i] = y[i] + prs[i - 1];
	ll mask = (1ll << 60ll) - 1;
	for(ll pt = 59; pt >= 0; pt--){
		mask ^= (1ll << pt);
		bool can;
		if(n <= 100) can = slv1(mask);
		else can = slv2(mask);
		if(!can) mask |= (1ll << pt);
	}
	cout << mask << endl;
	return 0; 
}

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