제출 #41439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41439		RockyB	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	533 ms	5100 KiB

sculpture

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)2000 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, A, B;
int a[N];

bool ok[N][N];

bool good(ll x, ll mask) {
	if (mask < (x | mask)) return 0;
	return 1;
}
bool dbg;


bitset <N> st[N];
bitset <N> lol;
bool check(ll mask) {
	memset(ok, 0, sizeof(ok));
	ok[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		st[i].reset();
		ll sum = 0;
		for (int j = i; j <= n; j++) {
			sum += a[j];
			if (good(sum, mask)) st[i][j] = 1;
		}
	}

	for (int id = 1; id <= B; id++) {
		lol.reset();
		for (int i = 0; i < n; i++) {
			if (ok[i][id - 1]) lol |= st[i + 1];
		}
		for (int i = 0; i <= n; i++) {
			if (lol[i]) ok[i][id] = 1;
		}
		if (id >= A && ok[n][id]) return 1;
	}
	return 0;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	ll mask = (1LL << 38) - 1;
	for (int i = 37; i >= 0; i--) {
		mask ^= 1LL << i;
		if (!check(mask)) {
			mask ^= 1LL << i;
		}
	}
	cout << mask;
	ioi
}

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