#902895 (C++17) No.2423 Merge Stones

提出ソース

結果

問題	No.2423 Merge Stones
ユーザー	Cyanmond
提出日時	2023-08-12 15:08:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	544 ms / 4,000 ms
コード長	13,992 bytes
コンパイル時間	2,488 ms
コンパイル使用メモリ	215,176 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-19 23:51:09
合計ジャッジ時間	33,191 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	543 ms 5,248 KB
testcase_12	AC	301 ms 5,248 KB
testcase_13	AC	542 ms 5,248 KB
testcase_14	AC	417 ms 5,248 KB
testcase_15	AC	380 ms 5,248 KB
testcase_16	AC	515 ms 5,248 KB
testcase_17	AC	422 ms 5,248 KB
testcase_18	AC	509 ms 5,248 KB
testcase_19	AC	307 ms 5,248 KB
testcase_20	AC	429 ms 5,248 KB
testcase_21	AC	544 ms 5,248 KB
testcase_22	AC	424 ms 5,248 KB
testcase_23	AC	378 ms 5,248 KB
testcase_24	AC	377 ms 5,248 KB
testcase_25	AC	377 ms 5,248 KB
testcase_26	AC	377 ms 5,248 KB
testcase_27	AC	464 ms 5,248 KB
testcase_28	AC	543 ms 5,248 KB
testcase_29	AC	502 ms 5,248 KB
testcase_30	AC	417 ms 5,248 KB
testcase_31	AC	423 ms 5,248 KB
testcase_32	AC	542 ms 5,248 KB
testcase_33	AC	374 ms 5,248 KB
testcase_34	AC	465 ms 5,248 KB
testcase_35	AC	420 ms 5,248 KB
testcase_36	AC	419 ms 5,248 KB
testcase_37	AC	381 ms 5,248 KB
testcase_38	AC	380 ms 5,248 KB
testcase_39	AC	544 ms 5,248 KB
testcase_40	AC	539 ms 5,248 KB
testcase_41	AC	459 ms 5,248 KB
testcase_42	AC	531 ms 5,248 KB
testcase_43	AC	304 ms 5,248 KB
testcase_44	AC	535 ms 5,248 KB
testcase_45	AC	371 ms 5,248 KB
testcase_46	AC	462 ms 5,248 KB
testcase_47	AC	367 ms 5,248 KB
testcase_48	AC	373 ms 5,248 KB
testcase_49	AC	307 ms 5,248 KB
testcase_50	AC	303 ms 5,248 KB
testcase_51	AC	496 ms 5,248 KB
testcase_52	AC	494 ms 5,248 KB
testcase_53	AC	533 ms 5,248 KB
testcase_54	AC	496 ms 5,248 KB
testcase_55	AC	524 ms 5,248 KB
testcase_56	AC	486 ms 5,248 KB
testcase_57	AC	488 ms 5,248 KB
testcase_58	AC	532 ms 5,248 KB
testcase_59	AC	544 ms 5,248 KB
testcase_60	AC	496 ms 5,248 KB
testcase_61	AC	535 ms 5,248 KB
testcase_62	AC	531 ms 5,248 KB
testcase_63	AC	533 ms 5,248 KB
testcase_64	AC	526 ms 5,248 KB
testcase_65	AC	536 ms 5,248 KB
testcase_66	AC	527 ms 5,248 KB
testcase_67	AC	526 ms 5,248 KB
testcase_68	AC	538 ms 5,248 KB
testcase_69	AC	531 ms 5,248 KB
testcase_70	AC	529 ms 5,248 KB
testcase_71	AC	529 ms 5,248 KB
testcase_72	AC	529 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);

            i64 a = X[l][(m - 1 + N) % N];
            i64 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];
        }
        if (X[l][(l - 1 + N) % N] != 0) ans = max(ans, sum);
    }
    print(ans);
}

yukicoder

結果

テストケース

ソースコード