oj.uz

Submission #402858

# Submission time Handle Problem Language Result Execution time Memory
402858 2021-05-12T12:51:04 Z yoavL Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 204 KB 
#include <iostream>
#include <vector>
#include <algorithm>

#define upmax(a, b) a = max(a, b);
#define upmin(a, b) a = min(a, b);
#define pr(x) cout << x << endl;
#define wpr(x) cout << #x << ": " << x << endl;

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;

const ll bits = 32;
ll n, a, b;
vll arr;


inline bool check(ll bit, ll mask, ll x)
{
	mask >>= bit;
	x >>= bit;
	if ((mask ^ x) == 0) {
		return true;
	}
	return false;
}

bool check2(ll mask, ll bit)
{
	// dp[i][j] = is it possible to make it ok for mask with i first vals using j groups?	
	vvb dp(n + 1, vb(b+1, 0));
	dp[0][0] = 1;
	for (ll i = 0; i <= n; i++) {
		for (ll j = 0; j < b; j++) {
			if (!dp[i][j]) continue;
			ll csum = 0;
			for (ll k = i + 1; k <= n; k++) {
				csum += arr[k - 1];
				if (check(bit, mask, csum)) dp[k][j + 1] = 1;
			}
		}
	}
	/*
	if (bit <= 4) {
		wpr(bit);
		wpr(mask);
		pr("dp:");
		for (ll i = 0; i <= n; i++) {
			for (ll j = 0; j <= b; j++) {
				cout << dp[i][j] << " ";
			}
			cout << endl;
		}
	}
	*/
	for (ll j = a; j <= b; j++) {
		//pr(j);
		if (dp[n][j]) return true;
	}
	return false;
}


int main()
{
	cin >> n >> a >> b;
	arr.resize(n);
	for (ll i = 0; i < n; i++) cin >> arr[i];
	//ll mask = ((ll)1 << bits) - (ll)1;
	ll mask = 0;
	for (ll bit = bits - 1; bit >= 0; bit--) {
		//wpr(mask);
		//mask -= (ll)1 << bit;
		if (!check2(mask, bit)) mask += (ll)1 << bit;
		/*
		if (a == 1) {
			if (!check2(mask, bit)) mask += (ll)1 << bit;
		}
		else {
			if (!check2(mask, bit)) mask += (ll)1 << bit;
		}
		*/
		//wpr(mask);
	}
	pr(mask);
}

/*

6 1 3 
8 1 2 1 5 4


3 2 3
1 3 4

*/

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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