結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2020-10-17 18:55:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 287 ms / 1,500 ms |
コード長 | 1,593 bytes |
コンパイル時間 | 1,873 ms |
コンパイル使用メモリ | 176,320 KB |
実行使用メモリ | 12,720 KB |
最終ジャッジ日時 | 2024-07-21 03:00:08 |
合計ジャッジ時間 | 10,758 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
/** * @FileName a.cpp * @Author kanpurin * @Created 2020.10.17 18:54:57 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; template<typename T> struct ConvexHullTrick { private: using P = pair<T,T>; deque<P> deq; inline bool check(P l, P m, P r) { return (m.first-l.first)*(r.second-m.second) >= (m.second-l.second)*(r.first-m.first); } public: ConvexHullTrick() {} void add_query(T a, T b) { if (deq.size() <= 1) { deq.push_back(make_pair(a,b)); return; } P m = deq.back(); deq.pop_back(); while(!deq.empty() && check(deq.back(),m,{a,b})) { m = deq.back(); deq.pop_back(); } deq.push_back(m); deq.push_back({a,b}); } T get_query(T x) { P m = deq.front(); deq.pop_front(); while(!deq.empty() && m.first * x + m.second >= deq.front().first * x + deq.front().second) { m = deq.front(); deq.pop_front(); } deq.push_front(m); return m.first * x + m.second; } }; int main() { ConvexHullTrick<ll> cht; int n;cin >> n; vector<ll> a(n),x(n),y(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> x[i]; } for (int i = 0; i < n; i++) { cin >> y[i]; } vector<ll> dp(n); for (int i = 0; i < n; i++) { cht.add_query(-2*x[i],(i==0?0:dp[i-1])+y[i]*y[i]+x[i]*x[i]); dp[i] = cht.get_query(a[i]) + a[i]*a[i]; } cout << dp[n-1] << endl; return 0; }