This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
/*
a <= x <= b subsegments
MINIMIZE bitwise or of sums
either n^2 and a=1 or n^3 and a is maybe not 1
st with a>=1:
can we iterate thru bits
the idea:
given previous restrictions on bits that have to be 0
(others can be 1 & are impossible to make 0)
can we make it good for this
for (i)
for (last i)
if the sum is good
for all dp[last_i][j] that are true, dp[i][j + 1] is true
complexity = n^2 * b * log(s)
st with a==1:
iterate thru sums bc only go up to like 2000
for each num find if you can have or <= num
by doing dp
bc a=1
can just track possible/not and min # of segments needed
at every ind
complexity = n^2 * log(s) ---> was gonna be max_s but turns out log(s) works
can this pass st5
if we binary search the maximum or
or do bit by bit
yeah
*/
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, a, b;
cin >> n >> a >> b;
vector<long long> s(n);
long long sum = 0;
for (int i = 0; i < n; i++) {
cin >> s[i];
sum += s[i];
}
long long p2 = 1ll, mxbit = 0;
while (p2 < sum) {
p2 <<= 1; mxbit++;
}
long long req = (1ll << (mxbit + 1)) - 1;
if (a == 1) {
for (int bit = mxbit; bit >= 0; bit--) {
req -= (1ll << bit);
vector<long long> best(n + 1, 1e9);
best[0] = 0;
for (int i = 1; i <= n; i++) {
long long lst = 0;
for (int j = i - 1; j >= 0; j--) {
lst += s[j];
if ((req | lst) == req) {
best[i] = min(best[i], best[j] + 1);
}
}
}
if (best[n] > b) {
req += (1ll << bit);
}
}
} else {
for (int bit = mxbit; bit >= 0; bit--) {
req -= (1ll << bit);
vector<vector<bool>> ok(n + 1, vector<bool>(b, false));
ok[0][0] = true;
for (int i = 1; i <= n; i++) {
long long lst = 0;
for (int j = i - 1; j >= 0; j--) {
lst += s[j];
if ((req | lst) == req) {
for (int k = 0; k < b; k++) {
if (ok[j][k]) {
ok[i][k + 1] = true;
}
}
}
}
bool good = false;
for (int i = a; i <= b; i++) {
if (ok[n][i]) {
good = true;
break;
}
}
if (!good) {
req += (1ll << bit);
}
}
}
}
cout << req << '\n';
}
/*
any observations help
check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER
NEVER GIVE UP
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |