結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2019-10-24 01:14:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 296 ms / 1,500 ms |
コード長 | 2,250 bytes |
コンパイル時間 | 1,720 ms |
コンパイル使用メモリ | 173,640 KB |
実行使用メモリ | 17,760 KB |
最終ジャッジ日時 | 2025-01-02 14:22:24 |
合計ジャッジ時間 | 9,546 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include "bits/stdc++.h" using namespace std; class LiChaoTree { using T = long long; using Line = std::pair<T, T>; const T inf = 1e15; // 最小化? bool isMinimum; int n; // 各区間には, その区間で最小(or最大)を取りうる直線を保持する std::vector<Line> node; std::vector<int> usd; static inline T f(const Line &line, T x) {return line.first * x + line.second;} // [l, r) に Line を追加, 現在ノードk void add(int k, int l, int r, Line line) { while(r-l>0) { if(!usd[k]) { node[k] = line; usd[k] = true; return; } int m = (l + r) / 2; bool left = (f(line, l) < f(node[k], l)); bool mid = (f(line, m) < f(node[k], m)); bool right = (f(line, r) < f(node[k], r)); if(left && right) { node[k] = line; return; } if(!left && !right) { return; } if(mid) { swap(line, node[k]); } if(left != mid) { k = 2 * k + 1; r = m; } else { k = 2 * k + 2; l = m; } } } public: // [0, n] 用の木を作る LiChaoTree(int _n, bool isMin=true) : isMinimum(isMin) { n = 1; while(n < _n) n *= 2; node.resize(2 * n - 1, Line(0, isMin ? inf : -inf)); usd.resize(2 * n - 1, false); } // ax + b を追加する void add(T a, T b) { add(0, 0, n, Line(a, b)); return; } T get(T x) { int k = x + (n - 1); T ret = usd[k] ? f(node[k], x) : inf; while(k > 0) { k = (k-1)/2; if(usd[k]) { ret = std::min(ret, f(node[k], x)); } } return ret; } }; // https://yukicoder.me/submissions/392545 void solve_yukicoder_703() { using ll = long long; const ll inf = 1e15; int n; cin >> n; vector<ll> a(n+1), x(n+1), y(n+1); 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]; } LiChaoTree cht(100010); vector<ll> dp(n + 1, inf); dp[0] = 0; for (int i = 1; i <= n; i++) { cht.add(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp[i-1]); dp[i] = cht.get(a[i]) + a[i] * a[i]; //cerr << dp[i] << endl; } cout << dp[n] << endl; } int main() { solve_yukicoder_703(); }