Submission #1277645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277645		harryleee	Building Bridges (CEOI17_building)	C++20	100 / 100	59 ms	65356 KiB

building

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
int n;
long long w[maxn + 1], h[maxn + 1];
long long dp[maxn + 1];

struct line{
    long long a, b;
    inline line(long long _a = 0, long long _b = 0){
        a = _a; b = _b;
    }
    inline long long calc(int x){
        return a * x + b;
    }
};

struct LICHAO_TREE{
    vector<line> st;
    int sz;

    inline LICHAO_TREE(){
        sz = 1e6;
        st.resize(4 * sz + 4, line(0, 1e18));
    }
    inline void update(int ind, int l, int r, line cur){
        if (l == r){
            if (cur.calc(l) < st[ind].calc(l)) st[ind] = cur;
            return;
        }
        int mid = (l + r) >> 1;
        if (st[ind].calc(mid) > cur.calc(mid)) swap(st[ind], cur);
        if (cur.calc(l) < st[ind].calc(l)) update(ind << 1, l, mid, cur);
        if (cur.calc(r) < st[ind].calc(r)) update(ind << 1 | 1, mid + 1, r, cur);
        return;
    }
    inline long long get(int ind, int l, int r, int pos){
        long long res = st[ind].calc(pos);
        if (l == r) return res;
        int mid = (l + r) >> 1;
        if (pos <= mid) return min(res, get(ind << 1, l, mid, pos));
        else return min(res, get(ind << 1 | 1, mid + 1, r, pos));
    }
} lichao;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    lichao.update(1, 1, 1e6, {-2 * h[1], dp[1] - w[1] + h[1] * h[1]});
    for (int i = 2; i <= n; ++i){
        dp[i] = lichao.get(1, 1, 1e6, h[i]) + h[i] * h[i] + w[i - 1];
        lichao.update(1, 1, 1e6, {-2 * h[i], dp[i] - w[i] + h[i] * h[i]});
    }
    cout << dp[n];
    return 0;   
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40