Submission #671932

#	Time	Username	Problem	Language	Result	Execution time	Memory
671932		Dan4Life	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	552 ms	312 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = (int)1e2+10;
const ll LINF = (ll)1e18;
int n, A, B;
ll a[maxn], pre[maxn]; ll ans=LINF;

bool needs(ll mask, int bit){
	bool dp[110][110]; bool ok=1; 
	//if possible to make first i element, j groups, no sum has mask turned on 
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= B; j++)
			dp[i][j]=false;
	dp[0][0]=true;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= B; j++){
			for(int k = 0; k<i; k++){
				ll sum = pre[i]-pre[k]; bool skip=false;
				for(int l = bit+1; l < 40; l++){
					if(mask&(1ll<<l)) continue;
					if(sum&(1ll<<l)) skip=true;
				}
				if(sum&(1ll<<bit) or skip) continue;
				dp[i][j] |= dp[k][j-1];
			}
		}
	}
	for(int i = A; i <= B; i++) if(dp[n][i]) ok=0;
	return ok;
}

int32_t main() {
	cin >> n >> A >> B;
	for(int i = 0; i < n; i++) cin >> a[i], pre[i+1]=pre[i]+a[i];
	if(n<=100){
		ans = 0;
		for(int i = 40; i >= 0; i--)
			ans|=needs(ans|(1ll<<i),i)*(1ll<<i);
	}
	else{

	}
	cout << ans;
}

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