Submission #316713

#	Time	Username	Problem	Language	Result	Execution time	Memory
316713		nandonathaniel	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	101 ms	640 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005,INF=1e9;
bool dp[MAXN][MAXN];
int dp2[MAXN],n,a,b;
long long pref[MAXN],ans;

bool submask(long long mask){
	return ((mask|ans)==ans);
}

long long get(int l,int r){
	return pref[r]-pref[l-1];
}

bool can(){  //bisa ga or dari sumnya, submask dari ans
	if(n<=100){
		dp[0][0]=true;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=i;j++){
				dp[i][j]=false;
				for(int k=0;k<i;k++){
					if(dp[k][j-1] && submask(get(k+1,i)))dp[i][j]=true;
				}
			}
		}
		for(int i=a;i<=b;i++){
			if(dp[n][i])return true;
		}
		return false;
	}
	else{  //minimum partition
		dp2[0]=0;
		for(int i=1;i<=n;i++){
			dp2[i]=INF;
			for(int j=0;j<i;j++){
				if(submask(get(j+1,i)))dp2[i]=min(dp2[i],dp2[j]+1);
			}
		}
		return dp2[n]<=b;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> a >> b;
	for(int i=1;i<=n;i++){
		int x;cin >> x;
		pref[i]=pref[i-1]+x;
	}
	ans=(1LL<<41)-1;
	for(int i=40;i>=0;i--){
		//iterate dari MSB,karena 2^0+2^1+...+2^(x-1)=2^x-1
		ans^=(1LL<<i);
		if(!can())ans^=(1LL<<i);
	}
	cout << ans << '\n';
	return 0;
}

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