Submission #534666

#	Time	Username	Problem	Language	Result	Execution time	Memory
534666		alextodoran	Building Bridges (CEOI17_building)	C++17	100 / 100	92 ms	68680 KiB

building

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int H_MAX = 2000000;

const ll INF = LLONG_MAX;

int n;
int h[N_MAX + 2];
int w[N_MAX + 2];

ll dp[N_MAX + 2];

struct Line {
    int a; ll b;
    ll operator () (const int &x) const {
        return (ll) a * x + b;
    }
};

Line LiChao[H_MAX * 4 + 2];

void build (int node, int l, int r) {
    LiChao[node] = Line{0, -INF};
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);
}
void build () {
    build(1, 1, H_MAX);
}
void update (int node, int l, int r, Line ln) {
    if (l == r) {
        if (LiChao[node](l) < ln(l)) {
            swap(LiChao[node], ln);
        }
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (LiChao[node].a > ln.a) {
        swap(LiChao[node], ln);
    }
    if (LiChao[node](mid) < ln(mid)) {
        swap(LiChao[node], ln);
        update(lSon, l, mid, ln);
    } else {
        update(rSon, mid + 1, r, ln);
    }
}
void update (Line ln) {
    update(1, 1, H_MAX, ln);
}
ll query (int node, int l, int r, int x) {
    if (l == r) {
        return LiChao[node](x);
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (x <= mid) {
        return max(LiChao[node](x), query(lSon, l, mid, x));
    } else {
        return max(LiChao[node](x), query(rSon, mid + 1, r, x));
    }
}
ll query (int x) {
    return query(1, 1, H_MAX, x);
}

void insertDp (int i) {
    update(Line{2 * h[i], -dp[i] - (ll) h[i] * h[i]});
}
ll getMin (int i) {
    return w[i] + (ll) h[i] * h[i] - query(h[i]);
}

int main () {
    ios_base::sync_with_stdio(false);
    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];
    }

    ll sumw = 0;
    for (int i = 1; i <= n; i++) {
        sumw += w[i];
        w[i] = -w[i];
    }

    build();
    dp[1] = w[1]; insertDp(1);
    for (int i = 2; i <= n; i++) {
        dp[i] = getMin(i); insertDp(i);
    }
    cout << dp[n] + sumw << "\n";

    return 0;
}

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