oj.uz

Submission #881833

# Submission time Handle Problem Language Result Execution time Memory
881833 2023-12-02T03:29:54 Z Zero_OP Building Bridges (CEOI17_building) C++14
100 / 100
 36 ms 13652 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 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7516 KB Output is correct
2 Correct 30 ms 7504 KB Output is correct
3 Correct 31 ms 7604 KB Output is correct
4 Correct 28 ms 7516 KB Output is correct
5 Correct 25 ms 8588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 31 ms 7516 KB Output is correct
7 Correct 30 ms 7504 KB Output is correct
8 Correct 31 ms 7604 KB Output is correct
9 Correct 28 ms 7516 KB Output is correct
10 Correct 25 ms 8588 KB Output is correct
11 Correct 29 ms 7512 KB Output is correct
12 Correct 30 ms 7508 KB Output is correct
13 Correct 24 ms 7768 KB Output is correct
14 Correct 31 ms 7508 KB Output is correct
15 Correct 36 ms 13652 KB Output is correct
16 Correct 30 ms 8788 KB Output is correct
17 Correct 16 ms 7568 KB Output is correct
18 Correct 16 ms 7388 KB Output is correct