제출 #584725

#제출 시각아이디문제언어결과실행 시간메모리
584725sofapudenBali Sculptures (APIO15_sculpture)C++14
100 / 100
140 ms340 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...