結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
![]() |
提出日時 | 2025-03-25 17:48:44 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,308 bytes |
コンパイル時間 | 8,611 ms |
コンパイル使用メモリ | 213,020 KB |
実行使用メモリ | 21,960 KB |
最終ジャッジ日時 | 2025-03-25 17:49:04 |
合計ジャッジ時間 | 18,953 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 WA * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; using ll = long long; const double eps = 1e-7; /* typ: 0: no cross point 1: only one 2: two points 3: same function */ struct point { double x1, x2; int typ; }; #define ls(i) (i << 1) #define rs(i) (i << 1 | 1) struct node { ll a, b, c; bool flag; ll operator () (int x) { if (!flag) return LLONG_MAX; return a * x * x + b * x + c; } friend point cross(node x, node y) { ll a = x.a - y.a, b = x.b - y.b, c = x.c - y.c; if (a == 0) { if (b == 0) { if (c == 0) { return {0, 0, 3}; } else { return {0, 0, 0}; } } else { return {-1.0 * c / b, 0, 1}; } } else { ll delta = b * b - 4 * a * c; if (delta < 0) return {0, 0, 0}; else if (delta == 0) return {-1.0 * b / (2 * a), 0, 1}; else { double x1 = 1.0 * (-1.0 * b + sqrtl(delta)) / (2 * a); double x2 = 1.0 * (-1.0 * b - sqrtl(delta)) / (2 * a); if (x1 > x2) swap(x1, x2); return {x1, x2, 2}; } } } } tree[N << 2]; bool in(point cur, int l, int r) { return (cur.typ == 1 && (l <= cur.x1 && cur.x1 <= r) || cur.typ == 2 && (l <= cur.x1 && cur.x1 <= r) && (l <= cur.x2 && cur.x2 <= r)); } 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].a = p.a; tree[i].b = p.b; tree[i].c = p.c; tree[i].flag = 1; return; } auto cur = cross(p, tree[i]); if (!in(cur, tl, tr)) { if (p(tl) - tree[i](tl) < 0 && p(tr) - tree[i](tr) < 0) tree[i].a = p.a, tree[i].b = p.b, tree[i].c = p.c; } else { int tm = tl + tr >> 1; if (p(tm) - tree[i](tm) < 0) swap(p.a, tree[i].a), swap(p.b, tree[i].b), swap(p.c, tree[i].c); if (in(cur, tl, tm)) update(ls(i), tl, tm, l, r, p); if (in(cur, tm + 1, tr)) 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, N - 5, {1, -2 * x[1], x[1] * x[1] + y[1] * 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, N - 5, {1, -2 * x[i + 1], x[i + 1] * x[i + 1] + y[i + 1] * y[i + 1] + dp[i], 1}); } cout << dp[n]; return 0; }