#include "bits/stdc++.h"
#pragma region cscpptemp
// require at least C++17 to compile
using llint = long long int;
template <class T>
using Heap = std::priority_queue<T>;
template <class T>
using RevHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// ex. for (const int i : range(a, b)) ... loop [a, b)
template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class range {
struct range_iterator {
T itr;
constexpr range_iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const range_iterator& other) const noexcept {
return itr != other.itr;
}
constexpr T operator*() const noexcept { return itr; }
};
public:
constexpr range(const T first_, const T last_) noexcept
: first(first_), last(last_) {}
constexpr range_iterator begin() const noexcept { return first; }
constexpr range_iterator end() const noexcept { return last; }
private:
const range_iterator first, last;
};
// ex. for (const int i : range(a, b)) ... revloop [a, b]
template <class T, class = std::enable_if_t<std::is_signed_v<T>>>
class revrange {
struct revrange_iterator {
T itr;
constexpr revrange_iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { --itr; }
constexpr bool operator!=(const revrange_iterator& other) const noexcept {
return itr != other.itr;
}
constexpr T operator*() const noexcept { return itr; }
};
public:
constexpr revrange(const T first_, const T last_) noexcept
: first(first_), last(last_ - 1) {}
constexpr revrange_iterator begin() const noexcept { return first; }
constexpr revrange_iterator end() const noexcept { return last; }
private:
const revrange_iterator first, last;
};
// ex. rec_lambda([](auto&& f, int n) -> int {return n < 1 ? 1 : f(--n); })
template <class F>
class rec_lambda {
public:
constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
template <class... Args>
constexpr auto operator()(Args&&... args) const {
return f(*this, std::forward<Args>(args)...);
}
private:
F f;
};
// ex. const int N = read()
struct read {
template <class T>
[[nodiscard]] operator T() {
T ret;
std::cin >> ret;
return ret;
}
};
// ex. chmax(a, b) ... a = max(a, b)
template <class T>
constexpr void chmax(T& a, const T b) noexcept {
if (a < b) a = b;
}
template <class T>
constexpr void chmin(T& a, const T b) noexcept {
if (a > b) a = b;
}
// ex. ceildiv(a, b) ... ceil(a / b)
template <class T, class = std::enable_if_t<std::is_integral_v<T>>>
constexpr T ceildiv(const T dividend, const T divisor) {
return (dividend + divisor - 1) / divisor;
}
// ex. mk_vec(a, b, c, v) ... 3D vector size: [a][b][c] init value: v
template <class T>
auto mk_vec(const int n, const T value) {
return std::vector(n, value);
}
template <class... Args>
auto mk_vec(const int n, Args... args) {
return std::vector(n, mk_vec(args...));
}
#pragma endregion
int main() {
const int N = read(), A = read(), B = read();
std::vector<llint> Y(N);
for (auto& el : Y) el = read();
std::vector<llint> R(N + 1);
R[0] = 0ll;
for (const int i : range(0, N)) R[i + 1] = R[i] + Y[i];
llint ans = 0ll, wal = 0ll;
for (const int bit : revrange(50, 0)) {
if (A == 1) {
std::vector<int> DP(N + 1, 1 << 30);
DP[0] = 0;
for (const int i : range(0, N))
for (const int j : range(0, i)) {
if (((R[i + 1] - R[j]) & wal + (1ll << bit)) == 0)
chmin(DP[i + 1], DP[j] + 1);
}
if (not(DP[N] <= B))
ans += 1ll << bit;
else
wal += 1ll << bit;
} else {
std::vector DP(N + 1, std::vector(N + 1, false));
DP[0][0] = true;
for (const int i : range(0, N))
for (const int j : range(0, i))
for (const int k : range(1, i + 1)) {
if (DP[i + 1][k]) continue;
if (((R[i + 1] - R[j]) & (wal + (1ll << bit))) == 0)
DP[i + 1][k] = DP[j][k - 1];
}
if (std::all_of(DP[N].begin() + A, DP[N].begin() + B + 1,
[](bool v) { return not v; }))
ans += 1ll << bit;
else
wal += 1ll << bit;
}
}
std::cout << ans << std::endl;
return 0;
}
Compilation message
sculpture.cpp:2: warning: ignoring #pragma region cscpptemp [-Wunknown-pragmas]
2 | #pragma region cscpptemp
|
sculpture.cpp:105: warning: ignoring #pragma endregion [-Wunknown-pragmas]
105 | #pragma endregion
|
sculpture.cpp: In function 'int main()':
sculpture.cpp:123:40: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
123 | if (((R[i + 1] - R[j]) & wal + (1ll << bit)) == 0)
| ~~~~^~~~~~~~~~~~~~
| # |
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 |
- |
