Submission #83265

#	Time	Username	Problem	Language	Result	Execution time	Memory
83265		farukkastamonuda	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	229 ms	16788 KiB

sculpture

#include <bits/stdc++.h>
#define li 2005
#define inf 1000000009
#define md 1000000007
#define lo long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LOG 40
using namespace std;
int n,a,b,mn[li],dp[li][li],A[li];
vector<int> v[li];
bool check(lo int val){
	for(int i=1;i<=n;i++){
		v[i-1].clear();
		mn[i]=inf;
		lo int sum=0;
		for(int j=i-1;j>=0;j--){
			sum+=A[j+1];
			if((sum|val)==val){
				mn[i]=min(mn[i],mn[j]+1);
				v[j].pb(i);
			}
		}
	}
	if(a==1){
		return mn[n]<=b;
	}
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int l=1;l<=n;l++){
		for(int i=0;i<=n;i++){
			if(dp[l-1][i]){
				for(int j=0;j<(int)v[i].size();j++){
					dp[l][v[i][j]]=1;
				}
			}
		}
	}
	for(int i=a;i<=b;i++){
		if(dp[n][i]==1) return true;
	}
	return false;
}
int main(){
	scanf("%d %d %d",&n,&a,&b);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	lo ans=((1LL<<(LOG+1))-1);
	for(int i=LOG;i>=0;i--){
		ans-=(1LL<<i);
		if(!check(ans)) ans+=(1LL<<i);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:47: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:48:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&A[i]);
                        ~~~~~^~~~~~~~~~~~

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