Submission #32177

#	Time	Username	Problem	Language	Result	Execution time	Memory
32177		minchurl	Bali Sculptures (APIO15_sculpture)	C++11	50 / 100	759 ms	1144 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];
LL N,A,B;
bool is_ok(LL x){
	LL i,j,sum,y,z;
	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;
}
void special(){
	//나중에...
	return;
}
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){
		special();
		return 0;
	}
	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:52: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:54:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
                        ^

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