oj.uz

Submission #1117944

# Submission time Handle Problem Language Result Execution time Memory
1117944 2024-11-24T11:57:05 Z mingga Building Bridges (CEOI17_building) C++17
100 / 100
 45 ms 19224 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ln '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define int long long
const int inf = 2e18;
const int N = 1e5 + 7;
const int M = 1e6 + 7;
int h[N], w[N], n, ps[N], f[N];

struct line {
    int a, b;
    line() {}
    line(int a, int b) : a(a), b(b) {}
    int calc(int x) {
        return a * x + b;
    }
    int slope() {
        return a;
    }
};

struct lichao {
    vector<line> st;
    lichao() {}
    int n;
    lichao(int n) : n(n) {
        st.resize(n + 1, line(0, inf));
    }
    void update(line f, int l, int r) {
        if(l > r) return ;
        int m = (l + r) >> 1;
        if(l == r) {
            st[m] = f.calc(l) < st[m].calc(l) ? f : st[m];
            return;
        }
        if(f.calc(m) < st[m].calc(m)) swap(f, st[m]);
        if(f.slope() > st[m].slope()) update(f, l, m - 1);
        if(f.slope() < st[m].slope()) update(f, m + 1, r);
    }
    int query(int l, int r, int x) {
        int m = (l + r) >> 1;
        int cur = st[m].calc(x);
        if(x == m) return cur;
        if(x < m) return min(cur, query(l, m - 1, x));
        return min(cur, query(m + 1, r, x));
    }
};

int a(int i) {
    return - 2 * h[i];
}
int b(int i) {
    return f[i] - ps[i] + h[i] * h[i];
}


signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> w[i], ps[i] = ps[i - 1] + w[i];
    lichao st(M);
    st.update(line(a(1), b(1)), 0, M);
    for(int i = 2; i <= n; i++) {
        int ext = ps[i - 1] + h[i] * h[i];
        f[i] = st.query(0, M, h[i]) + ext;
        st.update(line(a(i), b(i)), 0, M);
    }
    cout << f[n];
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 19024 KB Output is correct
2 Correct 33 ms 19056 KB Output is correct
3 Correct 33 ms 19192 KB Output is correct
4 Correct 30 ms 19024 KB Output is correct
5 Correct 29 ms 19076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18000 KB Output is correct
2 Correct 3 ms 18000 KB Output is correct
3 Correct 4 ms 18000 KB Output is correct
4 Correct 4 ms 18000 KB Output is correct
5 Correct 4 ms 18000 KB Output is correct
6 Correct 35 ms 19024 KB Output is correct
7 Correct 33 ms 19056 KB Output is correct
8 Correct 33 ms 19192 KB Output is correct
9 Correct 30 ms 19024 KB Output is correct
10 Correct 29 ms 19076 KB Output is correct
11 Correct 40 ms 19024 KB Output is correct
12 Correct 45 ms 19024 KB Output is correct
13 Correct 34 ms 19024 KB Output is correct
14 Correct 41 ms 19168 KB Output is correct
15 Correct 26 ms 19024 KB Output is correct
16 Correct 27 ms 19192 KB Output is correct
17 Correct 18 ms 19024 KB Output is correct
18 Correct 20 ms 19224 KB Output is correct