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 <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
int x, min_cap, max_cap;
int64_t arr[2005];
int64_t pfx[2005];
inline int64_t sum_query(int l, int r) {
return pfx[r] - ((l-1>=0) ? pfx[l-1] : 0);
}
bool can_solve(int64_t mask, int bit) {
if (min_cap==1) {
std::vector<int> dp(x, -1);
const std::function<int(int)> sol = [&](int pos) {
if (pos==x) return 0;
if (dp[pos]!=-1) return dp[pos];
int& ret = (dp[pos] = 0x3f3f3f3f);
for (int i = pos; i < x; i++) {
int64_t sum = sum_query(pos,i);
if (((mask>>bit)|(sum>>bit))==(mask>>bit)) {
ret = std::min(ret, 1+sol(i+1));
}
}
return ret;
};
return sol(0) <= max_cap;
}
else {
std::vector<std::vector<char>> dp(x, std::vector<char>(max_cap+1, -1));
const std::function<bool(int,int)> sol = [&](int pos, int k) {
if (pos==x) return min_cap <= k && k <= max_cap;
if (dp[pos][k]!=-1) return static_cast<bool>(dp[pos][k]);
char& ret = (dp[pos][k] = 0);
for (int i = pos; i < x; i++) {
int64_t sum = sum_query(pos,i);
if (((mask>>bit)|(sum>>bit))==(mask>>bit)) {
ret |= sol(i+1,k+1);
}
}
return static_cast<bool>(ret);
};
return sol(0,0);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> min_cap >> max_cap;
for (int i = 0; i < x; i++) {
std::cin >> arr[i];
pfx[i] = pfx[i-1] + arr[i];
}
int64_t ans = 0;
for (int bit = 60; bit >= 0; bit--) {
if (!can_solve(ans,bit)) {
ans |= (1LL<<bit);
}
}
std::cout << ans << "\n";
}
# | 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... |