Submission #68756

#	Time	Username	Problem	Language	Result	Execution time	Memory
68756		FedericoS	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	354 ms	1500 KiB

sculpture

#include <iostream>
using namespace std;
typedef long long int ll;

ll INF=1e18;
ll P=60;
int N,A,B;
ll Y[2005];
ll V[2005];
ll ans,res;
bool M[2005][2005];
bool flag;

int main(){

	cin>>N>>A>>B;
	for(int i=0;i<N;i++)
		cin>>Y[i];

	if(A==1){

		while(clock()<100000);

		ans=(1LL<<P)-1;

		for(int c=P-1;c>=0;c--){

			ans=ans^(1LL<<c);

			fill(V,V+N,INF);

			for(int i=N-1;i>=0;i--){
				res=0;
				for(int j=i;j<N;j++){
					res+=Y[j];
					if((res|ans)==ans)
						V[i]=min(V[i],V[j+1]+1);
				}

			}

			if(V[0]==INF or V[0]>B)
				ans=ans^(1LL<<c);

			//for(int i=0;i<N+1;i++)cout<<(V[i]==INF?-1:V[i])<<" ";cout<<endl;

		}

		cout<<ans;
			
	}
	else{

		M[0][N]=true;

		ans=(1LL<<P)-1;

		for(int c=P-1;c>=0;c--){

			ans=ans^(1LL<<c);

			for(int k=1;k<N;k++){

				fill(M[k],M[k]+N,false);

				for(int i=N-1;i>=0;i--){
					res=0;
					for(int j=i;j<N;j++){
						res+=Y[j];
						if((res|ans)==ans)
							M[k][i]=M[k][i]|M[k-1][j+1];
					}

				}
				
			}

			flag=false;
			for(int k=A;k<=B;k++)
				if(M[k][0])
					flag=true;

			if(!flag)
				ans=ans^(1LL<<c);

			//for(int i=0;i<N+1;i++)cout<<(V[i]==INF?-1:V[i])<<" ";cout<<endl;

		}

		cout<<ans;

	}

}
/*
6 1 3
8 1 2 1 5 4
*/

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