제출 #881833

#제출 시각아이디문제언어결과실행 시간메모리
881833Zero_OPBuilding Bridges (CEOI17_building)C++14
100 / 100
36 ms13652 KiB
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

typedef long long ll;
typedef long double ld;

struct Line {
  mutable ll m, b, p;
  bool operator<(const Line& o) const { return m < o.m; }
  bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  // Caution : This template solve for finding MAX, so if want to find MIN, NEGATE ALL THE LINE FUNCTION
    const ll inf = LLONG_MAX;
  ll div(ll a, ll b) { // floored division
    return a/b-((a^b)<0&&a%b); }
  bool isect(iterator x, iterator y) {
    if (y==end()) { x->p=inf; return false; }
    if (x->m==y->m) x->p=x->b>y->b?inf:-inf;
    else x->p=div(y->b-x->b, x->m-y->m);
    return x->p>=y->p;
  }
  void add(ll m, ll b) {
    m = -m; b = -b;
    auto z=insert({m, b, 0}), y=z++, x=y;
    while(isect(y, z)) z=erase(z);
    if (x!=begin() && isect(--x, y)) isect(x, y = erase(y));
    while((y = x)!=begin() && (--x)->p>=y->p)
    isect(x, erase(y));
  }
  ll query(ll x) { // max value at x
    assert(!empty());
    auto l=*lower_bound(x);
    return -(l.m*x+l.b);
  }
};

int n;
ll dp[N], h[N], w[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];

    LineContainer cht;
    cht.add(h[1], h[1] * h[1] + dp[1] - w[1]);
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + cht.query(-2 * h[i]);
        cht.add(h[i], h[i] * h[i] + dp[i] - w[i]);
    }

    cout << dp[n];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...