Submission #1344216

#TimeUsernameProblemLanguageResultExecution timeMemory
1344216ThylOneBali Sculptures (APIO15_sculpture)C++20
25 / 100
1095 ms460 KiB
//####################
//BaliSculture
//####################
#include<bits/stdc++.h> 



#define rall(x) x.rbegin(), x.rend()
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()

#define int int64_t
using namespace std;
const int LOG = 42;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,A,B;
	cin>>n>>A>>B;
	vector<int> vals(n);
	for(int &i:vals)cin>>i;
	

	auto possible = [&](int acceptable,int G){
		vector<vector<bool>> dp(n+1,vector<bool>(n+1,false));
		dp[n][0] = true;
		
		for(int k=1 ; k <= n ; k++){
			for(int pos = n-1 ; pos>=0U ; pos--){
				int sum(0);
				for(int i = pos ; i < n ; i++){
					sum += vals[i];
					if((sum|acceptable) == acceptable){//on est bon
						dp[pos][k] = dp[i+1][k-1];
						if(dp[pos][k])break;
					}
				}
			}
		}
		return (bool)dp[0][G];
	};
	
	int ans = ((int)1)<<(LOG-1);
	for(int g=A;g<=B;g++){
		int mask = 0;
		for(int b=0;b<LOG ; b++)mask|=(((int)1)<<b);
	
		for(int b = LOG-1 ; b>=(int)0 ; b--){
			bool re = possible(mask^(((int)1)<<b), g);
			if(re){
				mask = (mask^(((int)1)<<b));
			}
		}
		ans = min(ans, mask);
	}
	cout << ans << endl;
	return 0;
};
#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...