oj.uz

Submission #1113786

# Submission time Handle Problem Language Result Execution time Memory
1113786 2024-11-17T13:00:50 Z Zero_OP Building Bridges (CEOI17_building) C++14
100 / 100
 38 ms 14672 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
typedef long long ll;
typedef long double ld;
 
struct Line {
  mutable ll m, b, p;
  bool operator<(const Line& o) const { return m < o.m; }
  bool operator<(ll x) const { return p < x; }
};
 
struct LineContainer : multiset<Line, less<>> {
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  // Caution : This template solve for finding MAX, so if want to find MIN, NEGATE ALL THE LINE FUNCTION
    const ll inf = LLONG_MAX;
  ll div(ll a, ll b) { // floored division
    return a/b-((a^b)<0&&a%b); }
  bool isect(iterator x, iterator y) {
    if (y==end()) { x->p=inf; return false; }
    if (x->m==y->m) x->p=x->b>y->b?inf:-inf;
    else x->p=div(y->b-x->b, x->m-y->m);
    return x->p>=y->p;
  }
  void add(ll m, ll b) {
    m = -m; b = -b;
    auto z=insert({m, b, 0}), y=z++, x=y;
    while(isect(y, z)) z=erase(z);
    if (x!=begin() && isect(--x, y)) isect(x, y = erase(y));
    while((y = x)!=begin() && (--x)->p>=y->p)
    isect(x, erase(y));
  }
  ll query(ll x) { // max value at x
    assert(!empty());
    auto l=*lower_bound(x);
    return -(l.m*x+l.b);
  }
};
 
int n;
ll dp[N], h[N], w[N];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];
 
    LineContainer cht;
    cht.add(h[1], h[1] * h[1] + dp[1] - w[1]);
    for(int i = 2; i <= n; ++i){
        dp[i] = w[i - 1] + h[i] * h[i] + cht.query(-2 * h[i]);
        cht.add(h[i], h[i] * h[i] + dp[i] - w[i]);
    }
 
    cout << dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8528 KB Output is correct
2 Correct 29 ms 8528 KB Output is correct
3 Correct 28 ms 8528 KB Output is correct
4 Correct 26 ms 8528 KB Output is correct
5 Correct 24 ms 9544 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2556 KB Output is correct
6 Correct 29 ms 8528 KB Output is correct
7 Correct 29 ms 8528 KB Output is correct
8 Correct 28 ms 8528 KB Output is correct
9 Correct 26 ms 8528 KB Output is correct
10 Correct 24 ms 9544 KB Output is correct
11 Correct 27 ms 8776 KB Output is correct
12 Correct 29 ms 8520 KB Output is correct
13 Correct 22 ms 8588 KB Output is correct
14 Correct 30 ms 8648 KB Output is correct
15 Correct 38 ms 14672 KB Output is correct
16 Correct 24 ms 9548 KB Output is correct
17 Correct 15 ms 8528 KB Output is correct
18 Correct 14 ms 8528 KB Output is correct