結果

問題 No.1536 仕切り直し
ユーザー sten_sansten_san
提出日時 2021-06-06 20:19:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,776 bytes
コンパイル時間 2,635 ms
コンパイル使用メモリ 220,148 KB
実行使用メモリ 115,456 KB
最終ジャッジ日時 2024-05-04 00:50:41
合計ジャッジ時間 4,507 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct iofast_t {
    iofast_t() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} iofast;

struct uns_t {} uns;
template <typename Element, typename Head, typename ...Args>
auto vec(Element init, Head arg, Args ...args) {
    if constexpr (sizeof...(Args) == 0) return std::vector(arg, init);
    else return std::vector(arg, vec(init, args...));
}
template <typename Element, typename Head, typename ...Args>
auto vec(uns_t, Head arg, Args ...args) {
    return vec(Element(), arg, args...);
}

template <typename T, typename Compare = less<T>>
T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); }
template <typename T, typename Compare = less<T>>
T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); }

int main() {
    constexpr int64_t inf = INT64_MAX / 4;
    constexpr auto inv = make_tuple(-1, -1, -1);

    int n, m; cin >> n >> m;
    auto a = vec<int>(uns, n);
    for (auto &e : a) cin >> e;
    reverse(begin(a), end(a));

    auto dp = vec<array<int64_t, 2>>({ +inf, -inf }, n + 1, m + 1);

    auto prev = vec<array<tuple<int, int, int>, 2>>(uns, n + 1, m + 1);

    for (int j = 0; j <= m; ++j) {
        dp[0][j][0] = dp[0][j][1] = 0;
        prev[0][j][0] = prev[0][j][1] = inv;
    }

    int64_t sum = 0;
    for (int i = 1; i <= n; ++i) {
        int c = a[i - 1]; sum += c;

        dp[i][0][0] = dp[i][0][1] = sum;
        prev[i][0][0] = prev[i][0][1] = inv;

        int64_t l0 = dp[i - 1][0][0], r0 = dp[i - 1][0][1];
        int64_t l1 = +inf, r1 = -inf;

        auto pl0 = make_tuple(i - 1, 0, 0);
        auto pr0 = make_tuple(i - 1, 0, 1);
        auto pl1 = inv;
        auto pr1 = inv;

        for (int j = 1; j <= m; ++j) {
            dp[i][j][0] = dp[i - 1][j][0] + c;
            dp[i][j][1] = dp[i - 1][j][1] + c;

            prev[i][j][0] = make_tuple(i - 1, j, 0);
            prev[i][j][1] = make_tuple(i - 1, j, 1);

            if (2 <= j) {
                if (j % 2 == 0) {
                    if (+l0 + c < dp[i][j][0]) {
                        prev[i][j][0] = pl0;
                    }
                    if (+r0 + c > dp[i][j][1]) {
                        prev[i][j][1] = pr0;
                    }

                    chmin(dp[i][j][0], +l0 + c);
                    chmax(dp[i][j][1], +r0 + c);
                }
                else {
                    if (+l1 + c < dp[i][j][0]) {
                        prev[i][j][0] = pl1;
                    }
                    if (+r1 + c > dp[i][j][1]) {
                        prev[i][j][1] = pr1;
                    }

                    chmin(dp[i][j][0], +l1 + c);
                    chmax(dp[i][j][1], +r1 + c);
                }
            }

            if (1 <= j) {
                if (j % 2 == 0) {
                    if (-r1 - c < dp[i][j][0]) {
                        prev[i][j][0] = pr1;
                    }
                    if (-l1 - c > dp[i][j][1]) {
                        prev[i][j][1] = pl1;
                    }

                    chmin(dp[i][j][0], -r1 - c);
                    chmax(dp[i][j][1], -l1 - c);
                }
                else {
                    if (-r0 - c < dp[i][j][0]) {
                        prev[i][j][0] = pr0;
                    }
                    if (-l0 - c > dp[i][j][1]) {
                        prev[i][j][1] = pl0;
                    }

                    chmin(dp[i][j][0], -r0 - c);
                    chmax(dp[i][j][1], -l0 - c);
                }
            }

            if (j % 2 == 0) {
                if (dp[i - 1][j][0] < l0) {
                    pl0 = make_tuple(i - 1, j, 0);
                }
                if (dp[i - 1][j][0] > r0) {
                    pr0 = make_tuple(i - 1, j, 1);
                }

                chmin(l0, dp[i - 1][j][0]);
                chmax(r0, dp[i - 1][j][1]);
            }
            else {
                if (dp[i - 1][j][0] < l1) {
                    pl1 = make_tuple(i - 1, j, 0);
                }
                if (dp[i - 1][j][0] > r1) {
                    pr1 = make_tuple(i - 1, j, 1);
                }

                chmin(l1, dp[i - 1][j][0]);
                chmax(r1, dp[i - 1][j][1]);
            }
        }
    }

    auto ans = vec<int>(uns, 0);

    auto solve = [&](auto &&self, int i, int j, int k) -> void {
        auto p = prev[i][j][k];

        if (p == inv) {
            while (j--) {
                ans.push_back(i);
            }
            return;
        }

        auto [pi, pj, pk] = p;

        if (pj < j) {
            ans.push_back(i);
        }

        self(self, pi, pj, pk);
    };

    solve(solve, n, m, 1);

    for (auto v : ans) {
        cout << n - v << endl;
    }
}
0