Submission #1363351

#TimeUsernameProblemLanguageResultExecution timeMemory
1363351yeongminbBuilding Bridges (CEOI17_building)C++20
100 / 100
35 ms7760 KiB
#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct line{
  ll a,b;
  ll f(ll x){return a*x + b;}
};
struct Node{
  ll l,r;
  line L;
};
struct LiChaoTree{
public:
  ll S=0,E=1e6+10; vector<Node> tree;
  LiChaoTree(){
    tree.push_back({-1, -1, {0, INF}});
  }
  void update(ll m, ll b){
    update(0, S, E, {m,b});
  }
  ll query(ll x){
    return query(0, S, E, x);
  }
private:
  void update(ll node, ll st, ll en, line li){
    line high = tree[node].L, low = li;
    if(high.f(st) < low.f(st)) swap(high, low);
    if(high.f(en) >= low.f(en)) {tree[node].L = low; return;}
    ll mid = (st + en)/2;
    if(low.f(mid) < high.f(mid)){
      tree[node].L = low;
      if(tree[node].r == -1){
        tree[node].r = tree.size();
        tree.push_back({-1, -1, {0, INF}});
      }
      update(tree[node].r, mid, en, high);
    } else {
      tree[node].L = high;
      if(tree[node].l == -1){
        tree[node].l = tree.size();
        tree.push_back({-1, -1, {0, INF}});
      }
      update(tree[node].l, st, mid, low);
    }
  }
  ll query(ll node, ll st, ll en, ll x){
    if(node == -1) return INF;
    ll mid = (st + en)/2;
    if(x <= mid) return min(tree[node].L.f(x), query(tree[node].l, st, mid, x));
    return min(tree[node].L.f(x), query(tree[node].r, mid, en, x));
  }
};

int main(){
  fastio;
  ll N; cin >> N;
  vector<ll> H(N), W(N);
  for(auto &h : H) cin >> h;
  for(auto &w : W) cin >> w;
  
  vector<ll> S(N+1, 0), dp(N, 0);
  for(ll i=1;i<=N;i++) S[i] = S[i-1] + W[i-1];
  
  LiChaoTree LCT;
  LCT.update(-2*H[0], -S[1]+H[0]*H[0]);
  for(ll i=1;i<N;i++){
    dp[i] = H[i]*H[i] + S[i] + LCT.query(H[i]);
    if(i != N-1) LCT.update(-2*H[i], -S[i+1]+H[i]*H[i]+dp[i]);
  }
  cout << dp[N-1];
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...