#1197643 (C++23) No.952 危険な火薬庫

• 問題: No.952 危険な火薬庫
• ユーザー: drken1215
• 提出日時: 2026-11-08 00:40:15
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 260 ms / 2,000 ms
• コード長: 3,429 bytes
• コンパイル時間: 2,497 ms
• コンパイル使用メモリ: 350,992 KB
• 実行使用メモリ: 9,900 KB
• 最終ジャッジ日時: 2026-11-08 00:40:24
• 合計ジャッジ時間: 8,360 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 26

ソースコード

#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/952"

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

#line 4 "https://drken1215.github.io/algorithm/Optimization/monge_enum_d_shortest_paths.hpp.html"
using namespace std;

#line 4 "https://drken1215.github.io/algorithm/Optimization/smawk.hpp.html"
using namespace std;

// find min_j f(i, j) for all i, by SMAWK, O(H + W)
// f(i, j) must be totally monotone
// slide access NG
template<class VAL, class FUNC> void SMAWKRec
(const vector<int> &X, const vector<int> &Y, const FUNC &f, vector<pair<VAL, int>> &res) {
    if (X.empty()) return;

    // Reduce Step
    vector<int> X2, Y2;
    for (auto y : Y) {
        while (!Y2.empty()) {
            int py = Y2.back(), x = X[(int)Y2.size() - 1];
            if (f(x, y) >= f(x, py)) break;
            Y2.pop_back();
        }
        if (Y2.size() < X.size()) Y2.emplace_back(y);
    }

    // Recurse Step
    for (int i = 1; i < (int)X.size(); i += 2) X2.emplace_back(X[i]);
    SMAWKRec(X2, Y2, f, res);

    // Interpolate Step
    int p = 0;
    for (int i = 0; i < (int)X.size(); i += 2) {
        int lim = (i + 1 < (int)X.size() ? res[X[i + 1]].second : Y.back()), best = Y[p];
        while (Y[p] < lim) {
            p++;
            if (f(X[i], Y[p]) < f(X[i], best)) best = Y[p];
        }
        res[X[i]] = {f(X[i], best), best};
    }
}
template<class VAL, class FUNC> vector<pair<VAL, int>> SMAWK(int H, int W, const FUNC &f) {
    if (H == 0) return {};
    assert(W > 0);
    vector<pair<VAL, int>> res(H, make_pair(numeric_limits<VAL>::max() / 2, -1));
    vector<int> X(H), Y(W);
    for (int i = 0; i < H; i++) X[i] = i;
    for (int j = 0; j < W; j++) Y[j] = j;
    SMAWKRec(X, Y, f, res);
    return res;
}
#line 7 "https://drken1215.github.io/algorithm/Optimization/monge_enum_d_shortest_paths.hpp.html"

// find the d-edges shortest path for d = 1, 2, ..., D, in O(ND)
// vertex: 0, 1, 2, ..., N
// f(i, j) must be Monge (Then, A(j, i) = dp[i] + f(i, j) is also Monge)
// you can choose SMAWK (random access) or Monotone Minima (slide access)
template<class VAL> struct MongeShortestPathWithDEdges {
    VAL INF = numeric_limits<VAL>::max() / 2;

    // solver
    template<class FUNC> vector<VAL> solve(int N, const FUNC &f, int D, const string &solver = "smawk") {
        assert(D <= N);
        vector<VAL> res{VAL(0)}, dp(N + 1, INF);
        dp[0] = 0;
        auto f2 = [&](int i, int j) -> VAL { return (j < i ? dp[j] + f(j, i) : INF); };
        for (int d = 1; d <= D; d++) {
            vector<pair<VAL, int>> tmp;
            if (solver == "smawk") tmp = SMAWK<VAL>(N + 1, N + 1, f2);
            for (int i = d; i <= N; i++) dp[i] = tmp[i].first;
            res.emplace_back(dp[N]);
        }
        return res;
    }
};
#line 7 "test.cpp"

// yukicoder No.952 危険な火薬庫
/*
    末尾にドアを追加する。
    ノード 0, 1, ..., N, N+1
    f(i, j) = (S[j-1] - S[i])^2
    選ぶドアが k 個 → 区間の個数は、N+1-k
*/
int main() {
    int N;
    cin >> N;
    vector<long long> A(N + 1, 0), S(N + 2, 0);
    for (int i = 0; i < N; i++) cin >> A[i], S[i + 1] = S[i] + A[i];
    auto f = [&](int i, int j) -> long long { 
        return (S[j - 1] - S[i]) * (S[j - 1] - S[i]);
    };
    MongeShortestPathWithDEdges<long long> msp;
    auto res = msp.solve(N + 1, f, N + 1);
    for (int k = 1; k <= N; k++) cout << res[N + 1 - k] << endl;
}