oj.uz

Submission #35822

# Submission time Handle Problem Language Result Execution time Memory
35822 2017-12-01T04:23:43 Z funcsr Building Bridges (CEOI17_building) C++14
60 / 100
 3000 ms 19272 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;
vector<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); }
inline auto lower(int x) { return lower_bound(all(ps), x); }

void update(int x, long long y) {
  if (dp[x] <= y) return;
  if (dp[x] < INF) {
    //auto it = ps.find(x);
    auto it = lower(x);
    if (it != ps.end() && *it == x) 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);
  ps.insert(lower(x), x);
  //ps.push_back(x); sort(all(ps));
}

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++) {
    //assert(is_all_convex());
    long long m = INF;
    for (int x : ps) m = min(m, f[x] - 2LL*x*H[i]);
    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 3 ms 18420 KB Output is correct
2 Correct 6 ms 18420 KB Output is correct
3 Correct 3 ms 18420 KB Output is correct
4 Correct 3 ms 18420 KB Output is correct
5 Correct 3 ms 18420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 18420 KB Output is correct
2 Correct 283 ms 18420 KB Output is correct
3 Correct 293 ms 18420 KB Output is correct
4 Correct 149 ms 18420 KB Output is correct
5 Correct 1659 ms 18692 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18420 KB Output is correct
2 Correct 6 ms 18420 KB Output is correct
3 Correct 3 ms 18420 KB Output is correct
4 Correct 3 ms 18420 KB Output is correct
5 Correct 3 ms 18420 KB Output is correct
6 Correct 276 ms 18420 KB Output is correct
7 Correct 283 ms 18420 KB Output is correct
8 Correct 293 ms 18420 KB Output is correct
9 Correct 149 ms 18420 KB Output is correct
10 Correct 1659 ms 18692 KB Output is correct
11 Correct 179 ms 18420 KB Output is correct
12 Correct 293 ms 18420 KB Output is correct
13 Correct 106 ms 18420 KB Output is correct
14 Correct 286 ms 18420 KB Output is correct
15 Execution timed out 3000 ms 19272 KB Execution timed out
16 Halted 0 ms 0 KB -