oj.uz

Submission #143074

# Submission time Handle Problem Language Result Execution time Memory
143074 2019-08-12T22:29:57 Z Milki Building Bridges (CEOI17_building) C++14
100 / 100
 217 ms 12668 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 3064 KB Output is correct
2 Correct 216 ms 3984 KB Output is correct
3 Correct 216 ms 4136 KB Output is correct
4 Correct 204 ms 3704 KB Output is correct
5 Correct 151 ms 5628 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 217 ms 3064 KB Output is correct
7 Correct 216 ms 3984 KB Output is correct
8 Correct 216 ms 4136 KB Output is correct
9 Correct 204 ms 3704 KB Output is correct
10 Correct 151 ms 5628 KB Output is correct
11 Correct 206 ms 4020 KB Output is correct
12 Correct 214 ms 4004 KB Output is correct
13 Correct 134 ms 3804 KB Output is correct
14 Correct 213 ms 4160 KB Output is correct
15 Correct 195 ms 12668 KB Output is correct
16 Correct 151 ms 5744 KB Output is correct
17 Correct 80 ms 3844 KB Output is correct
18 Correct 81 ms 3960 KB Output is correct