oj.uz

Submission #35820

# Submission time Handle Problem Language Result Execution time Memory
35820 2017-12-01T03:58:40 Z funcsr Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 11668 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <set>
#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];
set<P> ps;
void update(int x, long long y) {
  if (dp[x] <= y) return;
  P p = P(x, y+1LL*x*x);
  if (dp[x] < INF) {
    auto it = ps.find(p);
    if (it != ps.end()) ps.erase(it);
  }
  dp[x] = y;

  //cout<<"cur: ";for (P p : ps) cout<<"("<<p._1<<","<<p._2<<"),"; cout<<"\n";
  while (true) {
    auto left = ps.lower_bound(P(x, -1));
    if (left == ps.begin()) break;
    left--;
    P l = *left;
    if (l._2 >= p._2) ps.erase(left);
    else {
      if (left == ps.begin()) break;
      left--;
      P k = *left;
      if (det(l-k, p-l) > 0) break;
      ps.erase(++left);
    }
  }

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

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;
  update(H[0], W[0]);
  for (int i=1; i<N-1; i++) {
    long long m = INF;
    for (P p : ps) m = min(m, p._2 - 2LL*p._1*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 0 ms 10612 KB Output is correct
2 Correct 3 ms 10612 KB Output is correct
3 Correct 0 ms 10612 KB Output is correct
4 Correct 3 ms 10612 KB Output is correct
5 Correct 6 ms 10612 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 10744 KB Output is correct
2 Correct 983 ms 10744 KB Output is correct
3 Correct 1002 ms 10744 KB Output is correct
4 Correct 326 ms 10612 KB Output is correct
5 Execution timed out 3000 ms 11668 KB Execution timed out

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10612 KB Output is correct
2 Correct 3 ms 10612 KB Output is correct
3 Correct 0 ms 10612 KB Output is correct
4 Correct 3 ms 10612 KB Output is correct
5 Correct 6 ms 10612 KB Output is correct
6 Correct 983 ms 10744 KB Output is correct
7 Correct 983 ms 10744 KB Output is correct
8 Correct 1002 ms 10744 KB Output is correct
9 Correct 326 ms 10612 KB Output is correct
10 Execution timed out 3000 ms 11668 KB Execution timed out