oj.uz

Submission #1090339

# Submission time Handle Problem Language Result Execution time Memory
1090339 2024-09-18T09:06:33 Z alexdumitru Building Bridges (CEOI17_building) C++17
100 / 100
 71 ms 67256 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63064 KB Output is correct
2 Correct 25 ms 63068 KB Output is correct
3 Correct 38 ms 62964 KB Output is correct
4 Correct 26 ms 63016 KB Output is correct
5 Correct 26 ms 63060 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 67120 KB Output is correct
2 Correct 63 ms 67156 KB Output is correct
3 Correct 60 ms 67172 KB Output is correct
4 Correct 61 ms 67000 KB Output is correct
5 Correct 56 ms 66896 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63064 KB Output is correct
2 Correct 25 ms 63068 KB Output is correct
3 Correct 38 ms 62964 KB Output is correct
4 Correct 26 ms 63016 KB Output is correct
5 Correct 26 ms 63060 KB Output is correct
6 Correct 63 ms 67120 KB Output is correct
7 Correct 63 ms 67156 KB Output is correct
8 Correct 60 ms 67172 KB Output is correct
9 Correct 61 ms 67000 KB Output is correct
10 Correct 56 ms 66896 KB Output is correct
11 Correct 69 ms 67256 KB Output is correct
12 Correct 64 ms 67100 KB Output is correct
13 Correct 56 ms 67148 KB Output is correct
14 Correct 71 ms 67152 KB Output is correct
15 Correct 55 ms 66896 KB Output is correct
16 Correct 59 ms 66896 KB Output is correct
17 Correct 52 ms 67152 KB Output is correct
18 Correct 54 ms 67184 KB Output is correct