Submission #584725

#	Time	Username	Problem	Language	Result	Execution time	Memory
584725		sofapuden	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	140 ms	340 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mxN = 2e3+5;

ll n, a, b, v[mxN], pre[mxN]; 

bool g1(ll mask){
	vector<int> dp(n+1, mxN);
	dp[0] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j < i; ++j){
			if((mask|(pre[i]-pre[j])) == mask)dp[i] = min(dp[i],dp[j]+1);
		}
	}
	return dp[n] <= b;
}

bool g2(ll mask){
	vector<vector<bool>> dp(n+1, vector<bool> (n+1,false));
	dp[0][0] = true;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j < i; ++j){
			for(int k = 0; k < n; ++k){
				dp[i][k+1] = dp[i][k+1] | (dp[j][k] & ((mask | (pre[i]-pre[j])) == mask));
			}
		}
	}
	bool ret = 0;
	for(int i = a; i <= b; ++i)ret|=dp[n][i];
	return ret;
}

int main(){
	cin >> n >> a >> b;
	pre[0] = 0;
	for(int i = 1; i <= n; ++i)cin >> v[i], pre[i] = pre[i-1] + v[i];
	ll ans = (1ll<<50)-1;
	for(int i = 49; ~i; --i){
		if(a == 1 && g1(ans^(1ll<<i)))ans^=(1ll<<i);
		if(a > 1 && g2(ans^(1ll<<i)))ans^=(1ll<<i);
	}
	cout << ans << '\n';
}

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