제출 #919608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919608		flappybird	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	92 ms	2392 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) {
		dp[1][1] = S[1];
		for (i = 2; i <= N; i++) {
			for (j = 2; j <= i; j++) dp[i][j] = INF;
			dp[i][1] = S[i];
			for (j = 1; j < i; j++) for (k = 1; k <= j; k++) dp[i][k + 1] = min(dp[i][k + 1], dp[j][k] | (S[i] - S[j]));
		}
		ll ans = INF;
		for (i = A; i <= B; i++) ans = min(ans, dp[N][i]);
		cout << ans << 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: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 29 / 29