제출 #1345262

#제출 시각아이디문제언어결과실행 시간메모리
1345262datBuilding Bridges (CEOI17_building)C++20
0 / 100
37 ms4916 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];
int preW[Nmax], dp[Nmax];

struct line {
    int a, b;
    line(int A = 0, int B = 1e9) : a(A), b(B) {}
    int get(int x){
        return a * 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); 
    }
    int query(int x, int id, int l, int r){
        int 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 solve(){
    for(int i = 1; i <= n; i++){
        preW[i] = preW[i - 1] + w[i];
    }
    lichao st(n);
    st.add(line(-2 * h[1], h[1] * h[1] - preW[1]), 1, 1, n);
    for(int i = 2; i <= n; i++){
        int T = preW[i - 1] + h[i] * h[i];
        dp[i] = st.query(h[i], 1, 1, n) + T;
        st.add(line(-2 * h[i], h[i] * 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(){
    enter();
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...