結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2018-11-09 10:07:56 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 284 ms / 1,500 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 1,191 ms |
コンパイル使用メモリ | 105,580 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2025-01-02 14:04:02 |
合計ジャッジ時間 | 9,071 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <random> using namespace std; typedef long long int ll; typedef pair<ll, ll> P; int main() { int n; cin>>n; ll a[300001], x[300001], y[300001]; 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]; deque<P> line; ll dp=0; for(int i=1; i<=n; i++){ ll a0=-2*x[i], b0=x[i]*x[i]+y[i]*y[i]+dp; if(!(line.size()>=1 && line.back().first==a0 && line.back().second<=b0)){ while(line.size()>1){ ll a1=line[line.size()-1].first, b1=line[line.size()-1].second; ll a2=line[line.size()-2].first, b2=line[line.size()-2].second; if((b1-b2)*(a1-a0)<(b0-b1)*(a2-a1)) break; line.pop_back(); } line.push_back(P(a0, b0)); } while(line.size()>1){ ll a1=line[0].first, b1=line[0].second; ll a2=line[1].first, b2=line[1].second; if(a1*a[i]+b1<a2*a[i]+b2) break; line.pop_front(); } ll a1=line[0].first, b1=line[0].second; dp=a1*a[i]+b1+a[i]*a[i]; } cout<<dp<<endl; return 0; }