Submission #40711

#	Time	Username	Problem	Language	Result	Execution time	Memory
40711		IvanC	Bali Sculptures (APIO15_sculpture)	C++14	21 / 100	4 ms	1428 KiB

sculpture

#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;
}

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