結果

問題 No.705 ゴミ拾い Hard
コンテスト
ユーザー 武内號
提出日時 2025-12-05 12:21:49
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 389 ms / 1,500 ms
コード長 2,182 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,431 ms
コンパイル使用メモリ 289,748 KB
実行使用メモリ 22,080 KB
最終ジャッジ日時 2025-12-05 12:22:02
合計ジャッジ時間 12,849 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < (b); i++)
#define aff(a) begin(a), end(a)
bool chmin(auto &a, auto b) {
    return a > b ? a = b, 1 : 0;
}
bool chmax(auto &a, auto b) {
    return a < b ? a = b, 1 : 0;
}

template <class T, class F>
vector<pair<int, T>> monotone_minima(int H, int W, F f, int lx = -1,
                                     int rx = -1, int ly = -1, int ry = -1) {
    if (lx == -1) {
        lx = ly = 0;
        rx = W;
        ry = H;
    }
    if (H <= 0)
        return {};
    int m = (ly + ry) / 2;
    int ans_j = lx;
    T ans = f(m, lx);
    for (int j = lx+1; j < rx; j++) {
        if (chmin(ans, f(m, j))) {
            ans_j = j;
        }
    }
    auto ret =
        monotone_minima<T>(m - ly, ans_j + 1 - lx, f, lx, ans_j + 1, ly, m);
    ret.push_back({ans_j, ans});
    auto ret2 =
        monotone_minima<T>(ry - (m + 1), rx - ans_j, f, ans_j, rx, m + 1, ry);
    ret.insert(end(ret), aff(ret2));
    return ret;
}



const ll inf = LLONG_MAX / 4;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll n;
    cin >> n;
    vector<ll> A(n), X(n), Y(n);
    rep(i, 0, n) cin >> A[i];
    rep(i, 0, n) cin >> X[i];
    rep(i, 0, n) cin >> Y[i];

    vector<ll> dp(n+1, inf);
    dp[0] = 0;
    auto f = [&](int i, int j) {
        return dp[j] + abs(X[j] - A[i-1]) * abs(X[j] - A[i-1]) * abs(X[j] - A[i-1]) + Y[j] * Y[j] * Y[j];
    };

    //[l, m) がわかっているときに [m, r) に寄与を反映する
    auto induce = [&](int l, int m, int r) -> void {
        auto g = [&](int i, int j) {
            return f(i + m, j + l);
        };
        auto ret = monotone_minima<ll, decltype(g)>(r - m, m - l, g);
        rep(i, 0, r - m) {
            chmin(dp[i + m], ret[i].second);
        }
    };
    // [0, l) が求まっていてかつ寄与が反映済みのとき [l, r) を求める
    auto dfs = [&](auto self, int l, int r) -> void {
        if(r - l <= 1) return;
        int m = (l + r) / 2;
        self(self, l, m);
        induce(l, m, r);
        self(self, m, r);
    };
    induce(0,1,n+1);
    dfs(dfs, 1, n+1);
    cout << dp[n] << endl;
}
0