제출 #853045

#제출 시각아이디문제언어결과실행 시간메모리
853045aymanrsBali Sculptures (APIO15_sculpture)C++14
100 / 100
66 ms692 KiB
#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n, a, b;
	cin >> n >> a >> b;
	int y[n+1];
	for(int i = 1;i <= n;i++) cin >> y[i];
	if(a == 1){
		long long bad = 0, ans = 0;
		for(int i = 40;i >= 0;i--){
			long long  t = bad;
			bad |= 1LL<<i;
			int dp[n+1];
			dp[0]=0;
			for(int i = 1;i <= n;i++){
				long long s = 0;
				dp[i] = 3000;
				for(int j = i;j;j--){
					s += y[j];
					if(!(s&bad)) dp[i] = min(dp[i], 1+dp[j-1]);
				}
			}
			if(dp[n] > b) {
				bad = t;
				ans |= 1LL<<i;
			}
		}
		cout << ans << '\n';
		return;
	}
	long long bad = 0, ans = 0;
	for(int i = 36;i >= 0;i--){
		long long  t = bad;
		bad |= 1LL<<i;
		int dp[n+1][n+1];
		for(int j = 0;j <= n;j++) for(int i = 0;i <= n;i++) dp[j][i] = 200;
		dp[0][0]=0;
		for(int i = 1;i <= n;i++){
			long long s = 0;
			for(int j = i;j;j--){
				s += y[j];
				if(!(s&bad)) {
					dp[i][0] = min(dp[i][0], 1+dp[j-1][0]);
					for(int k = 1;k <= n;k++){
						dp[i][k] = min(dp[i][k], 1+dp[j-1][k-1]);
					}
				}
			}
		}
		if(dp[n][a] > b) {
			bad = t;
			ans |= 1LL<<i;
		}
	}
	cout << ans << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}
#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...