結果

問題 No.705 ゴミ拾い Hard
ユーザー KowerKoint2010KowerKoint2010
提出日時 2024-04-17 18:05:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 428 ms / 1,500 ms
コード長 3,274 bytes
コンパイル時間 1,402 ms
コンパイル使用メモリ 125,028 KB
実行使用メモリ 17,556 KB
最終ジャッジ日時 2024-04-17 18:05:42
合計ジャッジ時間 10,605 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 384 ms
17,448 KB
testcase_25 AC 393 ms
17,432 KB
testcase_26 AC 381 ms
17,428 KB
testcase_27 AC 379 ms
17,464 KB
testcase_28 AC 396 ms
17,408 KB
testcase_29 AC 378 ms
17,428 KB
testcase_30 AC 428 ms
17,432 KB
testcase_31 AC 375 ms
17,428 KB
testcase_32 AC 369 ms
17,556 KB
testcase_33 AC 259 ms
17,432 KB
testcase_34 AC 263 ms
17,556 KB
testcase_35 AC 304 ms
17,428 KB
testcase_36 AC 344 ms
17,428 KB
testcase_37 AC 301 ms
17,428 KB
testcase_38 AC 352 ms
17,428 KB
testcase_39 AC 396 ms
17,432 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 389 ms
17,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "cpp/convex.hpp"
#include <cassert>
#include <vector>
#include <functional>
#include <stack>
#include <type_traits>
#include <optional>

/**
 * @brief monotoneな行列において、各行の最小値を取る最小列番号を$O((H+W)\log H)$時間で得る
 * @param h 行数(行番号は[0..h-1])
 * @param w 列数(列番号は[0..w-1])
 * @param f 行列の要素を与える関数(行番号と列番号を引数にとって値を返す)
 * @param comp 要素の比較関数(最小値を知りたい場合はデフォルトのstd::less<T>)
 * @return std::vector<int> 各行の最小値列番号
 */
template <typename F, typename Comp = std::less<std::invoke_result_t<F, int, int>>>
std::vector<int> monotone_minima(int h, int w, const F& f, const Comp& comp = Comp()) {
    using T = std::invoke_result_t<F, int, int>;
    assert(h >= 0);
    assert(w >= 0);
    std::vector<int> res(h);
    std::stack<std::tuple<int, int, int, int>> stk; // {i, j, l, r} : [i..j]行目の答えを求める。結果は[l..r]の範囲に収まることが保証されている。
    stk.emplace(0, h-1, 0, w-1);
    while(!stk.empty()) {
        auto [i, j, l, r] = stk.top(); stk.pop();
        int m = (i+j) / 2;
        T min_value = f(m, l);
        int min_idx = l;
        for(int k = l+1; k <= r; k++) {
            T value = f(m, k);
            if(comp(value, min_value)) {
                min_value = value;
                min_idx = k;
            }
        }
        res[m] = min_idx;
        if(i <= m-1) stk.emplace(i, m-1, l, min_idx);
        if(m+1 <= j) stk.emplace(m+1, j, min_idx, r);
    }
    return res;
}

template <typename F, typename Comp = std::less<std::invoke_result_t<F, int, int>>>
std::vector<std::invoke_result_t<F, int, int>> online_offline_dp(int n, const F& f, const Comp& comp = Comp{}) {
    using T = std::invoke_result_t<F, int, int>;
    std::vector<std::optional<T>> dp(n+1, std::nullopt);
    dp[0] = 0;
    // dp[l..r)の要素を、dp[l..r)からの遷移のみの範囲で求める
    auto solve_subproblem = [&](auto self, int l, int r) -> void {
        int mid = (l+r) / 2;
        if(mid-l >= 2) self(self, l, mid);
        auto submat = [&](int i, int j) {
            return dp[l+j].value() + f(l+j, mid+i);
        };
        std::vector<int> min_idx = monotone_minima(r-mid, mid-l, submat, comp);
        for(int i = 0; i < r-mid; i++) {
            T val = submat(i, min_idx[i]);
            if(!dp[mid+i] || comp(val, dp[mid+i].value())) {
                dp[mid+i] = val;
            }
        }
        if(r-mid >= 2) self(self, mid, r);
    };
    solve_subproblem(solve_subproblem, 0, n+1);
    std::vector<T> res(n+1);
    for(int i = 0; i <= n; i++) res[i] = dp[i].value();
    return res;
}
#line 2 "test/yukicoder-705.test.cpp"
#include <iostream>

int main() {
    using ll = long long;
    int n; std::cin >> n;
    std::vector<ll> a(n), x(n), y(n);
    for(int i = 0; i < n; i++) std::cin >> a[i];
    for(int i = 0; i < n; i++) std::cin >> x[i];
    for(int i = 0; i < n; i++) std::cin >> y[i];
    auto f = [&](int i, int j) {
        ll dx = std::abs(x[i] - a[j-1]);
        ll dy = std::abs(y[i]);
        return dx*dx*dx + dy*dy*dy;
    };
    std::cout << online_offline_dp(n, f)[n] << std::endl;
}
0