Submission #133575

#	Time	Username	Problem	Language	Result	Execution time	Memory
133575		junodeveloper	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	99 ms	632 KiB

sculpture

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define fi first
#define se second
using namespace std;
typedef long long ll;
int n, A, B, D[2010];
ll a[2010];
bool chk[2010][2010];
inline bool f(ll x,ll sum,int p) {
	return (~x&sum)==0;
}
bool Check1 (ll x, int p) {
	int i,j,k;ll sum;
	for(i=1;i<=n;i++) {
		chk[i][1]=f(x,a[i],p);
		for(j=2;j<=i;j++) {
			chk[i][j]=false;
			for(k=i-1;k>=j-1;k--) {
				sum=a[i]-a[k];
				if(f(x,sum,p)) {
					chk[i][j]|=chk[k][j-1];
				}
			}
		}
	}
	bool res=false;
	for(i=A;i<=B;i++) res|=chk[n][i];
	return res;
}
bool Check2(ll x, int p) {
	int i,j;
	for(i=1;i<=n;i++) {
		D[i]=B+1;
		for(j=0;j<i;j++) {
			if(f(x,a[i]-a[j],p))
				D[i]=min(D[i],D[j]+1);
		}
	}
	return D[n]<=B;
}
int main() {
	int task;
	scanf("%d%d%d",&n,&A,&B);
	if(n<=100) task=0;
	else task=1;
	int i;
	for(i=1;i<=n;i++) {
		scanf("%lld",a+i);
		a[i]+=a[i-1];
	}
	ll res=0;
	for(i=41;i>=0;i--) {
		if(task) { if(!Check2(res+(1ll<<i)-1,i)) res|=1ll<<i; }
		else { if(!Check1(res+(1ll<<i)-1,i)) res|=1ll<<i; }
	}
	printf("%lld",res);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~
sculpture.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",a+i);
   ~~~~~^~~~~~~~~~~~

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