oj.uz

Submission #35839

# Submission time Handle Problem Language Result Execution time Memory
35839 2017-12-01T10:40:35 Z funcsr Building Bridges (CEOI17_building) C++14
100 / 100
 666 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];
set<int> ps;
inline P get(int x) { return P(x, f[x]); }

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() {
  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++;
      }
    }
    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 0 ms 18424 KB Output is correct
2 Correct 3 ms 18424 KB Output is correct
3 Correct 6 ms 18424 KB Output is correct
4 Correct 3 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 306 ms 18556 KB Output is correct
2 Correct 319 ms 18556 KB Output is correct
3 Correct 306 ms 18556 KB Output is correct
4 Correct 246 ms 18424 KB Output is correct
5 Correct 293 ms 19348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18424 KB Output is correct
2 Correct 3 ms 18424 KB Output is correct
3 Correct 6 ms 18424 KB Output is correct
4 Correct 3 ms 18424 KB Output is correct
5 Correct 3 ms 18424 KB Output is correct
6 Correct 306 ms 18556 KB Output is correct
7 Correct 319 ms 18556 KB Output is correct
8 Correct 306 ms 18556 KB Output is correct
9 Correct 246 ms 18424 KB Output is correct
10 Correct 293 ms 19348 KB Output is correct
11 Correct 303 ms 18424 KB Output is correct
12 Correct 329 ms 18556 KB Output is correct
13 Correct 119 ms 18424 KB Output is correct
14 Correct 316 ms 18556 KB Output is correct
15 Correct 666 ms 23176 KB Output is correct
16 Correct 309 ms 19348 KB Output is correct
17 Correct 89 ms 18424 KB Output is correct
18 Correct 76 ms 18424 KB Output is correct