oj.uz

Submission #35869

# Submission time Handle Problem Language Result Execution time Memory
35869 2017-12-01T14:04:36 Z funcsr Building Bridges (CEOI17_building) C++14
100 / 100
 766 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 = ++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;
  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 6 ms 18424 KB Output is correct
2 Correct 3 ms 18424 KB Output is correct
3 Correct 13 ms 18424 KB Output is correct
4 Correct 3 ms 18424 KB Output is correct
5 Correct 9 ms 18424 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 18556 KB Output is correct
2 Correct 259 ms 18556 KB Output is correct
3 Correct 253 ms 18556 KB Output is correct
4 Correct 226 ms 18424 KB Output is correct
5 Correct 429 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 3 ms 18424 KB Output is correct
3 Correct 13 ms 18424 KB Output is correct
4 Correct 3 ms 18424 KB Output is correct
5 Correct 9 ms 18424 KB Output is correct
6 Correct 236 ms 18556 KB Output is correct
7 Correct 259 ms 18556 KB Output is correct
8 Correct 253 ms 18556 KB Output is correct
9 Correct 226 ms 18424 KB Output is correct
10 Correct 429 ms 19348 KB Output is correct
11 Correct 216 ms 18424 KB Output is correct
12 Correct 269 ms 18556 KB Output is correct
13 Correct 113 ms 18424 KB Output is correct
14 Correct 253 ms 18556 KB Output is correct
15 Correct 766 ms 23176 KB Output is correct
16 Correct 366 ms 19348 KB Output is correct
17 Correct 76 ms 18424 KB Output is correct
18 Correct 69 ms 18424 KB Output is correct