oj.uz

Submission #528417

# Submission time Handle Problem Language Result Execution time Memory
528417 2022-02-20T09:00:01 Z cig32 Building Bridges (CEOI17_building) C++17
100 / 100
 111 ms 12864 KB 
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
const int is_query = -(1ll<<62);
struct Line {
  int m, b;
  mutable function<const Line*()> succ;
  bool operator<(const Line& rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const Line* s = succ();
    if (!s) return 0;
    int x = rhs.m;
    return b - s->b < (s->m - m) * x;
  }
};
struct dynamic_hull : public multiset<Line> { // wiint maintain upper hull for maximum
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
        if (z == end()) return 0;
        return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) return y->m == x->m && y->b <= x->b;
    return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
  }
  void insert_line(int m, int b) {
    auto y = insert({ m, b });
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) { erase(y); return; }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  int eval(int x) {
    auto l = *lower_bound((Line) { x, is_query });
    return l.m * x + l.b;
  }
};


void solve(int tc) {
  int n;
  cin >> n;
  int h[n+1];
  int ps[n+1];
  ps[0] = 0;
  for(int i=1; i<=n; i++) {
    cin >> h[i];
  }
  for(int i=1; i<=n; i++) {
    cin >> ps[i];
    ps[i] += ps[i-1];
  }
  int dp[n+1];
  dp[1] = 0;
  dynamic_hull cht;
  cht.insert_line(-h[1], -h[1] * h[1] + ps[1]);
  for(int i=2; i<=n; i++) {
    dp[i] = -cht.eval(-2 * h[i]) + h[i] * h[i] + ps[i-1];
    cht.insert_line(-h[i], -h[i] * h[i] + ps[i] - dp[i]);
  }
  cout << dp[n] << "\n";
}
 
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1;// cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3764 KB Output is correct
2 Correct 68 ms 3712 KB Output is correct
3 Correct 58 ms 3768 KB Output is correct
4 Correct 51 ms 3604 KB Output is correct
5 Correct 57 ms 5316 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 62 ms 3764 KB Output is correct
7 Correct 68 ms 3712 KB Output is correct
8 Correct 58 ms 3768 KB Output is correct
9 Correct 51 ms 3604 KB Output is correct
10 Correct 57 ms 5316 KB Output is correct
11 Correct 56 ms 3760 KB Output is correct
12 Correct 65 ms 3768 KB Output is correct
13 Correct 34 ms 3660 KB Output is correct
14 Correct 62 ms 3920 KB Output is correct
15 Correct 111 ms 12864 KB Output is correct
16 Correct 57 ms 5316 KB Output is correct
17 Correct 26 ms 3636 KB Output is correct
18 Correct 21 ms 3632 KB Output is correct