| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1115619 | gdragon | Gondola (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
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 TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 1e5 + 5;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
int n, A, B;
vector<long long> f;
long long a[N];
void read() {
cin >> n >> A >> B;
f.assign(n + 1, 0);
for(int i = 1; i <= n; i++) {
cin >> f[i];
a[i] = f[i];
f[i] += f[i - 1];
}
}
long long sum(int l, int r) {
return f[r] - f[l - 1];
}
void sub1() {
int m = n - 1;
long long ans = INF;
for(int mask = 0; mask < MASK(m); mask++) {
if (CNTBIT(mask) + 1 > B || CNTBIT(mask) + 1 < A) continue;
int pre = 1;
long long res = 0;
for(int i = 1; i < n; i++) if (GETBIT(mask, i - 1)) {
res |= sum(pre, i);
pre = i + 1;
}
res |= sum(pre, n);
ans = min(ans, res);
}
cout << ans;
}
void sub3() {
vector<vector<vector<long long>>> dp(n + 2, vector<vector<long long>>(B + 2));
dp[0][0].push_back(0);
for(int i = 1; i <= n; i++) {
for(int k = 1; k <= min(i, B); k++) {
long long x = 0;
for(int j = i; j >= 1; j--) {
x += a[j];
long long mn1 = INF, mn2 = INF, mn3 = INF;
for(long long z: dp[j - 1][k - 1]) {
long long tmp = (x | z);
if (mn1 > tmp) {
mn3 = mn2;
mn2 = mn1;
mn1 = tmp;
}
else if (mn2 > tmp) {
mn3 = mn2;
mn2 = tmp;
}
else minimize(mn3, tmp);
}
if (mn1 != INF) dp[i][k].push_back(mn1);
if (mn2 != INF) dp[i][k].push_back(mn2);
if (mn3 != INF) dp[i][k].push_back(mn3);
}
}
}
long long ans = INF;
for(int k = A; k <= B; k++) {
for(long long x: dp[n][k]) ans = min(ans, x);
}
cout << ans;
}
const int NUMBIT = 41;
bool compare(long long mask1, long long mask2, int x) {
for(int i = NUMBIT; i >= x; i--) if (!GETBIT(mask1, i)) {
if (GETBIT(mask2, i)) return false;
}
return true;
}
bool setZero1(long long cur, int bit) {
const pair<long long, long long> inf = mp(INF, INF);
vector<pair<long long, long long>> dp(n + 2, inf);
// dp[0][0] = {0, 0};
dp[0] = {0, 0}; // (group, sumOr)
for(int i = 1; i <= n; i++) {
long long val = 0;
for(int j = i; j >= 1; j--) {
val += a[j];
if (dp[j - 1] == inf) continue;
if (compare(cur, (dp[j - 1].se | val), bit)) {
minimize(dp[i], mp(dp[j - 1].fi + 1, dp[j - 1].se | val));
}
}
}
if (dp[n] == inf) return false;
if (dp[n].fi < A || dp[n].fi > B) return false;
return true;
}
bool setZero0(long long cur, int bit) {
vector<vector<long long>> dp(n + 2, vector<long long>(B + 2, INF));
dp[0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int k = 1; k <= min(i, B); k++) {
long long val = 0;
for(int j = i; j >= 1; j--) {
val += a[j];
if (dp[j - 1][k - 1] == INF) continue;
if (compare(cur, (dp[j - 1][k - 1] | val), bit)) {
minimize(dp[i][k], dp[j - 1][k - 1] | val);
}
}
}
}
for(int k = A; k <= B; k++) if (dp[n][k] < INF) return true;
return false;
}
void sub4() {
long long cur = 0;
for(int i = 0; i <= NUMBIT; i++) cur |= MASK(i);
for(int i = NUMBIT; i >= 0; i--) {
cur ^= MASK(i);
if (A > 1) {
if (!setZero0(cur, i)) cur |= MASK(i);
}
else {
if (!setZero1(cur, i)) cur |= MASK(i);
}
}
cout << cur << endl;
}
void solve() {
sub4(); return;
if (n <= 20) {
sub1();
return;
}
else {
sub3();
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// cerr << (1082353817592 | 53288572918018395) << endl;
int test = 1;
// cin >> test;
while(test--) {
read();
solve();
}
return 0;
}