結果
| 問題 |
No.2423 Merge Stones
|
| コンテスト | |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2023-08-12 15:06:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,931 bytes |
| コンパイル時間 | 2,139 ms |
| コンパイル使用メモリ | 208,644 KB |
| 最終ジャッジ日時 | 2025-02-16 05:42:35 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 36 WA * 36 |
ソースコード
#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 2 "template.cpp"
#pragma region templates
#pragma region std::vector operator
template <class T>
std::vector<T> &operator++(std::vector<T> &v) {
for (auto &e : v) {
++e;
}
return v;
}
template <class T>
std::vector<T> operator++(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) {
++e;
}
return res;
}
template <class T>
std::vector<T> &operator--(std::vector<T> &v) {
for (auto &e : v) {
--e;
}
return v;
}
template <class T>
std::vector<T> operator--(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) {
--e;
}
return res;
}
#pragma endregion
#pragma region ios
namespace scanner {
namespace submodule {
void read(int &a) {
std::cin >> a;
}
void read(long long &a) {
std::cin >> a;
}
void read(char &a) {
std::cin >> a;
}
void read(double &a) {
std::cin >> a;
}
void read(std::string &a) {
std::cin >> a;
}
template <class T, class S>
void read(std::pair<T, S> &p) {
read(p.first);
read(p.second);
}
template <class T>
void read(std::vector<T> &);
template <class T>
void read(std::vector<T> &a) {
for (auto &e : a) {
read(e);
}
}
template <class T>
void read(T &a) {
std::cin >> a;
}
} // namespace submodule
void scan() {}
template <class Head, class... Tail>
void scan(Head &head, Tail &...tail) {
submodule::read(head);
scan(tail...);
}
void scanI() {}
template <class Head, class... Tail>
void scanI(Head &head, Tail &...tail) {
submodule::read(head);
--head;
scanI(tail...);
}
} // namespace scanner
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> pa) {
os << '{' << pa.first << ", " << pa.second << '}';
return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> vec) {
os << "{";
const int n = (int)vec.size();
for (int i = 0; i < n; i++) {
os << vec[i];
os << (i == n - 1 ? "}" : ", ");
}
return os;
}
template <class T, std::size_t S>
std::ostream &operator<<(std::ostream &os, std::array<T, S> arr) {
os << "{";
for (int i = 0; i < (int)S; i++) {
os << arr[i];
os << (i == S - 1 ? "}" : ", ");
}
os << "}";
return os;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::map<T, U> ma) {
os << "{";
auto itr = ma.begin();
while (itr != ma.end()) {
os << *itr << (itr == --ma.end() ? "}" : ", ");
++itr;
}
return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> st) {
os << "{";
auto itr = st.begin();
while (itr != st.end()) {
os << *itr << (itr == --st.end() ? "}" : ", ");
++itr;
}
return os;
}
namespace printer {
void print() {
std::cout << '\n';
}
template <class Head, class... Tail>
void print(const Head &head, const Tail &...tail) {
std::cout << head;
if (sizeof...(tail))
std::cout << ' ';
print(tail...);
}
} // namespace printer
namespace dumper {
void dumpFunc() {
std::cerr << std::endl;
}
template <class Head, class... Tail>
void dumpFunc(Head &&head, Tail &&...tail) {
std::cerr << head;
if (sizeof...(Tail) == 0) {
std::cerr << ' ';
} else {
std::cerr << ", ";
}
dumpFunc(std::move(tail)...);
}
} // namespace dumper
#pragma endregion
#pragma region functions
template <class T>
constexpr int si(const T &c) {
return static_cast<int>(c.size());
}
template <class T>
constexpr bool afMin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
constexpr bool afMax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T = long long, class S>
constexpr T calcSum(const S &container) {
return std::accumulate(container.begin(), container.end(), static_cast<T>(0));
}
template <class T>
constexpr auto calcMin(const T &container) {
return *std::min_element(container.begin(), container.end());
}
template <class T>
constexpr auto calcMax(const T &container) {
return *std::max_element(container.begin(), container.end());
}
template <class T>
constexpr int lwbi(const T &container, const typename T::value_type &value) {
return static_cast<int>(std::distance(container.cbegin(), std::lower_bound(container.cbegin(), container.cend(), value)));
}
template <class T>
constexpr int upbi(const T &container, const typename T::value_type &value) {
return static_cast<int>(std::distance(container.cbegin(), std::upper_bound(container.cbegin(), container.cend(), value)));
}
template <class T>
auto makeVec(const int n, const T &value) {
return std::vector(n, value);
}
template <class... Args>
auto makeVec(const int n, Args... args) {
return std::vector(n, makeVec(args...));
}
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
while (abs(ok - ng) > 1) {
T mid = ok + ng >> 1;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template <class T, class F>
T binarySearchReal(T ok, T ng, const F &f, int iter = 80) {
while (iter--) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
#pragma endregion
#pragma region macros and vars
using namespace scanner;
using namespace printer;
using i64 = long long;
template <class T>
using Vec = std::vector<T>;
template <class T>
using PQ = std::priority_queue<T>;
template <class T>
using RPQ = std::priority_queue<T, std::vector<T>, std::greater<T>>;
std::mt19937 mtRand(std::random_device{}());
constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr std::array<std::pair<int, int>, 8> dxy8 = {
{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};
#define INT(...) \
int __VA_ARGS__; \
scan(__VA_ARGS__)
#define INTI(...) \
int __VA_ARGS__; \
scanI(__VA_ARGS__)
#define I64(...) \
i64 __VA_ARGS__; \
scan(__VA_ARGS__)
#define I64I(...) \
i64 __VA_ARGS__; \
scanI(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
scan(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
scan(__VA_ARGS__)
#define DOUBLE(...) \
double __VA_ARGS__; \
scan(__VA_ARGS__)
#define VEC(type, name, n) \
std::vector<type> name(n); \
scan(name)
#define VECI(type, name, n) \
std::vector<type> name(n); \
scanI(name)
#define VEC2(type, name1, name2, n) \
std::vector<type> name1(n), name2(n); \
for (int i = 0; i < n; i++) \
scan(name1[i], name2[i])
#define VEC2I(type, name1, name2, n) \
std::vector<type> name1(n), name2(n); \
for (int i = 0; i < n; i++) \
scanI(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, n) \
std::vector<type> name1(n), name2(n), name3(n); \
for (int i = 0; i < n; i++) \
scan(name1[i], name2[i], name3[i])
#define VEC3I(type, name1, name2, name3, n) \
std::vector<type> name1(n), name2(n), name3(n); \
for (int i = 0; i < n; i++) \
scanI(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, n) \
std::vector<type> name1(n), name2(n), name3(n), name4(n); \
for (int i = 0; i < n; i++) \
scan(name1[i], name2[i], name3[i], name4[i]);
#define VEC4I(type, name1, name2, name3, name4, n) \
std::vector<type> name1(n), name2(n), name3(n), name4(n); \
for (int i = 0; i < n; i++) \
scanI(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w) \
std::vector<std::vector<type>> name(h, std::vector<type>(w)); \
scan(name)
#define VVI(type, name, h, w) \
std::vector<std::vector<type>> name(h, std::vector<type>(w)); \
scanI(name)
#define overload5(a, b, c, d, e, name, ...) name
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define fore0(a) rep (a.size())
#define fore1(i, a) for (auto &&i : a)
#define fore2(a, b, v) for (auto &&[a, b] : v)
#define fore3(a, b, c, v) for (auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define mp std::make_pair
#define ALL(x) (x).begin(), (x).end()
#define UNIQUE(x) (x).erase(std::unique((x).begin(), (x).end()), (x).end())
#define fi first
#define se second
#define dump(...) \
std::cerr << ' '; \
std::cerr << #__VA_ARGS__ << " : [" << __LINE__ << " : " << __FUNCTION__ << "]" << std::endl; \
std::cerr << " "; \
dumper::dumpFunc(__VA_ARGS__)
#pragma endregion
#pragma endregion
#line 4 "main.cpp"
struct MakeIOFast {
MakeIOFast() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(15);
}
} makeIOFastv;
using namespace std;
i64 op(i64 a, i64 b, int K) {
i64 c = 0;
for (int i = 0; i <= K; ++i) c |= (b << i);
for (int i = 0; i <= K; ++i) c |= (b >> i);
return a & c;
}
int main() {
INT(N, K);
VEC(i64, A, N);
VEC(int, C, N);
for (auto &e : C) --e;
vector X(N, vector(N, 0ll));
vector isUsed(N, vector(N, false));
auto sol = [&](auto &&self, const int l, const int r) -> void {
if (isUsed[l][r]) return;
if (l == r) {
X[l][l] = 1ll << C[l];
isUsed[l][l] = true;
return;
}
for (int m = (l + 1) % N; m != (r + 1) % N; m = (m + 1) % N) {
self(self, l, (m - 1 + N) % N);
self(self, m, r);
// dump(l, m, r);
int a = X[l][(m - 1 + N) % N];
int b = X[m][r];
X[l][r] |= op(a, b, K) | op(b, a, K);
}
isUsed[l][r] = true;
};
rep (i, 0, N) sol(sol, i, (i + N - 1) % N);
i64 ans = 0;
rep (l, 0, N) {
i64 sum = A[l];
for (int r = (l + 1) % N; r != l; r = (r + 1) % N) {
if (X[l][(r - 1 + N) % N] != 0) ans = max(ans, sum);
sum += A[r];
}
}
print(ans);
}