제출 #40947

#제출 시각아이디문제언어결과실행 시간메모리
40947IvanCBali Sculptures (APIO15_sculpture)C++14
50 / 100
123 ms976 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2010;
int dp[MAXN],N,A,B;
ll soma[MAXN],proibido,atual;
ll calc(ll a,ll b){return soma[b] - soma[a-1];}
int solve(int pos){
	if(dp[pos] != -1) return dp[pos];
	if(pos == N + 1) return dp[pos] = 0;
	int best = MAXN;
	for(int quebra = pos;quebra<=N;quebra++){
		if((calc(pos,quebra)) & proibido) continue;
		best = min(best, 1 + solve(quebra+1));
	}
	return dp[pos] = best;
}
int main(){
	cin >> N >> A >> B;
	for(int i = 1;i<=N;i++){
		cin >> soma[i];
		soma[i] += soma[i-1];
	}
	for(ll i = 41;i>=0;i--){
		proibido |= (1LL << i);
		memset(dp,-1,sizeof(dp));
		if(solve(1) > B){
			proibido ^= (1LL << i);
			atual |= (1LL << i);
		}
	}
	cout << atual << 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...