제출 #671943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671943		Dan4Life	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	1086 ms	312 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = (int)2e3+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;
	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];
				if(sum&(1ll<<bit) or ((sum>>bit)|mask)!=mask) continue;
				dp[i][j] |= dp[k][j-1];
			}
		}
	}
	for(int i = A; i <= B; i++) if(dp[n][i]) ok=0;
	return ok;
}

bool needs2(ll mask, int bit){
	int dp[2010];
	for(int i = 0; i <= n; i++) dp[i]=n+1;
	dp[0]=0;
	for(int i = 1; i <= n; i++){
		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] = min(dp[i], dp[k]+1);
		}
	}
	return dp[n]>B;
}

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

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