oj.uz

Submission #35863

# Submission time Handle Problem Language Result Execution time Memory
35863 2017-12-01T13:59:48 Z funcsr Building Bridges (CEOI17_building) C++14
100 / 100
 816 ms 23176 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(xs) xs.begin(), xs.end()
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, long long> P;

P operator -(const P &a, const P &b) { return P(a._1-b._1, a._2-b._2); }
inline long long det(P a, P b) { return 1LL*a._1*b._2 - 1LL*a._2*b._1; }

int N;
int H[100000], W[100000];
long long dp[1000001];
long long f[1000001];
inline P get(int x) { return P(x, f[x]); }
set<int, bool(*)(int, int)> *p_ps;
bool comp(int a, int b) {
  if (a < 0) return !comp(b, a);
  if (b < 0) {
    auto l = p_ps->find(a);
    auto r = next(l);
    return !(r == p_ps->end() || det(get(*r)-get(*l), P(1, -b)) <= 0);
  }
  return a < b;
}
set<int, bool(*)(int, int)> ps(comp);

bool is_all_convex() {
  vector<P> xs;
  for (int x : ps) xs.push_back(P(x, f[x]));
  rep(i, (int)xs.size()-2) {
    if (det(xs[i+1]-xs[i], xs[i+2]-xs[i]) <= 0) return false;
  }
  return true;
}

inline auto lower(int x) { return ps.lower_bound(x); }

void update(int x, long long y) {
  if (dp[x] <= y) return;
  if (dp[x] < INF) {
    auto it = ps.find(x);
    if (it != ps.end()) ps.erase(it);
  }
  P p = P(x, y+1LL*x*x);
  dp[x] = y;
  f[x] = p._2;
  //cout<<"cur: ";for (P p : ps) cout<<"("<<p._1<<","<<p._2<<"),"; cout<<"\n";
  //cout<<"cur: ";for (P p : ps) cout<<"("<<p._1<<","<<p._2<<"),"; cout<<"\n";
  while (true) {
    auto right = lower(x);
    if (right == ps.end()) break;
    P r = get(*right);
    if (p._2 >= r._2) return; // erase p
    else {
      right++;
      if (right == ps.end()) break;
      P k = get(*right);
      if (det(r-p, k-r) > 0) break;
      ps.erase(--right);
    }
  }

  while (true) {
    auto left = lower(x);
    if (left == ps.begin()) break;
    left--;
    P l = get(*left);
    if (l._2 >= p._2) ps.erase(left);
    else {
      if (left == ps.begin()) break;
      left--;
      P k = get(*left);
      if (det(l-k, p-l) > 0) break;
      ps.erase(++left);
    }
  }
  auto right = lower(x);
  if (right != ps.begin() && right != ps.end()) {
    P r = get(*right);
    P l = get(*(--right));
    if (det(p-l, r-p) <= 0) return;
  }
  ps.insert(x);
}

signed main() {
  p_ps = &ps;

  cin >> N;
  rep(i, N) cin >> H[i];
  long long sum = 0;
  rep(i, N) {
    cin >> W[i];
    sum += W[i];
    W[i] = -W[i];
  }
  rep(h, 1000001) dp[h] = INF, f[h] = INF;
  update(H[0], W[0]);
  for (int i=1; i<N-1; i++) {
    long long m = INF;
    int h = H[i];
    /*
    if (ps.size() <= 2) {
      for (int x : ps) m = min(m, f[x] - 2LL*x*h);
    }
    else {
      int lo = *ps.begin(), hi = *(--ps.end());
      while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        auto l = lower(mid), r = ++lower(mid);
        if (r == ps.end() || det(get(*r)-get(*l), P(1, 2LL*h)) <= 0) hi = mid;
        else lo = mid;
      }
      auto it = lower(lo);
      rep(_, 2) {
        if (it == ps.end()) break;
        int x = *it;
        m = min(m, f[x] - 2LL*x*h);
        it++;
      }
    }
    */
    int x = *ps.lower_bound(-2*h);
    m = f[x] - 2LL*x*h;
    update(H[i], m+1LL*H[i]*H[i]+W[i]);
  }
  long long m = INF;
  rep(h, 1000001) m = min(m, dp[h] + 1LL*(h-H[N-1])*(h-H[N-1]));
  cout << sum + m + W[N-1] << "\n";
  return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 18556 KB Output is correct
2 Correct 243 ms 18556 KB Output is correct
3 Correct 246 ms 18556 KB Output is correct
4 Correct 219 ms 18424 KB Output is correct
5 Correct 383 ms 19348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18424 KB Output is correct
2 Correct 6 ms 18424 KB Output is correct
3 Correct 3 ms 18424 KB Output is correct
4 Correct 6 ms 18424 KB Output is correct
5 Correct 3 ms 18424 KB Output is correct
6 Correct 246 ms 18556 KB Output is correct
7 Correct 243 ms 18556 KB Output is correct
8 Correct 246 ms 18556 KB Output is correct
9 Correct 219 ms 18424 KB Output is correct
10 Correct 383 ms 19348 KB Output is correct
11 Correct 229 ms 18424 KB Output is correct
12 Correct 263 ms 18556 KB Output is correct
13 Correct 119 ms 18424 KB Output is correct
14 Correct 253 ms 18556 KB Output is correct
15 Correct 816 ms 23176 KB Output is correct
16 Correct 379 ms 19348 KB Output is correct
17 Correct 76 ms 18424 KB Output is correct
18 Correct 89 ms 18424 KB Output is correct