oj.uz

Submission #1118523

# Submission time Handle Problem Language Result Execution time Memory
1118523 2024-11-25T15:44:57 Z Icelast Building Bridges (CEOI17_building) C++17
100 / 100
 77 ms 13276 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
// line add min get, returns INF if no line added

template <class T>
struct LiChao {
    const T INF = numeric_limits<T>::max() / 2;

    int C;
    vector<T> dom;
    vector<array<T, 2>> first;
    vector<int> label;

    T f(array<T, 2> p, int x) {
        return p[0] * dom[x] + p[1];
    }

    LiChao(vector<T> _dom) : dom(_dom) {
        sort(dom.begin(), dom.end());
        dom.resize(unique(dom.begin(), dom.end()) - dom.begin());
        C = dom.size();
        first.resize(4 * C, {0, INF});
        label.resize(4 * C, -1);
    }

    void add(T a, T b, int lab) {
        array<T, 2> p{a, b};
        int idx = 0, l = 0, r = C;
        while (l < r) {
            int m = (l + r) >> 1;
            bool doml = f(p, l) < f(first[idx], l);
            bool domm = f(p, m) < f(first[idx], m);
            if (domm) swap(p, first[idx]), swap(label[idx], lab);
            if (l + 1 == r) break;
            if (doml != domm) idx = 2 * idx + 1, r = m;
            else idx = 2 * idx + 2, l = m;
        }
    }

    pair<T, int> getMin(T x) {
//        x -= 1e-9;
        x = lower_bound(dom.begin(), dom.end(), x) - dom.begin();
        T mn = INF;
        int lab = -1;
        int idx = 0, l = 0, r = C;
        while (l < r) {
            if (f(first[idx], x) < mn) mn = f(first[idx], x), lab = label[idx];
            if (l + 1 == r) break;
            int m = (l + r) >> 1;
            if (x < m) idx = 2 * idx + 1, r = m;
            else idx = 2 * idx + 2, l = m;
        }
        return make_pair(mn, lab);
    }
};
void solve(){
    int n;
    cin >> n;
    vector<ll> h(n+1), w(n+1);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    ll tot = 0;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        tot += w[i];
    }
    vector<ll> dom;
    for(int i = 1; i <= n; i++){
        dom.push_back(h[i]);
    }
    LiChao<ll> T(dom);
    vector<ll> f(n+1, 0);
    f[1] = -w[1];
    T.add(-h[1]*2, f[1]+h[1]*h[1], 1);
    for(int i = 2; i <= n; i++){
        f[i] = T.getMin(h[i]).first + h[i]*h[i] - w[i];
        T.add(-h[i]*2, f[i]+h[i]*h[i], i);
    }
    cout << f[n]+tot;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5848 KB Output is correct
2 Correct 52 ms 5836 KB Output is correct
3 Correct 52 ms 6000 KB Output is correct
4 Correct 42 ms 5292 KB Output is correct
5 Correct 43 ms 13272 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 52 ms 5848 KB Output is correct
7 Correct 52 ms 5836 KB Output is correct
8 Correct 52 ms 6000 KB Output is correct
9 Correct 42 ms 5292 KB Output is correct
10 Correct 43 ms 13272 KB Output is correct
11 Correct 66 ms 10612 KB Output is correct
12 Correct 63 ms 10416 KB Output is correct
13 Correct 43 ms 5604 KB Output is correct
14 Correct 77 ms 10596 KB Output is correct
15 Correct 46 ms 13100 KB Output is correct
16 Correct 44 ms 13276 KB Output is correct
17 Correct 18 ms 5596 KB Output is correct
18 Correct 20 ms 5480 KB Output is correct