tests/yukicoder_705_general_li_chao_tree.test.cpp

View this file on GitHub
Last update: 2026-11-04 14:46:41+09:00
Problem: https://yukicoder.me/problems/no/705

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/705"

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

#include "template.hpp"
#include "monge_shortest_path_by_cht.hpp"

// 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;
}

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

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

#line 3 "template.hpp"
using namespace std;

using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }

#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()

#line 3 "Others/io_for_contests.hpp"
using namespace std;

// input stream
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }

// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }

// Yes/No
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
#line 3 "Others/neighbors.hpp"
using namespace std;

// neighbors
const vector<int> DX = {1, 0, -1, 0, 1, -1, 1, -1};
const vector<int> DY = {0, 1, 0, -1, 1, -1, -1, 1};
#line 3 "Others/floor_ceil.hpp"
using namespace std;

// floor, ceil
template<class T> T floor(T a, T b) {
    if (a % b == 0 || a >= 0) return a / b;
    else return -((-a) / b) - 1;
}
template<class T> T ceil(T x, T y) {
    return floor(x + y - 1, y);
}
#line 3 "Optimization/binary_search.hpp"
using namespace std;

// binary search
template<class T, class FUNC> T binary_search_01(T ng, T ok, const FUNC &f) {
    while (abs(ok - ng) > 1) {
        T mid = ok + ng >> 1;
        if (f(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
template<class T, class FUNC> T binary_search_10(T ok, T ng, const FUNC &f) {
    return binary_search_01(ng, ok, f);
}
#line 48 "template.hpp"

// power of ten
const vector<i128> TEN = {
    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,
    10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL,
    1000000000000000LL, 10000000000000000LL, 100000000000000000LL, 1000000000000000000LL
};
template<class T = long long> T get_ten(int n) {
    assert(n >= 0);
    if (n <= 18) return T(TEN[n]);
    T res = TEN[18];
    for (int i = 0; i < n - 18; i++) res *= 10;
    return res;
}

// min non-negative i such that 2^i <= n
template<class T> T floor_pow2(T n) {
    T i = 0;
    while ((T(1) << (i + 1)) <= T(n)) i++;
    return i;
}

// min non-negative i such that n <= 2^i
template<class T> T ceil_pow2(T n) {
    T i = 0;
    while ((T(1) << i) < T(n)) i++;
    return i;
}

// num of i such that (x & (1 << i)) != 0
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(unsigned int x) { return __builtin_popcount(x); }
int popcnt(long long x) { return __builtin_popcountll(x); }
int popcnt(unsigned long long x) { return __builtin_popcountll(x); }

// min non-negative i such that (x & (1 << i)) != 0
int bsf(int x) { return __builtin_ctz(x); }
int bsf(unsigned int x) { return __builtin_ctz(x); }
int bsf(long long x) { return __builtin_ctzll(x); }
int bsf(unsigned long long x) { return __builtin_ctzll(x); }

// max non-negative i such that (x & (1 << i)) != 0
int bsr(int x) { return 8 * (int)sizeof(int) - 1 - __builtin_clz(x); }
int bsr(unsigned int x) { return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(x); }
int bsr(long long x) { return 8 * (int)sizeof(long long) - 1 - __builtin_clzll(x); }
int bsr(unsigned long long x) { return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(x); }

// compression
template<class T> vector<T> compress(const vector<T> &v) {
    auto alt = v;
    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    vector<T> res(v.size());
    for (int i = 0; i < res.size(); i++) {
        res[i] = lower_bound(alt.begin(), alt.end(), v[i]) - alt.begin();
    }
    return res;
}
template<typename T, typename... Ts>
vector<T> merge_and_unique(const vector<T> &a, const Ts &...z) {
    vector<T> res = a;
    (res.insert(res.end(), z.begin(), z.end()), ...);
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}
#line 4 "Optimization/monge_shortest_path_by_cht.hpp"
using namespace std;

#line 4 "Optimization/general_li_chao_tree.hpp"
using namespace std;


// Dynamic Li Chao Tree for Pairwise Single Crossing Functions
/*
    Func: Pairwise Single Crossing 性を仮定
    注意点：i < j なる領域だけでなく、全領域での Pairwise Single Crossing 性が必要！！！

    x 座標のとりうる値の範囲: [XL, XR)
*/
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
    using Func = function<VAL(X)>;
    struct IndexedFunc {
        Func f;
        int id;
        VAL eval(X x) const { return f(x); };
    };
    struct Node {
        optional<IndexedFunc> func;
        unique_ptr<Node> left, right;
    };
    
    // inner values
    X XL, XR;
    VAL INF = numeric_limits<VAL>::max() / 2;
    int next_id = 0;
    unique_ptr<Node> root;
    
    // constructors
    DynamicGeneralLiChaoTree() {}
    DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2) : XL(xl), XR(xr), INF(inf) {
        assert(xl < xr);
    }
    static bool better(const IndexedFunc &a, const IndexedFunc &b, X x) {
        return make_pair(a.eval(x), a.id) < make_pair(b.eval(x), b.id);
    }
    void clear() {
        root.reset();
        next_id = 0;
    }

    // insert(f), in O(log X)
    void insert(unique_ptr<Node> &p, X left, X right, IndexedFunc f) {
        if (!p) p = make_unique<Node>();
        if (!p->func) {
            p->func.emplace(f);
            return;
        }
        X mid = (left + right) / 2;
        bool left_better = better(f, *p->func, left);
        bool right_better = better(f, *p->func, right - 1);

        if (!left_better && !right_better) return;
        if (left_better && right_better) {
            p->func.emplace(f);
            return;
        }
        bool mid_better = better(f, *p->func, mid);
        if (mid_better) {
            IndexedFunc old = std::move(*p->func);
            p->func.emplace(f);
            if (left_better != mid_better) insert(p->left, left, mid, old);
            else insert(p->right, mid, right, old);
        } else {
            if (left_better != mid_better) insert(p->left, left, mid, f);
            else insert(p->right, mid, right, f);
        }
    }
    int insert(Func f) {
        int id = next_id++;
        insert(root, XL, XR, IndexedFunc{std::move(f), id});
        return id;
    }

    // insert_segment(l, r, f), in O(log^2 X)
    void insert_segment(unique_ptr<Node> &p, X left, X right, X l, X r, const IndexedFunc &f) {
        if (r <= left || right <= l) return;
        if (l <= left && right <= r) {
            insert(p, left, right, f);
            return;
        }
        if (!p) p = make_unique<Node>();
        X mid = (left + right) / 2;
        insert_segment(p->left, left, mid, l, r, f);
        insert_segment(p->right, mid, right, l, r, f);
    }
    int insert_segment(X l, X r, Func f) {
        assert(XL <= l && l <= r && r <= XR);
        int id = next_id++;
        if (l != r) insert_segment(root, XL, XR, l, r, IndexedFunc{std::move(f), id});
        return id;
    }

    // query(x), in O(log X)
    pair<VAL, int> query(X x) const {
        assert(XL <= x && x < XR);
        pair<VAL, int> res{INF, -1};
        const Node *p = root.get();
        X left = XL, right = XR;
        while (p) {
            if (p->func) {
                auto cur = make_pair(p->func->eval(x), p->func->id);
                if (res.second == -1 || cur < res) res = cur;
            }
            if (right - left == 1) break;
            X mid = (left + right) / 2;
            if (x < mid) {
                p = p->left.get();
                right = mid;
            } else {
                p = p->right.get();
                left = mid;
            }
        }
        return res;
    }
};

#line 7 "Optimization/monge_shortest_path_by_cht.hpp"

// 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); };
    };
    DynamicGeneralLiChaoTree<VAL, decltype(make_func(0))> cht(1, 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 8 "tests/yukicoder_705_general_li_chao_tree.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;
}