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

• 問題: No.705 ゴミ拾い Hard
• ユーザー: drken1215
• 提出日時: 2026-11-11 09:01:11
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 11,505 bytes
• コンパイル時間: 2,590 ms
• コンパイル使用メモリ: 351,848 KB
• 実行使用メモリ: 34,328 KB
• 最終ジャッジ日時: 2026-11-11 09:01:23
• 合計ジャッジ時間: 9,942 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge1_0

ファイルパターン	結果
sample	AC * 3 WA * 1
other	AC * 11 WA * 29

ソースコード

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

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

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

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

// General Li-Chao Tree (Dynamic ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
    struct Node {
        int id = -1;  // function id
        Node *left = nullptr, *right = nullptr;
    };
    
    // inner values using chunk-based memory pool
    vector<unique_ptr<Node[]>> blocks;
    vector<FUNC> funcs;
    Node *root = nullptr;
    X XL, XR;
    VAL INF = numeric_limits<VAL>::max() / 2;
    
    // constructors
    explicit DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2)
    : XL(xl), XR(xr), INF(inf) {
        assert(xl < xr);
    }

    // basic functions
    void reserve_functions(size_t n) {
        funcs.reserve(n);
    }
    VAL eval(int id, X x) const {
        return funcs[id](x);
    }
    bool better(int fid, int gid, X x) const {
        VAL a = eval(fid, x), b = eval(gid, x);
        return (a < b) || (a == b && fid < gid);
    }
    void clear() {
        funcs.clear();
        blocks.clear();
        used = BLOCK;
        root = nullptr;
    }

    // insert(f), in O(log X)
    int insert(FUNC f) {
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        insert_at(root, XL, XR, id);
        return id;
    }

    // insert_segment(l, r, f), in O(log^2 X)
    int insert_segment(FUNC f, X l, X r) {
        assert(XL <= l && l <= r && r <= XR);
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (l != r) insert_segment_at(root, XL, XR, l, r, id);
        return id;
    }

    // query(x), in O(log X)
    pair<VAL, int> query(X x) const {
        assert(XL <= x && x < XR);
        VAL best = INF;
        int best_id = -1;
        Node *p = root;
        X left = XL, right = XR;
        while (p) {
            if (p->id != -1) {
                int fid = p->id;
                VAL y = eval(fid, x);
                if (best_id == -1 || y < best || (y == best && fid < best_id)) {
                    best = y, best_id = fid;
                }
            }
            if (right - left == 1) break;
            X mid = (left + right) / 2;
            if (x < mid) p = p->left, right = mid;
            else p = p->right, left = mid;
        }
        return {best, best_id};
    }

private:
    // chunk-based node allocation
    static constexpr int BLOCK = 4096;
    int used = BLOCK;
    Node *new_node() {
        if (used == BLOCK) {
            blocks.emplace_back(make_unique<Node[]>(BLOCK));
            used = 0;
        }
        return &blocks.back()[used++];
    }

    // inner insert
    void insert_at(Node *&p, X left, X right, int fid) {
        Node **cur = &p;
        while (true) {
            if (!*cur) *cur = new_node();
            Node *v = *cur;
            int gid = v->id;
            if (gid == -1) {
                v->id = fid;
                return;
            }
            bool left_better = better(fid, gid, left), right_better = better(fid, gid, right - 1);
            if (!left_better && !right_better) return;
            if (left_better && right_better) {
                v->id = fid;
                return;
            }
            X mid = (left + right) / 2;
            bool mid_better = better(fid, gid, mid);
            if (mid_better) v->id = fid, fid = gid;
            if (left_better != mid_better) cur = &v->left, right = mid;
            else cur = &v->right, left = mid;
        }
    }

    // inner insert_segment
    void insert_segment_at(Node *&p, X left, X right, X l, X r, int fid) {
        if (r <= left || right <= l) return;
        if (l <= left && right <= r) {
            insert_at(p, left, right, fid);
            return;
        }
        if (!p) p = new_node();
        X mid = (left + right) / 2;
        if (l < mid) insert_segment_at(p->left, left, mid, l, r, fid);
        if (mid < r) insert_segment_at(p->right, mid, right, l, r, fid);
    }
};

// General Li-Chao Tree (static ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct GeneralLiChaoTree {
    // inner values
    int N, siz;
    bool compressed = true;
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<X> xs;
    vector<int> ids;
    vector<FUNC> funcs;

    // constructors
    explicit GeneralLiChaoTree(vector<X> xs_, VAL inf = numeric_limits<VAL>::max() / 2, bool sorted = true) 
    : compressed(true), INF(inf), xs(std::move(xs_)) {
        if (!sorted) {
            sort(xs.begin(), xs.end());
            xs.erase(unique(xs.begin(), xs.end()), xs.end());
        }
        N = (int)xs.size();
        siz = 1;
        while (siz < N) siz <<= 1;
        ids.assign(siz << 1, -1);
    }
    explicit GeneralLiChaoTree(int n, VAL inf = numeric_limits<VAL>::max() / 2) 
    : N(n), siz(1), compressed(false), INF(inf) {
        assert(n >= 0);
        while (siz < N) siz <<= 1;
        ids.assign(siz << 1, -1);
    }

    // basic functions
    void reserve_functions(size_t n) {
        funcs.reserve(n);
    }
    VAL eval(int id, X x) const {
        return funcs[id](x);
    }
    bool better(int fid, int gid, X x) const {
        VAL a = eval(fid, x), b = eval(gid, x);
        return (a < b) || (a == b && fid < gid);
    }
    void clear() {
        funcs.clear();
        fill(ids.begin(), ids.end(), -1);
    }

    // insert(f), in O(log N)
    int insert(FUNC f) {
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (N) insert_at(1, 0, siz, id);
        return id;
    }

    // insert_segment(f, l, r), in O(log^2 N)
    int insert_segment(FUNC f, X l, X r) {
        assert(l <= r);
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (N == 0 || l == r) return id;
        int L = lower_bound_index(l);
        int R = lower_bound_index(r);
        if (L == R) return id;

        int a = L + siz, b = R + siz;
        while (a < b) {
            if (a & 1) {
                int v = a++;
                int depth = 31 - __builtin_clz((unsigned)v);
                int length = siz >> depth;
                int left = (v - (1 << depth)) * length;
                insert_at(v, left, left + length, id);
            }
            if (b & 1) {
                int v = --b;
                int depth = 31 - __builtin_clz((unsigned)v);
                int length = siz >> depth;
                int left = (v - (1 << depth)) * length;
                insert_at(v, left, left + length, id);
            }
            a >>= 1, b >>= 1;
        }
        return id;
    }

    // query(x), x must be in xs, in O(log N)
    pair<VAL, int> query(X x) const {
        int pos = 0;
        if (compressed) {
            auto it = lower_bound(xs.begin(), xs.end(), x);
            assert(it != xs.end() && *it == x);
            pos = int(it - xs.begin());
        } else {
            assert(X(0) <= x && x < X(N));
            pos = int(x);
        }
        VAL best = INF;
        int best_id = -1;
        int v = pos + siz;
        while (v) {
            int fid = ids[v];
            if (fid != -1) {
                VAL y = eval(fid, x);
                if (best_id == -1 || y < best || (y == best && fid < best_id)) {
                    best = y, best_id = fid;
                }
            }
            v >>= 1;
        }
        return {best, best_id};
    }

private:
    // coordinate compression
    int lower_bound_index(X x) const {
        if (compressed) {
            return int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        } else {
            if (x <= X(0)) return 0;
            else if (x >= X(N)) return N;
            else return int(x);
        }
    }

    // inner insert
    void insert_at(int v, int left, int right, int fid) {
        auto coord = [&](int i) -> X { 
            i = min(i, N - 1);
            return (compressed ? xs[i] : X(i));
        };
        while (true) {
            int gid = ids[v];
            if (gid == -1) {
                ids[v] = fid;
                return;
            }
            bool left_better = better(fid, gid, coord(left));
            bool right_better = better(fid, gid, coord(right - 1));
            if (!left_better && !right_better) return;
            if (left_better && right_better) {
                ids[v] = fid;
                return;
            }
            X mid = (left + right) / 2;
            bool mid_better = better(fid, gid, coord(mid));
            if (mid_better) ids[v] = fid, fid = gid;
            if (left_better != mid_better) {
                v <<= 1;
                right = mid;
            } else {
                v = v << 1 | 1;
                left = mid;
            }
        }
    }
};
#line 7 "https://drken1215.github.io/algorithm/Optimization/monge_shortest_path_by_cht.hpp.html"

// find shortest path on DAG with Pairwise Single Crossing cost, by Li Chao Tree, O(N log N)
// vertex: 0, 1, 2, ..., N
// A(j, i) = dp[i] + f(i, j) must be Pairwise Single Crossing (must be in all 0 <= i, j <= N, including i >= j)
// Attention: Even if f is Pairwise Single Crossing, A is not necessarily Pairwise Single Crossing
// edges: (i, j), j >= start[i] (i + 1 <= start[i] <= N + 1), start is non-decreasing
template<class VAL, class FUNC> vector<pair<VAL, int>> MongeShortestPathByCHT(int N, const FUNC &f, const vector<int> &start) {
    assert((int)start.size() == N);
    for (int i = 0; i < N; i++) {
        assert(i + 1 <= start[i] && start[i] <= N + 1);
        if (i > 0) assert(start[i - 1] <= start[i]);
    }
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<pair<VAL, int>> dp(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
    auto make_func = [&](int i) {
        return [&, i](long long j) -> VAL { return dp[i].first + f(i, j); };
    };
    GeneralLiChaoTree<VAL, decltype(make_func(0))> cht(N + 1, INF);
    dp[0].first = 0;
    int i = 0;
    for (int j = 1; j <= N; j++) {
        while (i < N && j >= start[i]) {
            cht.insert(make_func(i));
            i++;
        }
        dp[j] = cht.query(j);
    };
    return dp;
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MongeShortestPathByCHT(int N, const FUNC &f) {
    vector<int> start(N);
    for (int i = 0; i < N; i++) start[i] = i + 1;
    return MongeShortestPathByCHT<VAL>(N, f, start);
}
#line 7 "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 = MongeShortestPathByCHT<long long>(N, func);
    cout << res[N].first << endl;
}