結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2019-09-25 20:23:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 100 ms / 1,500 ms |
コード長 | 1,913 bytes |
コンパイル時間 | 952 ms |
コンパイル使用メモリ | 71,024 KB |
実行使用メモリ | 16,772 KB |
最終ジャッジ日時 | 2025-01-02 14:20:58 |
合計ジャッジ時間 | 5,134 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
#include <iostream> #include <utility> #include <vector> #define llint long long #define inf 1e18 using namespace std; typedef pair<llint, llint> P; struct LiChaoTree{ int size; vector<P> seg; LiChaoTree(){} LiChaoTree(int size){ this->size = size; seg.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(0, inf); } llint calc(P f, llint x) { return f.first * x + f.second; } llint query(int x) //xにおける最小値を取得 { int i = x + (1 << size); llint ret = inf; while(i >= 1){ ret = min(ret, calc(seg[i], x)); i /= 2; } return ret; } void add(int k, int l, int r, P f) { int m = (l+r)/2; if(calc(f, m) < calc(seg[k], m)) swap(seg[k], f); bool L = (calc(f, l) < calc(seg[k], l)), R = (calc(f, r) < calc(seg[k], r)); if(L == R) return; if(L) add(k*2, l, m, f); if(R) add(k*2+1, m+1, r, f); } void addSegment(int a, int b, int k, int l, int r, P f) { if(b < l || r < a) return; if(a <= l && r <= b){ add(k, l, r, f); return; } addSegment(a, b, k*2, l, (l+r)/2, f); addSegment(a, b, k*2+1, (l+r)/2+1, r, f); } void addSegment(int a, int b, llint p, llint q) //区間[a, b]に線分px+qを追加 { addSegment(a, b, 1, 0, (1<<size)-1, make_pair(p, q)); } void addLine(llint p, llint q) //直線px+qを追加 { return addSegment(0, (1<<size)-1, p, q); } }; llint n; llint a[300005], x[300005], y[300005]; llint dp[300005]; LiChaoTree lct(17); int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = n; i >= 1; i--) cin >> a[i]; for(int i = n; i >= 1; i--) cin >> x[i]; for(int i = n; i >= 1; i--) cin >> y[i]; lct.init(); dp[0] = 0; lct.addLine(-2*a[1], a[1]*a[1]+dp[0]); for(int i = 1; i <= n; i++){ dp[i] = lct.query(x[i]) + x[i]*x[i] + y[i]*y[i]; lct.addLine(-2*a[i+1], a[i+1]*a[i+1]+dp[i]); } cout << dp[n] << endl; return 0; }