Submission #110972

#	Time	Username	Problem	Language	Result	Execution time	Memory
110972		aleksam	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	3 ms	512 KiB

sculpture

//Apio 15 structures
#include <bits/stdc++.h>
#define INF INT_MAX
#define MOD 100000007
#define MAX_N 2019

using namespace std;
 
int A, B, N;
int a[MAX_N];
unsigned long long s[MAX_N];
int fs[MAX_N], ls[MAX_N];

bool bfs(unsigned long long n){//vraca moze ne moze
	memset(fs, -1, sizeof(fs));
	memset(ls, -1, sizeof(ls));
	fs[0]=ls[0]=0;//pusti grane iz nule
	for(int i=1; i<=N; ++i){
		if((s[i-1]|n)==n){
			fs[i]=fs[0]+1;
			ls[i]=ls[0]+1;
			//printf("Digao sam %d iz 0", i);
		}
	}
	for(int i=1; i<N; ++i){
		if(fs[i]==-1)continue;
		//pustamo grane iz i
		for(int j=i+1; j<=N; ++j){
			if(((s[j-1]-s[i-1])|n)==n){
				if(fs[j]>fs[i]+1 || fs[j]==-1)fs[j]=fs[i]+1;
				if(ls[j]<ls[i]+1)ls[j]=ls[i]+1;
			}
		}
	}
	if(ls[N]==-1)return 0;
	if(ls[N]>=A && fs[N]<=B)return 1;
	return 0;
}

int main(){
	ios::sync_with_stdio(false);
	cin>>N>>A>>B;
	for(int i=0; i<N; ++i){
		cin>>a[i];
		if(i==0)s[i]=a[i];
		else s[i]=a[i]+s[i-1];
	}
	
	long long log=0;
	while(s[N-1]>(1LLU<<log))log++;
	long long mask=(1<<log)-1;
	//assert(log<50);
	for(int i=log-1; i>=0; --i){
		mask-=(1<<i);
		if(bfs(mask))continue;
		else mask+=(1<<i);
	}
	cout<<mask;
	return 0;
}
/*
6 1 3
8 1 2 1 5 4
*/
 
/*
7 3
4 1 3 4 0 2 3
*/

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