#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 inf = 1e18;
const ll maxn = 1026; // each one is smaller than 10. so sum is no more than 500. Which means maxn's last bit is no more than 1023.
const ll maxn2 = 2050;
const ll maxg = 21;
const ll bits = 32;
ll n, a, b;
vll arr;
ll ans;
vll s;
inline bool check(ll mask, ll bit, 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;
ll res = inf;
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(mask, bit, csum)) dp[k][j + 1] = 1;
}
}
}
for (ll j = a; j <= b; 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];
s.resize(n);
s[0] = arr[0];
for (ll i = 1; i < n; i++) s[i] = arr[i] + s[i - 1];
ans = inf;
ll mask = ((ll)1 << bits) - 1;
for (ll bit = bits - 1; bit >= 0; bit--) {
//wpr(mask);
mask -= (ll)1 << bit;
if (a == 1) {
if (!check2(mask, bit)) mask += (ll)1 << bit;
}
else {
if (!check2(mask, bit)) mask += (ll)1 << bit;
}
}
pr(mask);
}
/*
6 1 3
8 1 2 1 5 4
*/
Compilation message
sculpture.cpp: In function 'bool check2(ll, ll)':
sculpture.cpp:46:5: warning: unused variable 'res' [-Wunused-variable]
46 | ll res = inf;
| ^~~
| # |
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 |
- |
| # |
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 |
- |
| # |
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 |
- |
| # |
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 |
- |
| # |
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 |
- |
