#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#define pb push_back
#define __V vector
#define all(x) x.begin(), x.end()
#define oit ostream_iterator
#define mod M
using namespace std;
void doin() {
cin.tie();
cout.tie();
ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
in >> a.first >> a.second;
return in;
}
template<typename T>
void getv(T& i) {
cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
v.resize(n);
for (auto& i : v)
getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
v.resize(n + 1);
for (int i = 1; i <= n; i++)
getv(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &x) {
while (x = getchar_unlocked(), x < 33) {
;
}
}
inline void getstr(string &str) {
str.clear();
char cur;
while (cur = getchar_unlocked(), cur < 33) {
;
}
while (cur > 32) {
str += cur;
cur = getchar_unlocked();
}
}
template<typename T> inline bool sc(T &num) {
bool neg = 0;
int c;
num = 0;
while (c = getchar_unlocked(), c < 33) {
if (c == EOF)
return false;
}
if (c == '-') {
neg = 1;
c = getchar_unlocked();
}
for (; c > 47; c = getchar_unlocked())
num = num * 10 + c - 48;
if (neg)
num *= -1;
return true;
}
typedef unsigned long long ull;
typedef long long ll;
typedef float ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
uniform_real_distribution<double> double_dist(0, 1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, A, B;
ll dp[101][101];
vi a, pref;
ll solve(int k) {
for (int i = 0; i <= n; i++) {
for (int p = 0; p <= B; p++) {
dp[i][p] = LLONG_MAX;
}
}
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int p = 0; p < B; p++) {
for (int ni = i + 1; ni <= n; ni++) {
ll sum = (pref[ni - 1] - (i ? pref[i - 1] : 0));
if(sum >= (1ll<<k)) break;
dp[ni][p+1] = min(dp[ni][p+1], dp[i][p]|sum);
}
}
}
ll ans = LLONG_MAX;
for (int c = A; c <= B; c++) {
ans = min(ans, dp[n][c]);
}
return ans;
}
int main() {
doin();
cin >> n >> A >> B;
getv(a, n);
pref.resize(n);
pref[0] = a[0];
for (int i = 1; i < n; i++)
pref[i] = a[i] + pref[i - 1];
ll ans = LLONG_MAX;
for(int a = 1; (1ll<<a) <= pref.back(); a++)
ans = min(ans, solve(a));
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
