제출 #40711

#제출 시각아이디문제언어결과실행 시간메모리
40711IvanCBali Sculptures (APIO15_sculpture)C++14
21 / 100
4 ms1428 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 110;
const ll INF = (ll)1e17;
ll dp[MAXN][MAXN],soma[MAXN],vetor[MAXN],n,a,b;
ll calc(ll a,ll b){return soma[b] - soma[a-1];}
ll solve(ll pos,ll resta){
	if(pos == n + 1){
		if(resta == 0) return 0;
		else return INF; 
	}
	if(resta <= 0){
		return INF;
	}
	if(dp[pos][resta] != -1) return dp[pos][resta];
	ll best = INF;
	for(int quebra = pos;quebra<=n;quebra++){
		best = min(best, calc(pos,quebra) | solve(quebra+1,resta - 1) );
	}
	return dp[pos][resta] = best;
}	
int main(){
	memset(dp,-1,sizeof(dp));
	cin >> n >> a >> b;
	for(int i = 1;i<=n;i++){
		cin >> vetor[i];
		soma[i] = vetor[i] + soma[i-1];
	}
	ll best = solve(1,a);
	for(int i = a+1;i<=b;i++) best = min(best, solve(1,i) );
	cout << best << 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...