cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: other_algorithms/test/monge_d_edge_shortest_paths_enum.yuki952.test.cpp

Depends on

Code

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

#include "../monge_d_edge_shortest_paths_enum.hpp"

#include <algorithm>
#include <iostream>
using namespace std;

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

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;

    vector<long long> cs(N + 1);
    for (int i = 0; i < N; ++i) cs.at(i + 1) = cs.at(i) + A.at(i);

    constexpr long long inf = 1LL << 60;

    auto f = [&](int i, int j) -> long long {
        long long sum = cs.at(j - 1) - cs.at(i);
        return sum * sum;
    };

    auto costs = MongeDEdgeShortestPaths<long long>(N + 2, N, f, inf);
    std::reverse(costs.begin(), costs.end());
    for (auto x : costs) cout << x << '\n';
}
#line 1 "other_algorithms/test/monge_d_edge_shortest_paths_enum.yuki952.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/952"

#line 2 "other_algorithms/smawk.hpp"
#include <cassert>
#include <functional>
#include <numeric>
#include <utility>
#include <vector>

// SMAWK: finding minima of totally monotone function f(i, j) (0 <= i < N, 0 <= j < M) for each i
// Constraints: every submatrix of f(i, j) is monotone.
// Complexity: O(N + M)
// Reference:
// https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120923/1348327542.html
// http://web.cs.unlv.edu/larmore/Courses/CSC477/monge.pdf
// Verify: https://codeforces.com/contest/1423/submission/98368491
template <class T>
std::vector<std::pair<int, T>> SMAWK(int N, int M, const std::function<T(int i, int j)> &weight) {
    std::vector<std::pair<int, T>> minima(N);

    auto rec = [&](auto &&self, const std::vector<int> &js, int ib, int ie, int id) {
        if (ib > ie) return;
        std::vector<int> js2;
        int i = ib;
        for (int j : js) {
            while (!js2.empty() and weight(i, js2.back()) >= weight(i, j)) js2.pop_back(), i -= id;
            if (int(js2.size()) != (ie - ib) / id) js2.push_back(j), i += id;
        }
        self(self, js2, ib + id, ie, id * 2);

        for (int i = ib, q = 0; i <= ie; i += id * 2) {
            const int jt = (i + id <= ie ? minima[i + id].first : js.back());
            T fm = 0;
            bool init = true;
            for (; q < int(js.size()); ++q) {
                const T fq = weight(i, js[q]);
                if (init or fm > fq) fm = fq, minima[i] = std::make_pair(js[q], fq);
                init = false;
                if (js[q] == jt) break;
            }
        }
    };

    std::vector<int> js(M);
    std::iota(js.begin(), js.end(), 0);
    rec(rec, js, 0, N - 1, 1);

    return minima;
}

// Concave max-plus convolution
// b must be concave
// Complexity: O(n + m)
// Verify: https://www.codechef.com/problems/MAXPREFFLIP
template <class S, S INF>
std::vector<S> concave_max_plus_convolution(const std::vector<S> &a, const std::vector<S> &b) {
    const int n = a.size(), m = b.size();

    auto is_concave = [&](const std::vector<S> &u) -> bool {
        for (int i = 1; i + 1 < int(u.size()); ++i) {
            if (u[i - 1] + u[i + 1] > u[i] + u[i]) return false;
        }
        return true;
    };

    bool a_concave = is_concave(a), b_concave = is_concave(b);
    assert(a_concave or b_concave);
    if (!b_concave) return concave_max_plus_convolution<S, INF>(b, a);

    auto select = [&](int i, int j) -> S {
        int aidx = j, bidx = i - j;
        if (bidx < 0 or bidx >= m or aidx >= n) return INF;
        return -(a[aidx] + b[bidx]);
    };
    const auto minima = SMAWK<S>(n + m - 1, n, select);
    std::vector<S> ret;
    for (auto x : minima) ret.push_back(-x.second);
    return ret;
}
#line 3 "other_algorithms/monge_d_edge_shortest_paths_enum.hpp"

#line 7 "other_algorithms/monge_d_edge_shortest_paths_enum.hpp"

// Calculate min cost paths of N vertices DAG from 0 to (N - 1), whose weight is Monge
// returns vector<T> costs, where costs[d - 1] == (min cost from 0 to (N - 1) with exactly d edges)
// Complexity: O(N maxD) (if SMAWK is used)
// Verify: https://yukicoder.me/problems/no/952
// Verify: https://mofecoder.com/contests/monoxercon_202508/tasks/monoxercon_202508_k
template <class T>
std::vector<T>
MongeDEdgeShortestPaths(int N, int max_d, const std::function<T(int i, int j)> &weight, T inf) {
    assert(max_d < N);
    std::vector<T> ans;

    std::vector<T> dp(N, inf);
    dp.at(0) = 0;
    // std::vector prevs(max_d, std::vector<int>(N, -1)); // if you need to retrieve path

    std::vector<T> costs;
    for (int d = 1; d <= max_d; ++d) {
        // MonotoneMinima<T>() is Also OK
        const auto res = SMAWK<T>(
            N, N - 1, [&](int j, int i) -> T { return i < j ? dp[i] + weight(i, j) : inf; });

        for (int i = d; i < N; ++i) dp.at(i) = res.at(i).second;
        // for (int i = d; i < N; ++i) {
        //     prevs.at(d - 1).at(i) = res.at(i).first;
        // }
        costs.push_back(dp.at(N - 1));
    }

    return costs;
}
#line 4 "other_algorithms/test/monge_d_edge_shortest_paths_enum.yuki952.test.cpp"

#include <algorithm>
#include <iostream>
using namespace std;

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

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;

    vector<long long> cs(N + 1);
    for (int i = 0; i < N; ++i) cs.at(i + 1) = cs.at(i) + A.at(i);

    constexpr long long inf = 1LL << 60;

    auto f = [&](int i, int j) -> long long {
        long long sum = cs.at(j - 1) - cs.at(i);
        return sum * sum;
    };

    auto costs = MongeDEdgeShortestPaths<long long>(N + 2, N, f, inf);
    std::reverse(costs.begin(), costs.end());
    for (auto x : costs) cout << x << '\n';
}
Back to top page