結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-21 22:18:01
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 110 ms / 1,500 ms
コード長 2,180 bytes
コンパイル時間 5,694 ms
コンパイル使用メモリ 211,832 KB
実行使用メモリ 13,024 KB
最終ジャッジ日時 2025-03-21 22:18:11
合計ジャッジ時間 10,459 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define lc(i) (i << 1)
#define rc(i) (i << 1 | 1)
using namespace std;
const int N = 3e5 + 10;
struct LiChao_Tree {
    struct line {
        ll k, b; bool fg;
        inline ll gety(ll x) { return fg ? k * x + b : 2e18; }
    } tree[N << 2];
    inline void update(int id, int tl, int tr, line p) {
        if (!tree[id].fg) {
            tree[id] = p;
            tree[id].fg = 1;
        } else if (p.gety(tl) < tree[id].gety(tl) && p.gety(tr) < tree[id].gety(tr)) {
            tree[id].k = p.k; tree[id].b = p.b;
        } else if (p.gety(tl) < tree[id].gety(tl) || p.gety(tr) < tree[id].gety(tr)) {
            int mid = (tl + tr) >> 1;
            if (p.gety(mid) < tree[id].gety(mid)) swap(tree[id].k, p.k), swap(tree[id].b, p.b);
            if (p.gety(tl) < tree[id].gety(tl)) update(lc(id), tl, mid, p);
            if (p.gety(tr) < tree[id].gety(tr)) update(rc(id), mid + 1, tr, p);
        }
    }
    inline ll query(int id, int tl, int tr, ll x) {
        if (tl == tr) return tree[id].gety(x);
        int mid = (tl + tr) >> 1; ll ans = tree[id].gety(x);
        if (x <= mid) return min(ans, query(lc(id), tl, mid, x));
        return min(ans, query(rc(id), mid + 1, tr, x));
    }
} T;
ll a[N], x[N], y[N], dp[N];
ll prex[N], prey[N], pre[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= n; ++i) cin >> y[i];
    for (int i = 1; i <= n; ++i) dp[i] = 2e18;
    // for (int i = 1; i <= n; ++i) {
    //     for (int j = 0; j < i; ++j) {
    //         // [j + 1, i]
    //         dp[i] = min(dp[i], dp[j] + (a[i] - x[j + 1]) * (a[i] - x[j + 1]) + y[j + 1] * y[j + 1]);
    //     }
    // }
    T.update(0, -300000, 300000, {-2 * x[1], dp[0] + x[1] * x[1] + y[1] * y[1], 1});
    for (int i = 1; i <= n; ++i) {
        dp[i] = a[i] * a[i] + T.query(0, -300000, 300000, a[i]);
        T.update(0, -300000, 300000, {-2 * x[i + 1], dp[i] + x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1], 1});
    }
    cout << dp[n];
    return 0;
}
0