結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-03-21 17:22:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 1,500 ms |
コード長 | 2,228 bytes |
コンパイル時間 | 1,765 ms |
コンパイル使用メモリ | 166,360 KB |
実行使用メモリ | 107,036 KB |
最終ジャッジ日時 | 2025-03-21 17:23:06 |
合計ジャッジ時間 | 8,227 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | scanf("%lld", &n); | ~~~~~^~~~~~~~~~~~ main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | scanf("%lld", &a[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:72:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 72 | scanf("%lld", &x[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:74:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 74 | scanf("%lld", &y[i]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 3e5 + 10; const long double eps = 1e-9; const int INF = 2e18; const int V = 1e5; int x[N], y[N], a[N], sum, dp[N]; int n; struct line{ long double k, b; int ls, rs, l, r; bool flag = 0; int getY(int x){ return x * k + b; } long double IntersectionX(line v){ return (b - v.b) / (v.k - k); } }; struct node{ line tree[N * 4]; int ncnt, root; void update(int &id, int tl, int tr, line p){ // cout << tl << " " << tr << endl; if(id == 0){ id = ++ncnt; } if(p.l <= tl && tr <= p.r){ if(tree[id].flag == 0){ tree[id].k = p.k; tree[id].b = p.b; tree[id].flag = 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 tm = (tl + tr) / 2; if(tree[id].getY(tm) > p.getY(tm)) swap(p.k, tree[id].k), swap(p.b, tree[id].b); if((long double) tm - p.IntersectionX(tree[id]) > eps){ update(tree[id].ls, tl, tm, p); }else{ update(tree[id].rs, tm + 1, tr, p); } } }else{ int tm = (tl + tr) / 2; if(p.l <= tm) update(tree[id].ls, tl, tm, p); if(p.r > tm) update(tree[id].rs, tm + 1, tr, p); } } int query(int id, int tl, int tr, int x){ if(id == 0) return INF; if(tl == tr){ if(tree[id].flag) return tree[id].getY(x); return INF; } int tm = (tl + tr) / 2; int ret = (tree[id].flag == 1) ? tree[id].getY(x) : INF; if(x <= tm){ return min(ret, query(tree[id].ls, tl, tm, x)); }else{ return min(ret, query(tree[id].rs, tm + 1, tr, x)); } } }LCtree; signed main(){ scanf("%lld", &n); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); for(int i = 1; i <= n; i++) scanf("%lld", &x[i]); for(int i = 1; i <= n; i++) scanf("%lld", &y[i]); for(int i = 1; i <= n; i++){ dp[i] = INF; line p; p.k = -2 * x[i]; p.b = y[i] * y[i] + dp[i - 1] + x[i] * x[i]; p.l = 1; p.r = V; p.ls = p.rs = p.flag = 0; LCtree.update(LCtree.root, 1, V, p); dp[i] = LCtree.query(LCtree.root, 1, V, a[i]) + a[i] * a[i]; // cout << i << " " << dp[i] << endl; } printf("%lld\n", dp[n]); }