Submission #1090339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090339		alexdumitru	Building Bridges (CEOI17_building)	C++17	100 / 100	71 ms	67256 KiB

building

#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;
}

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