結果
問題 | No.703 ゴミ拾い Easy |
ユーザー | kopricky |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 1 ms
6,816 KB |
testcase_07 | AC | 1 ms
6,820 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 1 ms
6,816 KB |
testcase_10 | AC | 1 ms
6,816 KB |
testcase_11 | AC | 1 ms
6,816 KB |
testcase_12 | AC | 1 ms
6,820 KB |
testcase_13 | AC | 1 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 2 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,816 KB |
testcase_17 | AC | 2 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 2 ms
6,816 KB |
testcase_21 | AC | 1 ms
6,820 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,820 KB |
testcase_24 | AC | 78 ms
10,112 KB |
testcase_25 | AC | 82 ms
10,240 KB |
testcase_26 | AC | 81 ms
10,240 KB |
testcase_27 | AC | 77 ms
10,112 KB |
testcase_28 | AC | 80 ms
10,240 KB |
testcase_29 | AC | 80 ms
10,236 KB |
testcase_30 | AC | 83 ms
10,240 KB |
testcase_31 | AC | 84 ms
10,240 KB |
testcase_32 | AC | 77 ms
10,240 KB |
testcase_33 | AC | 77 ms
10,136 KB |
testcase_34 | AC | 75 ms
10,276 KB |
testcase_35 | AC | 74 ms
10,240 KB |
testcase_36 | AC | 85 ms
10,104 KB |
testcase_37 | AC | 84 ms
10,184 KB |
testcase_38 | AC | 77 ms
10,240 KB |
testcase_39 | AC | 75 ms
10,076 KB |
testcase_40 | AC | 79 ms
10,112 KB |
testcase_41 | AC | 77 ms
10,240 KB |
testcase_42 | AC | 73 ms
10,240 KB |
testcase_43 | AC | 73 ms
10,240 KB |
testcase_44 | AC | 1 ms
6,820 KB |
testcase_45 | AC | 1 ms
6,816 KB |
testcase_46 | AC | 82 ms
10,240 KB |
testcase_47 | AC | 83 ms
10,212 KB |
testcase_48 | AC | 1 ms
6,820 KB |
testcase_49 | AC | 2 ms
6,820 KB |
ソースコード
#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; } } }