Submission #42092

#	Time	Username	Problem	Language	Result	Execution time	Memory
42092		minchurl	Bali Sculptures (APIO15_sculpture)	C++11	0 / 100	2 ms	532 KiB

sculpture

#include<bits/stdc++.h>
#define MAX_N 2005
#define inf (1LL<<60)
#define LL long long
using namespace std;
LL n,a,b,ans,arr[MAX_N];
LL t[MAX_N],ct[MAX_N][MAX_N];
LL case1(){
	LL i,j,k,sum;
	for(i=0;i<=n;i++)	for(j=0;j<=n;j++)	ct[i][j]=inf;
	ans=inf;
	ct[0][0]=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			sum=0;
			for(k=i;k>=1;k--){
				sum+=arr[k];
				ct[j][i]=min(ct[j][i],ct[j-1][k-1]|sum);
				if(i==n && j>=a && j<=b)	ans=min(ans,ct[j][i]);
			}
		}
	}
	return ans;
}
bool is_ok(LL x){
	LL i,j,sum,test,y,z,k;
	y=inf-1;y-=(1LL<<x)-1;
	z=ans&y;
	for(i=1;i<=n;i++)	t[i]=inf;
	t[0]=0;
	for(i=1;i<=n;i++){
		sum=0;
		for(j=i;j>=1;j--){
			sum+=arr[j];
			k=sum&y;
			if((z|k)==z)	t[i]=min(t[i],t[j-1]+1);
		}
	}
	return t[n]<=b;
}
int main(){
	LL i,x;
	scanf("%lld",&n);
	scanf("%lld %lld",&a,&b);
	for(i=1;i<=n;i++)	scanf("%lld",&arr[i]);
	if(n<=100)	return !printf("%lld\n",case1());
	ans=0;
	for(i=50;i>=0;i--)	ans|=is_ok(i)?0LL:(1LL<<i);
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'bool is_ok(long long int)':
sculpture.cpp:26:13: warning: unused variable 'test' [-Wunused-variable]
  LL i,j,sum,test,y,z,k;
             ^
sculpture.cpp: In function 'int main()':
sculpture.cpp:42:7: warning: unused variable 'x' [-Wunused-variable]
  LL i,x;
       ^
sculpture.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
sculpture.cpp:44:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&a,&b);
                          ^
sculpture.cpp:45:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%lld",&arr[i]);
                                         ^

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