제출 #1345281

#제출 시각아이디문제언어결과실행 시간메모리
1345281datBuilding Bridges (CEOI17_building)C++20
0 / 100
30 ms8856 KiB
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int Nmax = 1e5 + 5, inf = 1e9 + 5;

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

struct line {
    ll a, b;
    line(ll A = 0, ll B = 1e18) : a(A), b(B) {}
    ll get(ll x){
        return a * val[x] + 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));
    }
};


// int cost(int l, int r){
//     //int sum1 = preW[r - 1] - preW[l];
//     //int sum2 = h[r] * h[r] + h[l] * h[l] - 2 * h[r] * h[l];
//     int T = preW[r - 1] + h[r] * h[r];
//     int axb = - 2 * h[r] * h[l] + h[l] * h[l] - preW[l];
//     return sum1 + sum2;
// }



void compress(){
    vector<int> c(h + 1, h + n + 1);
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    for(int i = 1; i <= n; i++){
        int idx = lower_bound(c.begin(), c.end(), h[i]) - c.begin() + 1;
        val[idx] = h[i];
        h[i] = idx;
    }
}


void solve(){
    compress();

    for(int i = 1; i <= n; i++){
        preW[i] = preW[i - 1] + w[i];
    }
    lichao st(n);
    st.add(line(-2 * val[h[1]], val[h[1]] * val[h[1]] - preW[1]), 1, 1, n);
    for(int i = 2; i <= n; i++){
        ll T = preW[i - 1] + val[h[i]] * val[h[i]];
        dp[i] = st.query(h[i], 1, 1, n) + T;
        st.add(line(-2LL * val[h[i]], val[h[i]] * val[h[i]] - preW[i] + dp[i]), 1, 1, n);
    }
    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...