Submission #1105559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105559		_rain_	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	126 ms	31996 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define name "main"

const int maxlog=(int)42;
const int N=(int)2000;
ll arr[N+2]={};
ll ans=((ll)1<<maxlog)-1;
ll dp[N+2][N+2]={};
int n,a,b;

bool possible(ll limit){
	memset(dp,0x3f,sizeof dp);
	int INF=dp[0][0];
	dp[0][0]=0;
	for (int i=1;i<=n;++i){
		ll tot=0;
		for (int j=i;j<=n;++j){
			tot+=arr[j];
			if ((tot&limit)!=tot) continue;
			if (a==1) dp[j][1]=min(min(dp[i-1][0],dp[i-1][1])+1,dp[j][1]);
			else{
				for (int block=1;block<=min(i,b);++block){
					dp[j][block]=min(dp[i-1][block-1]+1,dp[j][block]);
				}
			}
		}
	}
	if (a==1){
		if (dp[n][1]<=b) return true;
		return false;
	}
	for (int i=a;i<=b;++i)
		if (dp[n][i]==i) return true;
	return false;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>a>>b;
	for (int i=1;i<=n;++i) cin>>arr[i];
	for (int i=maxlog-1;i>=0;--i){
		if (possible(ans^((ll)1<<i))) {
			ans^=((ll)1<<i);
		}
	}
	cout<<ans;
	exit(0);
}

Compilation message (stderr)

sculpture.cpp: In function 'bool possible(ll)':
sculpture.cpp:16:6: warning: unused variable 'INF' [-Wunused-variable]
   16 |  int INF=dp[0][0];
      |      ^~~

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