結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-04-04 09:34:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 1,500 ms |
コード長 | 2,180 bytes |
コンパイル時間 | 3,705 ms |
コンパイル使用メモリ | 277,640 KB |
実行使用メモリ | 15,972 KB |
最終ジャッジ日時 | 2025-04-04 09:34:45 |
合計ジャッジ時間 | 7,256 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#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; }