結果

問題 No.703 ゴミ拾い Easy
コンテスト
ユーザー vjudge1
提出日時 2025-03-21 17:01:26
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 129 ms / 1,500 ms
コード長 2,458 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,855 ms
コンパイル使用メモリ 276,576 KB
実行使用メモリ 29,440 KB
最終ジャッジ日時 2025-03-21 17:01:36
合計ジャッジ時間 8,627 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
#define F first
#define S second
#define Bout(x) (x ? "Yes" : "No")
#define DO(x) return x, void(0);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using mii = map<int, int>;
using ui = unsigned;
const int N = 3e5 + 5;
const int Md = 1e18 + 7;
int n, m;
int a[N], x[N], y[N], dp[N];
struct LiChaoT {
#define ls (id << 1)
#define rs (id << 1 | 1)
#define mid ((tl + tr) >> 1)
    struct node {
        int k, b;
        node(int _k = 0, int _b = 1e18) : k(_k), b(_b) { }
        int operator () (const int &x) const & { return k * x + b; }
        bool operator == (const node &T) const & { return k == T.k && b == T.b; }
    } seg[N << 2];
    node cmp(node a, node b, int x) {
        if (a(x) - b(x) > 0) return b;
        if (b(x) - a(x) > 0) return a;
        return b;
    }
    void add(int id, int tl, int tr, node val) {
        if (seg[id] == val) return;
        if (cmp(seg[id], val, mid) == val) swap(seg[id], val);
        if (cmp(seg[id], val, tl) == val) add(ls, tl, mid, val);
        if (cmp(seg[id], val, tr) == val) add(rs, mid + 1, tr, val);
    }
    node qry(int id, int tl, int tr, int x) {
        if (tl == tr) return seg[id];
        node a = seg[id], b = (x <= mid ? qry(ls, tl, mid, x) : qry(rs, mid + 1, tr, x));
        return cmp(a, b, x);
    }
#undef mid
#undef ls
#undef rs
}T;
signed main() {
    FASTIO;
    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];

    T.add(1, 0, 1e5, { -2 * x[0 + 1], 0 + x[0 + 1] * x[0 + 1] + y[0 + 1] * y[0 + 1] });
    for (int i = 1; i <= n; i++) {
        int now = T.qry(1, 0, 1e5, a[i])(a[i]) + a[i] * a[i];
        T.add(1, 0, 1e5, { -2 * x[i + 1], now + x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1] });
        if (i == n) cout << now;
    }
    return 0;
}
/*
a[i] : ppl
x[i] : garbage X_i
y[i] : garbage Y_i

dp[i] = min(dp[j] + (a[i] - x[j + 1]) ^ 2 + y[j + 1] * y[j + 1]) | j < i
dp[i] = min(dp[j] + a[i] * a[i] + x[j + 1] * x[j + 1] + y[j + 1] * y[j + 1] - 2 * a[i] * x[j + 1]) | j < i
dp[i] = a[i] * a[i] + min(-2 * x[j + 1] * a[i] + dp[j] + x[j + 1] * x[j + 1] + y[j + 1] * y[j + 1]) | j < i
                          ------k------    -x-                               b

*/
0