結果
問題 | No.703 ゴミ拾い Easy |
ユーザー |
|
提出日時 | 2018-06-30 17:31:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 85 ms / 1,500 ms |
コード長 | 1,887 bytes |
コンパイル時間 | 1,722 ms |
コンパイル使用メモリ | 162,204 KB |
実行使用メモリ | 10,276 KB |
最終ジャッジ日時 | 2025-01-02 13:56:51 |
合計ジャッジ時間 | 5,676 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define ll long long #define fi first #define se second #define push_back pb #define show(x) cout << #x << " = " << x << "\n" using namespace std; typedef pair<int,int> P; //f[j](x) = a[j]x + b[j]でaがjの増加に伴い単調減少する場合 template<typename T> class CHT { private: using ptt = pair<T, T>; bool check(ptt l1, ptt l2, ptt l3){ return (l2.first-l1.first)*(l3.second-l2.second)>=(l2.second-l1.second)*(l3.first-l2.first); } T f(int i, T x){ return lines[i].first * x + lines[i].second; } public: vector<ptt> lines; CHT(){}; void add(T a, T b){ ptt line(a, b); while((int)lines.size() >= 2 && check(*(lines.end()-2), lines.back(), line)){ lines.pop_back(); } lines.emplace_back(line); } T get(T x){ static int head = 0; while((int)lines.size() - head >= 2 && f(head, x) > f(head + 1, x)){ head++; } return f(head, x); // int low = -1, high = lines.size() - 1; // while (high - low > 1) { // int mid = (high + low) / 2; // if(f(mid, x) >= f(mid+1, x)){ // low = mid; // }else{ // high = mid; // } // } // return f(high, x); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<ll> a(n),x(n),y(n); rep(i,n){ cin >> a[i]; } rep(i,n){ cin >> x[i]; } rep(i,n){ cin >> y[i]; } CHT<ll> cht; cht.add(-2*x[0],x[0]*x[0]+y[0]*y[0]); rep(i,n){ if(i < n-1){ cht.add(-2*x[i+1],cht.get(a[i])+x[i+1]*x[i+1]+y[i+1]*y[i+1]+a[i]*a[i]); }else{ cout << cht.get(a[i])+a[i]*a[i] << "\n"; return 0; } } }