Submission #40906

#	Time	Username	Problem	Language	Result	Execution time	Memory
40906		IvanC	Bali Sculptures (APIO15_sculpture)	C++14	46 / 100	333 ms	79684 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 105;
const int MAXOR = 4097;
int dp[MAXN][MAXN][MAXOR];
unordered_set<ll> dp1[MAXN][MAXN];
int N,A,B;
ll soma[MAXN],best;
ll calc(int a,int b){return soma[b] - soma[a-1];}
void solve1(int pos,int resta,ll curOr){
	if(resta < 0) return;
	if(dp1[pos][resta].count(curOr)) return;
	dp1[pos][resta].insert(curOr);
	if(pos == N + 1){
		if(resta != 0) return;
		best = min(best,curOr);
		return;
	}
	if(resta == 0) return;
	for(int quebra = pos;quebra<=N;quebra++){
		solve1(quebra+1,resta - 1,curOr | calc(pos,quebra));
	}
}
void solve(int pos,int resta,ll curOr){
	if(dp[pos][resta][curOr]) return;
	dp[pos][resta][curOr] = 1;
	if(pos == N + 1){
		if(resta != 0) return;
		best = min(best,curOr);
		return;
	}
	if(resta == 0) return;
	for(int quebra = pos;quebra<=N;quebra++){
		solve(quebra+1,resta - 1,curOr | calc(pos,quebra));
	}
}
int main(){
	scanf("%d %d %d",&N,&A,&B);
	for(int i = 1;i<=N;i++){
		scanf("%lld",&soma[i]);
		soma[i] += soma[i-1];
	}
	best = (ll)1e18;
	if(N <= 20){
		for(int i = A;i<=B;i++) solve1(1,i,0);
		printf("%lld\n",best);
		return 0;
	}
	for(int i = A;i<=B;i++) solve(1,i,0);
	printf("%lld\n",best);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&A,&B);
                            ^
sculpture.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&soma[i]);
                         ^

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