Submission #1345289

#TimeUsernameProblemLanguageResultExecution timeMemory
1345289datBuilding Bridges (CEOI17_building)C++20
100 / 100
41 ms9792 KiB
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int Nmax = 1e5 + 5;
const ll INF = 4e18;

int n, h[Nmax], w[Nmax];
ll preW[Nmax], dp[Nmax];

vector<ll> comp;

struct line {
    ll a, b;
    line(ll A = 0, ll B = INF) : a(A), b(B) {}
    ll get(int x){
        return a * comp[x - 1] + b;
    }
};

struct lichao {
    vector<line> st;
    int n;

    lichao(int N){
        n = N;
        st.assign(n << 2, line());
    }

    void add(line nw, int id, int l, int r){
        int mid = (l + r) >> 1;

        bool left = nw.get(l) < st[id].get(l);
        bool middle = nw.get(mid) < st[id].get(mid);

        if(middle) swap(nw, st[id]);

        if(l == r) return;

        if(left != middle) add(nw, id << 1, l, mid);
        else add(nw, id << 1 | 1, mid + 1, r); 
    }

    ll query(int x, int id, int l, int r){
        ll res = st[id].get(x);
        if(l == r) return res;
        
        int mid = (l + r) >> 1;
        
        if(x <= mid) return min(res, query(x, id << 1, l, mid));
        else return min(res, query(x, id << 1 | 1, mid + 1, r));
    }
};

void compress(){
    comp.assign(h + 1, h + n + 1);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    for(int i = 1; i <= n; i++){
        h[i] = lower_bound(comp.begin(), comp.end(), h[i]) - comp.begin() + 1;
    }
}

void solve(){
    compress();

    for(int i = 1; i <= n; i++){
        preW[i] = preW[i - 1] + w[i];
    }

    lichao st(comp.size());

    st.add(line(-2LL * comp[h[1] - 1], comp[h[1] - 1] * comp[h[1] - 1] - preW[1]), 1, 1, comp.size());

    for(int i = 2; i <= n; i++){
        ll x = comp[h[i] - 1];
        ll T = preW[i - 1] + x * x;

        dp[i] = st.query(h[i], 1, 1, comp.size()) + T;

        st.add(line(-2LL * x, x * x - preW[i] + dp[i]), 1, 1, comp.size());
    }

    cout << dp[n];
}

void enter(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    enter();
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...