#1197759 (C++23) No.705 ゴミ拾い Hard

• 問題: No.705 ゴミ拾い Hard
• ユーザー: drken1215
• 提出日時: 2026-11-08 18:53:20
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 253 ms / 1,500 ms
• コード長: 3,893 bytes
• コンパイル時間: 2,569 ms
• コンパイル使用メモリ: 344,612 KB
• 実行使用メモリ: 19,832 KB
• 最終ジャッジ日時: 2026-11-08 18:53:32
• 合計ジャッジ時間: 9,897 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 4
other	AC * 40

ソースコード

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

#line 2 "https://drken1215.github.io/algorithm/Optimization/dd_monotone_minima.hpp.html"
#include <bits/stdc++.h>
#line 4 "https://drken1215.github.io/algorithm/Optimization/dd_monotone_minima.hpp.html"
using namespace std;

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

// find min_j f(i, j) for all i, by Monotone Minima, O(H + W log H)
// f(i, j) must be monotone (argmin is not decreasing)
// slide access OK
template<class VAL, class FUNC> void MonotoneMinimaRec
(int HL, int HR, int WL, int WR, const FUNC &f, vector<pair<VAL, int>> &res) {
    if (HR - HL <= 0) return;
    int HM = (HL + HR) / 2;
    res[HM].second = WL;
    for (int i = WL; i < WR; i++) {
        VAL val = f(HM, i);
        if (res[HM].first > val) res[HM] = make_pair(val, i);
    }
    MonotoneMinimaRec(HL, HM, WL, res[HM].second + 1, f, res);
    MonotoneMinimaRec(HM + 1, HR, res[HM].second, WR, f, res);
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MonotoneMinima(int H, int W, const FUNC &f) {
    vector<pair<VAL, int>> res(H, make_pair(numeric_limits<VAL>::max() / 2, -1));
    MonotoneMinimaRec(0, H, 0, W, f, res);
    return res;
}
#line 7 "https://drken1215.github.io/algorithm/Optimization/dd_monotone_minima.hpp.html"

// find shortest path on DAG by D&D Monotone Minima, O(N (log N)^2)
// vertex: 0, 1, 2, ..., N
// A(j, i) = dp[i] + f(i, j) must be monotone (argmin is not decreasing)
// Attention: Even if f is monotone, A is not necessarily monotone
// slide access OK
template<class VAL> struct DDMonotoneMinima {
    VAL INF = numeric_limits<VAL>::max() / 2;
    int CNT_INF = numeric_limits<int>::max() / 2;

    // results
    vector<VAL> dp;
    vector<int> cnt, prev;

    // solver
    template<class FUNC> vector<pair<VAL, int>> solve(int N, const FUNC &f) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;
        vector<pair<VAL, int>> res(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
        res[0].first = VAL(0);
        auto f2 = [&](int i, int j) -> VAL { return res[j].first + f(j, i); };
        auto rec = [&](auto &&rec, int left, int right) -> void {
            if (right - left <= 1) return;
            int mid = (left + right) / 2;
            rec(rec, left, mid);
            MonotoneMinimaRec(mid, right, left, mid, f2, res);
            rec(rec, mid, right);
        };
        rec(rec, 0, N + 1);
        for (int r = 1; r <= N; r++) {
            dp[r] = res[r].first;
            prev[r] = res[r].second;
            if (prev[r] != -1) cnt[r] = cnt[prev[r]] + 1;
        }
        return res;
    }

    // reconstruct the shortest path
    vector<int> reconstruct() {
        int N = (int)dp.size() - 1;
        vector<int> path;
        for (int v = N; v > 0; v = prev[v]) path.emplace_back(v);
        path.emplace_back(0);
        reverse(path.begin(), path.end());
        return path;
    }
};
#line 4 "test.cpp"

// yukicoder No.705 ゴミ拾い Hard
/*
    A, X, Y: N 個
    これらを区間に分割していく
    　dp[j] = min_{0 ≦ i < j}(dp[i] + |A[j-1] - X[i]|^3 + |-Y[i]|^3)
    i -> j のコスト：|A[j-1] - X[i]|^3 + |-Y[i]|^3 ...... 差の凸関数 (Monge) + 縞々 (Monge) -> Monge
    スタート: 0, ゴール: N
*/
int main() {
    int N;
    cin >> N;
    vector<long long> A(N), X(N), Y(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < N; i++) cin >> Y[i];
    auto func = [&](int i, int j) -> long long {
        long long dx = abs(A[j-1] - X[i]), dy = abs(Y[i]);
        return dx * dx * dx + dy * dy * dy;
    };
    DDMonotoneMinima<long long> opt;
    auto res = opt.solve(N, func);
    cout << res[N].first << endl;
}