Submission #32178

#	Time	Username	Problem	Language	Result	Execution time	Memory
32178		minchurl	Bali Sculptures (APIO15_sculpture)	C++11	100 / 100	749 ms	5068 KiB

sculpture

#include<stdio.h>
#define LL long long
#define MAX_N 2005
#define inf (1LL<<60)
#define MIN(x,y) ((x)<(y)?(x):(y))
LL ans,e;
LL arr[MAX_N],t[MAX_N];
bool sp_t[MAX_N][MAX_N];
LL N,A,B;
bool sp=false;
bool sp_is_ok(LL x){
	LL i,j,k,sum,y,z;
	LL end_point;
	for(i=0;i<=N;i++){
		for(j=0;j<=i;j++)	sp_t[i][j]=false;
	}
	sp_t[0][0]=true;
	if(x>=0)	ans+=(1LL<<x);
	y=(ans&-ans);
	for(i=1;i<=N;i++){
		sum=0;
		for(j=i;j>=1;j--){
			sum+=arr[j];
			z=sum;
			if(x>=0){z=sum|(y-1);z++;z-=y;}
			z|=ans;
			if(z!=ans)	continue;
			end_point=MIN(j,B);
			for(k=0;k<end_point;k++){
				if(sp_t[j-1][k]==true)	sp_t[i][k+1]=true;
			}
		}
	}
	if(x>=0)	ans-=(1LL<<x);
	for(i=A;i<=B;i++){
		if(sp_t[N][i]==true)	return true;
	}
	return false;
}

bool is_ok(LL x){
	LL i,j,sum,y,z;
	if(sp==true)	return sp_is_ok(x);
	for(i=1;i<=N;i++)	t[i]=inf;
	t[0]=0;
	if(x>=0)	ans+=(1LL<<x);
	y=(ans&-ans);
	for(i=1;i<=N;i++){
		sum=0;
		for(j=i;j>=1;j--){
			sum+=arr[j];
			z=sum;
			if(x>=0){z=sum|(y-1);z++;z-=y;}
			z|=ans;
			if(z!=ans)	continue;
			t[i]=MIN(t[i],t[j-1]+1);
		}
	}
	if(x>=0)	ans-=(1LL<<x);
	if(t[N]>B)	return false;
	else	return true;
}
LL bin_search(){
	LL s=0,mid;
	bool x;
	while(s<=e){
		mid=(s+e)/2;
		x=is_ok(mid);
		if(x==true){
			if(is_ok(mid-1)==false)	return mid;
			else	e=mid-1;
		}else{
			if(is_ok(mid+1)==true)	return mid+1;
			else	s=mid+1;
		}
	}
	return -1;
}
int main(){
	LL i,x;
	scanf("%lld %lld %lld",&N,&A,&B);
	for(i=1;i<=N;i++){
		scanf("%lld",&arr[i]);
	}
	if(A!=1)	sp=true;
	e=51;
	ans=(1LL<<56);
	while(e>=0){
		x=bin_search();
		if(x==-1 || x==e+1)	break;
		ans|=(1LL<<(x));
		e--;
	}
	ans-=(1LL<<56);
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:81:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&N,&A,&B);
                                  ^
sculpture.cpp:83:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
                        ^

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