제출 #572628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572628		beaconmc	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	513 ms	31868 KiB

sculpture

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double

using namespace std;

ll n,a,b;
ll nums[2005];
vector<ll> dp1[2005];
ll dp2[2005][2005];


ll poww(ll n){
	ll sus = 1;

	FOR(i,0,n){
		sus *= 2;
	}
	return sus;
}
int check(ll v){
	FOR(i,0,n+2) FOR(j,0,n+2) dp2[i][j] = 1000000000000000;

	FOR(i,0,n+1) dp1[i] = {1000000000000000,1000000000000000};

	dp1[0] = {0,0};

	if (a==1){
		FOR(i,0,n+1){
			ll cur = 0;
			FOR(x, i+1, n+1){
				cur += nums[x];
				if ((cur&v)==cur){
					dp1[x] = {cur, min(dp1[x][1], dp1[i][1] + 1)};
				}
			}
		}
		if ((dp1[n][0]&v)==dp1[n][0] && dp1[n][1] <= b) return 1;

		return 0;
	}else{
		dp2[0][0] = 0;

		FOR(i,0,n+1){
			FOR(j,0,n+1){
				ll cur = 0;
				FOR(x, i+1, n+1){
					cur += nums[x];
					if ((cur&v)==cur) dp2[x][j+1] = min(dp2[x][j+1], dp2[i][j] | cur);
				}
			}
		}


		FOR(i,a,b+1){
			if ((dp2[n][i]&v) == dp2[n][i]) return 1;
		}
	}


	return 0;

}


int main(){
	cin >> n >> a >> b;
	FOR(i,0,n) cin >> nums[i+1];

	ll sus = poww(50)-1;


	FORNEG(i, 49, -1){
		sus -= poww(i);
		if (check(sus)) continue;
		else sus += poww(i);
	}
	cout << sus;

}

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