Submission #59060

#	Time	Username	Problem	Language	Result	Execution time	Memory
59060		Adhyyan1252	Bali Sculptures (APIO15_sculpture)	C++11	71 / 100	1002 ms	263168 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, a, b;
ll y[100], pref[101];
long long ans = 0;
int firstI = 40;

inline ll rem(ll i, ll cnt){
	return ((i>>cnt)<<cnt);
}

bool check(){
	vector<vector<bool> > dp(n, vector<bool>(b+1, 0));
	dp[0][1] = ((rem(y[0], firstI)|ans) == ans);
	for(int i = 1; i < n; i++){
		dp[i][1] = ((rem(pref[i+1], firstI)|ans) == ans);
		for(int k = 2; k <= b; k++){
			ll sum = y[i];
			for(int j = i-1; j >= 0 && !dp[i][k]; j--){
				dp[i][k] = (dp[j][k-1] && ((rem(sum, firstI)|ans) == ans));
				sum += y[j];
			}
		}
	}
//	for(int i = 0; i < n; i++){
//		for(int j = 0; j <= b; j++){
//			cout<<dp[i][j]<<"\t";
//		}
//		cout<<endl;
//	}
//	cout<<endl;
	for(int i = a; i <= b; i++){
		if(dp[n-1][i]) return true;
	}
	return false;
}

int main(){
	cin>>n>>a>>b;
	pref[0] = 0;
	for(int i = 0; i < n; i++){
		cin>>y[i];
		pref[i+1] = pref[i] + y[i];
	}
	
	ans = (1LL<<firstI)-1;
	
	for(firstI--; firstI >= 0; firstI--){
		
		ans -= (1LL<<firstI);
		//cout<<"PRE "<<firstI<<" : "<<ans<<endl;
		if(!check()){
			//cout<<"NO"<<endl;
			ans += (1LL<<(firstI));
		}	
	}
	cout<<ans<<endl;
}

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