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

• 問題: No.705 ゴミ拾い Hard
• ユーザー: drken1215
• 提出日時: 2026-11-07 20:58:35
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 304 ms / 1,500 ms
• コード長: 3,742 bytes
• コンパイル時間: 2,573 ms
• コンパイル使用メモリ: 346,212 KB
• 実行使用メモリ: 23,220 KB
• 最終ジャッジ日時: 2026-11-07 20:58:49
• 合計ジャッジ時間: 13,081 ms
• ジャッジサーバーID （参考情報）: judge7_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_smawk.hpp.html"
#include <bits/stdc++.h>
#line 4 "https://drken1215.github.io/algorithm/Optimization/dd_smawk.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/dd_smawk.hpp.html"

// find shortest path on DAG by D&D SMAWK, O(N log N)
// vertex: 0, 1, 2, ..., N
// A(j, i) = dp[i] + f(i, j) must be totally monotone
// Attention: Even if f is totally monotone, A is not necessarily totally monotone
// slide access NG
template<class VAL, class FUNC> vector<pair<VAL, int>> DDSMAWK(int N, const FUNC &f) {
    vector<pair<VAL, int>> res(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
    vector<pair<VAL, int>> tmp(N + 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;
        vector<int> X(right - mid), Y(mid - left);
        for (int i = mid; i < right; i++) X[i - mid] = i;
        for (int j = left; j < mid; j++) Y[j - left] = j;
        rec(rec, left, mid);
        SMAWKRec(X, Y, f2, tmp);
        for (auto x : X) if (tmp[x].first < res[x].first) res[x] = tmp[x];
        rec(rec, mid, right);
    };
    rec(rec, 0, N + 1);
    return res;
}
#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;
    };
    auto res = DDSMAWK<long long>(N, func);
    cout << res[N].first << endl;
}