Submission #919625

#	Time	Username	Problem	Language	Result	Execution time	Memory
919625		flappybird	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	83 ms	2652 KiB

sculpture

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2020
#define MAXS 20
#define INF 1'000'000'100'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 998244353
#define TC 1
ll arr[MAX];
ll S[MAX];
ll dp[MAX][MAX];
int dis[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, A, B;
	cin >> N >> A >> B;
	int i, j, k;
	for (i = 1; i <= N; i++) cin >> arr[i], S[i] = S[i - 1] + arr[i];
	if (A > 1) {
		ll mask = 0;
		for (i = 50; i >= 0; i--) {
			ll nmask = mask | (1ll << i);
			for (j = 1; j <= N; j++) for (k = 1; k <= N; k++) dp[j][k] = 0;
			dp[0][0] = 1;
			for (j = 0; j <= N; j++) {
				for (k = j + 1; k <= N; k++) {
					if ((S[k] - S[j]) & nmask) continue;
					for (int x = 0; x <= N; x++) dp[k][x + 1] |= dp[j][x];
				}
			}
			int chk = 0;
			for (j = A; j <= B; j++) chk |= dp[N][j];
			if (chk) mask = nmask;
		}
		mask ^= ((1ll << 51) - 1);
		cout << mask << ln;
		return 0;
	}
	ll mask = 0;
	for (i = 50; i >= 0; i--) {
		ll nmask = mask | (1ll << i);
		for (j = 1; j <= N; j++) dis[j] = N + 100;
		for (j = 0; j <= N; j++) {
			if (dis[j] > N) continue;
			for (k = j + 1; k <= N; k++) {
				if ((S[k] - S[j]) & nmask) continue;
				dis[k] = min(dis[k], dis[j] + 1);
			}
		}
		if (dis[N] <= B) mask = nmask;
	}
	mask ^= ((1ll << 51) - 1);
	cout << mask << ln;
}

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