Submission #39458

#	Time	Username	Problem	Language	Result	Execution time	Memory
39458		qoo2p5	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	149 ms	2224 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = 2005;
const int L = 42;

int n, a, b;
ll x[N], p[N];

ll get(int l, int r) {
	return p[r] - (l == 0 ? 0 : p[l - 1]);
}

namespace SmallN {
	const int SN = 105;
	bool dp[SN][SN];
	
	void solve() {
		ll ans = 0;
		ll deny = 0;
		
		per(bit, L, 0) {
			memset(dp, 0, sizeof dp);
			dp[0][0] = 1;
			deny |= (1LL << bit);
			rep(i, 0, n) {
				rep(cnt, 0, b) {
					if (!dp[i][cnt]) continue;
					
					rep(j, i, n) {
						ll s = get(i, j);
						if (s & deny) continue;
						
						dp[j + 1][cnt + 1] = 1;
					}
				}
			}
			
			bool ok = 0;
			rep(i, a, b + 1) ok |= dp[n][i];
			if (!ok) {
				deny ^= (1LL << bit);
				ans |= (1LL << bit);
			}
		}
		
		cout << ans << "\n";
	}
};

namespace LastGroup {
	int dp[N];
	
	void solve() {
		ll ans = 0;
		ll deny = 0;
		
		per(bit, L, 0) {
			fill(dp, dp + N, INF);
			dp[0] = 0;
			deny |= (1LL << bit);
			rep(i, 0, n) {
				rep(j, i, n) {
					ll s = get(i, j);
					if (s & deny) continue;
					mini(dp[j + 1], dp[i] + 1);
				}
			}
			
			bool ok = dp[n] <= b;
			if (!ok) {
				deny ^= (1LL << bit);
				ans |= (1LL << bit);
			}
		}
		
		cout << ans << "\n";
	}
};

void run() {
	cin >> n >> a >> b;
	rep(i, 0, n) {
		cin >> x[i];
	}
	partial_sum(x, x + n, p);
	
	if (n <= 100) {
		SmallN::solve();
	} else {
		LastGroup::solve();
	}
}

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