제출 #1090339

#제출 시각아이디문제언어결과실행 시간메모리
1090339alexdumitruBuilding Bridges (CEOI17_building)C++17
100 / 100
71 ms67256 KiB
#include <bits/stdc++.h>

using ll = long long;

const int NMAX = 1e5;
const int VMAX = 1e6;

int n;
ll w[NMAX + 1];
ll h[NMAX + 1];
ll dp[NMAX + 1];
ll sp[NMAX + 1];

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

ll get_sum(int l, int r) {
    return sp[r] - sp[l - 1];
}

struct Line {
    ll a, b;
    Line() : a(0), b(LLONG_MAX) {}
    Line(ll _a, ll _b) : a(_a), b(_b) {}
    ll operator()(const int & x) {
        return a * x + b;
    }
};

namespace LiChao {
    Line aint[4 * VMAX + 5];
    void add(int node, int l, int r, Line nline) {
        int m = (l + r) / 2;
        bool lef = nline(l) < aint[node](l);
        bool mid = nline(m) < aint[node](m);
        if (mid)
            std::swap(nline, aint[node]);
        if (l == r) return;
        if (lef != mid) add(node * 2, l, m, nline);
        else add(node * 2 + 1, m + 1, r, nline);
    }

    ll query(int node, int l, int r, int x) {
        int m = (l + r) / 2;
        if (l == r)
            return aint[node](x);
        if (x < m)
            return std::min(aint[node](x), query(node * 2, l, m, x));
        return std::min(aint[node](x), query(node * 2 + 1, m + 1, r, x));
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            dp[i] = h[i] * h[i] + sp[i - 1];
            dp[i] += LiChao::query(1, 0, VMAX, h[i]);
        }
        LiChao::add(1, 0, VMAX, Line(-2 * h[i], h[i] * h[i] + dp[i] - sp[i]));
    }
    std::cout << dp[n] << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    read();
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...