oj.uz

Submission #35866

# Submission time Handle Problem Language Result Execution time Memory
35866 2017-12-01T14:01:21 Z funcsr Building Bridges (CEOI17_building) C++14
100 / 100
 783 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 r = next(p_ps->find(a));
    return !(r == p_ps->end() || det(get(*r)-get(a), 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++) {
    int h = H[i];
    int x = *ps.lower_bound(-2*h);
    update(H[i], (f[x]-2LL*x*h) + 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 9 ms 18424 KB Output is correct
2 Correct 3 ms 18424 KB Output is correct
3 Correct 3 ms 18424 KB Output is correct
4 Correct 0 ms 18424 KB Output is correct
5 Correct 6 ms 18424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 18556 KB Output is correct
2 Correct 246 ms 18556 KB Output is correct
3 Correct 253 ms 18556 KB Output is correct
4 Correct 209 ms 18424 KB Output is correct
5 Correct 389 ms 19348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18424 KB Output is correct
2 Correct 3 ms 18424 KB Output is correct
3 Correct 3 ms 18424 KB Output is correct
4 Correct 0 ms 18424 KB Output is correct
5 Correct 6 ms 18424 KB Output is correct
6 Correct 249 ms 18556 KB Output is correct
7 Correct 246 ms 18556 KB Output is correct
8 Correct 253 ms 18556 KB Output is correct
9 Correct 209 ms 18424 KB Output is correct
10 Correct 389 ms 19348 KB Output is correct
11 Correct 246 ms 18424 KB Output is correct
12 Correct 273 ms 18556 KB Output is correct
13 Correct 116 ms 18424 KB Output is correct
14 Correct 273 ms 18556 KB Output is correct
15 Correct 783 ms 23176 KB Output is correct
16 Correct 409 ms 19348 KB Output is correct
17 Correct 89 ms 18424 KB Output is correct
18 Correct 86 ms 18424 KB Output is correct