結果

問題 No.704 ゴミ拾い Medium
ユーザー vjudge1
提出日時 2025-03-21 19:56:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 377 ms / 1,500 ms
コード長 2,230 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 195,412 KB
実行使用メモリ 19,148 KB
最終ジャッジ日時 2025-03-21 19:57:06
合計ジャッジ時間 11,837 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const double eps = 1e-7;
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
struct node {
    ll k, b;
    bool flag;
    ll operator () (int x) {
        if (!flag) return LLONG_MAX;
        return k * x + b;
    }
    friend double cross(node x, node y) {
        return 1.0 * (x.b - y.b) / (y.k - x.k);
    }
} tree[N << 2];
void update(int i, int tl, int tr, int l, int r, node p) {
    if (l <= tl && tr <= r) {
        if (!tree[i].flag) {
            tree[i].k = p.k;
            tree[i].b = p.b;
            tree[i].flag = 1;
            return;
        }
        if (p(tl) - tree[i](tl) < 0 && p(tr) - tree[i](tr) < 0) 
            tree[i].k = p.k, tree[i].b = p.b;
        else if (p(tl) - tree[i](tl) < 0 || p(tr) - tree[i](tr) < 0) {
            int tm = tl + tr >> 1;
            if (p(tm) - tree[i](tm) < 0) 
                swap(tree[i].k, p.k), swap(tree[i].b, p.b);
            if (cross(p, tree[i]) - tm < eps)
                update(ls(i), tl, tm, l, r, p);
            else
                update(rs(i), tm + 1, tr, l, r, p);
        }
    }
    else {
        int tm = tl + tr >> 1;
        if (l <= tm)
            update(ls(i), tl, tm, l, r, p);
        if (r > tm)
            update(rs(i), tm + 1, tr, l, r, p);
    }
}
ll query(int i, int tl, int tr, int pos) {
    if (tl == tr) return tree[i](pos);
    int tm = tl + tr >> 1;
    ll ans = tree[i](pos);
    if (pos <= tm)
        return min(ans, query(ls(i), tl, tm, pos));
    else
        return min(ans, query(rs(i), tm + 1, tr, pos));
}
ll a[N * 3], x[N * 3], y[N * 3], dp[N * 3];
int main() {
    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];
    update(1, 0, N - 5, 0, x[1], {-1, x[1] + dp[0] + y[1], 1});
    update(1, 0, N - 5, x[1], N - 5, {1, -x[1] + dp[0] + y[1], 1});
    for (int i = 1; i <= n; i++) {
        dp[i] = query(1, 0, N - 5, a[i]);
        update(1, 0, N - 5, 0, x[i + 1], {-1, x[i + 1] + dp[i] + y[i + 1], 1});
        update(1, 0, N - 5, x[i + 1], N - 5, {1, -x[i + 1] + dp[i] + y[i + 1], 1});
    }
    cout << dp[n];
    return 0;
}
0