oj.uz

Submission #143075

# Submission time Handle Problem Language Result Execution time Memory
143075 2019-08-12T22:31:11 Z Milki Building Bridges (CEOI17_building) C++14
100 / 100
 217 ms 11908 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

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

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

ll 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);
}

int 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 1144 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 215 ms 3076 KB Output is correct
2 Correct 215 ms 3064 KB Output is correct
3 Correct 217 ms 2964 KB Output is correct
4 Correct 204 ms 2724 KB Output is correct
5 Correct 152 ms 4652 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 1144 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 215 ms 3076 KB Output is correct
7 Correct 215 ms 3064 KB Output is correct
8 Correct 217 ms 2964 KB Output is correct
9 Correct 204 ms 2724 KB Output is correct
10 Correct 152 ms 4652 KB Output is correct
11 Correct 207 ms 2952 KB Output is correct
12 Correct 214 ms 2980 KB Output is correct
13 Correct 135 ms 2808 KB Output is correct
14 Correct 216 ms 3032 KB Output is correct
15 Correct 199 ms 11908 KB Output is correct
16 Correct 152 ms 4692 KB Output is correct
17 Correct 80 ms 2728 KB Output is correct
18 Correct 82 ms 2680 KB Output is correct