Submission #148185

#	Time	Username	Problem	Language	Result	Execution time	Memory
148185		Juney	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	96 ms	504 KiB

sculpture

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll MAXBIT = 45;
const ll INF = 1e18;

ll N, X, Y, A[2005], dp[2005], ans;
bool dp2[105][105];

bool in(ll x, ll y) { return (x | y) == x; }
bool chk(ll x) {
	if(X > 1) {
		memset(dp2, 0, sizeof(dp2));
		dp2[0][0] = 1;
		for(int i=1; i<=N; i++) {
			ll sum = 0;
			for(int j=i; j<=N; j++) {
				sum += A[j];
				if(in(x, sum)) for(int k=1; k<=Y; k++) dp2[k][j] |= dp2[k-1][i-1];
			}
		}
		for(int i=X; i<=Y; i++) if(dp2[i][N]) return 1;
		return 0;
	}
	for(int i=1; i<=N; i++) dp[i] = INF;
	for(int i=1; i<=N; i++) {
		ll sum = 0;
		for(int j=i; j<=N; j++) {
			sum += A[j];
			if(in(x, sum)) dp[j] = min(dp[j], dp[i-1] + 1);
		}
	}
	return dp[N] <= Y;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> X >> Y;
	for(int i=1; i<=N; i++) cin >> A[i];
	ans = (1LL << MAXBIT) - 1;
	for(ll i=MAXBIT-1; i>=0; i--) if(chk(ans - (1LL << i))) ans -= (1LL << i);
	cout << ans;
}

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