제출 #143074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143074		Milki	Building Bridges (CEOI17_building)	C++14	100 / 100	217 ms	12668 KiB

building

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
#define int long long

typedef long long ll;
typedef pair<ll, ll> point;
typedef long double ld;

const int MAXN = 1e5 + 5, MAXV = 105;
const ll inf = 1e16;

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

ld ccw(point A, point B, point C){
  return (ld)A.first * (B.second - C.second) +
         (ld)B.first * (C.second - A.second) +
         (ld)C.first * (A.second - B.second);
}

void merge(vector <point> &lt, vector <point> &rt, vector <point> &hull){
  int pnt1 = 0, pnt2 = 0;
  vector <point> v;
  while(pnt1 < sz(lt) || pnt2 < sz(rt)){
    if(pnt1 == sz(lt))
      v.pb(rt[pnt2 ++]);
    else if(pnt2 == sz(rt))
      v.pb(lt[pnt1 ++]);
    else if(lt[pnt1].first == rt[pnt2].first){
      if(lt[pnt1].second < rt[pnt2].second)
        v.pb(lt[pnt1 ++]);
      else
        v.pb(rt[pnt2 ++]);
    }
    else if(lt[pnt1].first < rt[pnt2].first)
      v.pb(lt[pnt1 ++]);
    else
      v.pb(rt[pnt2 ++]);
  }

  hull.clear();
  for(auto it : v){
    while(sz(hull) > 1 && ccw( hull[ sz(hull) - 2 ], hull.back(), it) <= 0)
      hull.pop_back();
    hull.pb(it);
  }
}

ll check(ll x, point y){
  return x * y.first + y.second;
}

void eval(int x, vector <point> &hull){
  if(hull.empty())
    return;

  int lo = 0, hi = sz(hull) - 1;
  while(lo < hi){
    int mid = (lo + hi) >> 1;
    if(mid + 1 > hi)
      lo = mid;
    if( check(h[x], hull[mid]) > check(h[x], hull[mid + 1]) )
      lo = mid + 1;
    else
      hi = mid;
  }
  //TRACE(check(h[x], hull[lo]));
  //TRACE(hull[lo].first); TRACE(hull[lo].second);
  dp[x] = min(dp[x], check(h[x], hull[lo]) + w[x - 1] + h[x] * h[x]);
}

void solve(int lo, int hi, vector <point> &hull){
  if(lo > hi) return;
  if(lo == hi){
    hull.pb(point(-2 * h[lo], dp[lo] + h[lo] * h[lo] - w[lo]));
    return;
  }
  vector <point> lt, rt;
  int mid = (lo + hi) >> 1;

  FOR(i, lo, hi + 1)
    eval(i, hull);

  solve(lo, mid, lt);

  FOR(i, mid + 1, hi + 1)
    eval(i, lt);

  solve(mid + 1, hi, rt);

  vector <point> tmp;
  merge(lt, rt, tmp);
  merge(hull, tmp, hull);
}

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  fill(dp, dp + MAXN, inf);
  dp[1] = 0;

  cin >> n;
  REP(i, n)
    cin >> h[i + 1];
  REP(i, n){
    cin >> w[i + 1];
    if(i > 0)
      w[i + 1] += w[i];
  }

  /*FOR(i, 2, n + 1){
    dp[i] = inf;
    FOR(j, 1, i){
      dp[i] = min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + w[i - 1] - w[j] );

    }
  }*/
  vector <point> v;
  solve(1, n, v);
  cout << dp[n];
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40