test/algorithm/monge_3.test.cpp

View this file on GitHub
Last update: 2026-10-21 23:29:36+09:00
Problem: https://yukicoder.me/problems/no/705

Depends on

Code

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

#include "../../algorithm/monge_shortest_path.hpp"
#include <cstdlib>
#include <iostream>
#include <vector>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<long long> A(N), X(N), Y(N);
    for (auto &a : A) std::cin >> a;
    for (auto &x : X) std::cin >> x;
    for (auto &y : Y) std::cin >> y;

    auto cost = [&](int i, int j){
        long long dx = std::abs(A[j - 1] - X[i]);
        return dx * dx * dx + Y[i] * Y[i] * Y[i];
    };

    auto dp = po167::monge_shortest_path(N, cost);
    std::cout << dp.first[N] << "\n";
}

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

#line 2 "algorithm/monge_shortest_path.hpp"
// po167 Monge library v2: predecessor support (2026-10-21)
#include <cassert>
#include <utility>
#include <vector>
#line 2 "algorithm/larsch.hpp"
// po167 Monge library v2 (2026-10-21)
#line 6 "algorithm/larsch.hpp"

namespace po167 {
namespace detail {

// A[r][c] = value(r,c), 0 <= c <= r < n: Monge.
// r-th next_argmin() = min argmin_{0 <= c <= r} A[r][c].
// O(n) total time, O(n) space.
// https://noshi91.github.io/Library/algorithm/larsch.cpp.html (CC0)
template <class F>
class Larsch {
    struct Level {
        int n, row = 0, state = 0, size = 0;
        std::vector<int> column;
        Level(int n_, bool base) : n(n_), column(base ? 0 : n_) {}
    };
    F value;
    std::vector<Level> levels;

    int next_argmin(int depth) {
        auto& a = levels[depth];
        int row = a.row++, r = ((row + 1) << depth) - 1;
        auto column = [&](int j) { return depth ? a.column[j] : j; };
        int best = column(a.state);
        if (row & 1) {
            int last = column(row);
            return value(r, last) < value(r, best) ? last : best;
        }
        int bound;
        if (row + 1 == a.n) {
            bound = column(a.n - 1);
        } else {
            auto& b = levels[depth + 1];
            for (int j = (row ? row - 1 : 0); j <= row; ++j) {
                int c = column(j);
                while (b.size > row / 2) {
                    int q = (b.size << (depth + 1)) - 1;
                    if (!(value(q, c) < value(q, b.column[b.size - 1]))) break;
                    --b.size;
                }
                if (b.size < b.n) b.column[b.size++] = c;
            }
            bound = next_argmin(depth + 1);
        }
        if (best != bound) {
            auto best_value = value(r, best);
            do {
                int c = column(++a.state);
                auto candidate = value(r, c);
                if (candidate < best_value) best_value = candidate, best = c;
            } while (column(a.state) != bound);
        }
        return best;
    }

public:
    // A[r][c] = value_(r,c), 0 <= c <= r < n; next row = 0.
    Larsch(int n, F value_) : value(std::move(value_)) {
        assert(n >= 0);
        for (int size = n; size; size /= 2) levels.emplace_back(size, levels.empty());
    }

    // return min argmin_{0 <= c <= r} A[r][c], then r <- r+1.
    int next_argmin() {
        assert(!levels.empty() && levels[0].row < levels[0].n);
        return next_argmin(0);
    }

    // r <- 0; A may be changed before the next sequence of queries.
    void reset() {
        for (auto& a : levels) a.row = a.state = a.size = 0;
    }
};

}  // namespace detail
}  // namespace po167
#line 7 "algorithm/monge_shortest_path.hpp"

namespace po167 {

// f(a,c)+f(b,d) <= f(a,d)+f(b,c) (0 <= a < b < c < d <= n).
// return {dp, prev}: dp[0]=0, prev[0]=-1.
// dp[j]=min_{0 <= i < j}(dp[i]+f(i,j)) (1 <= j <= n).
// prev[j]=min argmin_{0 <= i < j}(dp[i]+f(i,j)).
// n >= 0; all costs and candidate sums must fit in T. Negative costs are allowed.
// O(n) time, O(n) space, assuming f is O(1).
template <class T = long long, class F>
std::pair<std::vector<T>, std::vector<int>> monge_shortest_path(int n, const F& f) {
    assert(n >= 0);
    std::vector<T> dp(n + 1);
    std::vector<int> prev(n + 1, -1);
    auto value = [&](int row, int col) { return dp[col] + T(f(col, row + 1)); };
    detail::Larsch<decltype(value)> solver(n, value);
    for (int v = 1; v <= n; ++v) {
        int p = prev[v] = solver.next_argmin();
        dp[v] = dp[p] + T(f(p, v));
    }
    return {std::move(dp), std::move(prev)};
}

}  // namespace po167
#line 4 "test/algorithm/monge_3.test.cpp"
#include <cstdlib>
#include <iostream>
#line 7 "test/algorithm/monge_3.test.cpp"

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<long long> A(N), X(N), Y(N);
    for (auto &a : A) std::cin >> a;
    for (auto &x : X) std::cin >> x;
    for (auto &y : Y) std::cin >> y;

    auto cost = [&](int i, int j){
        long long dx = std::abs(A[j - 1] - X[i]);
        return dx * dx * dx + Y[i] * Y[i] * Y[i];
    };

    auto dp = po167::monge_shortest_path(N, cost);
    std::cout << dp.first[N] << "\n";
}