Submission #40947

#	Time	Username	Problem	Language	Result	Execution time	Memory
40947		IvanC	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	123 ms	976 KiB

sculpture

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

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