oj.uz

Submission #463889

# Submission time Handle Problem Language Result Execution time Memory
463889 2021-08-12T01:09:06 Z Hamed5001 Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mxN = 2e3+10;
int dp1[mxN], dp2[mxN][mxN];
int N, A, B;
int Y[mxN];
ll msk, ans;

int fun2(int idx, int grp) {
	if (grp > B)
		return 0;
	if (idx == N)
		return (A <= grp && grp <= B);

	int &ret = dp2[idx][grp];
	if (~ret) return ret;

	ret = 0;
	ll sum = 0;
	for (int i = idx; i < N; ++i) {
		sum += Y[i];
		if (!(sum & msk))
			ret |= fun2(i+1, grp+1);
	}

	return ret;
}

int fun1(int idx) {
	if (idx == N)
		return 0;
	int &ret = dp1[idx];
	if (~ret) return ret;
	ret = 1e9;
	ll sum = 0;
	for (int i = idx; i < N; ++i) {
		sum += Y[i];
		if (!(sum & msk))
			ret = min(ret, fun1(i+1));
	}
	return ret + 1;
}

bool check2() {
	memset(dp2, -1, sizeof dp2);
	return fun2(0, 0);
}

bool check1() {
	memset(dp1, -1, sizeof dp1);
	return fun1(0) <= B;
}

void solve1() {
	for (int bit = 50; bit >= 0; --bit) {
		msk |= (1LL << bit);
		if (!check1())
			msk ^= (1LL << bit), ans |= (1LL << bit);
	}
	cout << ans << endl;
}

void solve2() {
	for (int bit = 50; bit >= 0; --bit) {
		msk |= (1LL << bit);
		if (!check2())
			msk ^= (1LL << bit), ans |= (1LL << bit);
	}
	cout << ans << endl;
}

void solve() {
	cin >> N >> A >> B;
	for (int i = 0; i < N; ++i)
		cin >> Y[i];
	if (A == 1) {
		solve1();
	}
	else {
		solve2();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 0 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -