Submission #1295385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295385		sunflower	Building Bridges (CEOI17_building)	C++17	100 / 100	50 ms	9552 KiB

building

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b);i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

template <class T>
void remove_dup(T &v) {
    sort(ALL(v));
    v.resize(unique(ALL(v)) - v.begin());
}
template <class X, class Y>
int POS(X x, const vector<Y> &v) {
    return lower_bound(ALL(v), x) - v.begin();
}

#define MAX_N 100100
int n;

vector<int> values;

int h[MAX_N + 2], w[MAX_N + 2];
ll pre[MAX_N + 2], dp[MAX_N + 2];

struct Line {
    ll a, b;

    Line(ll _a = 0, ll _b = 1e18) {
        a = _a, b = _b;
    }

    ll calc(ll x) {
        return a * x + b;
    }
};

struct minTree {
    Line seg[4 * MAX_N + 2];

    void update(int id, int l, int r, Line newLine) {
        if (l == r) {
            seg[id] = (seg[id].calc(values[l]) < newLine.calc(values[l]) ? seg[id] : newLine);
            return;
        }

        int g = (l + r) >> 1;

        bool midBetter = (seg[id].calc(values[g]) > newLine.calc(values[g]));
        bool leftBetter = (seg[id].calc(values[l]) > newLine.calc(values[l]));

        if (midBetter) swap(seg[id], newLine);

        if (midBetter != leftBetter) update(id << 1, l, g, newLine);
        else {
            if (seg[id].calc(values[r]) > newLine.calc(values[r])) update(id << 1 | 1, g + 1, r, newLine);
        }
    }

    ll get(int id, int l, int r, int pos) {
        ll cur = seg[id].calc(values[pos]);
        if (l == r) return cur;

        int g = (l + r) >> 1;
        if (pos <= g) return min(cur, get(id << 1, l, g, pos));
        else return min(cur, get(id << 1 | 1, g + 1, r, pos));
    }
} lct;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    // freopen("test.inp","r",stdin);
    // freopen("test.out","w",stdout);
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) cin >> w[i], pre[i] = pre[i - 1] + w[i];

    /// h[j] - h[i]

    FOR(i, 1, n) values.push_back(h[i]);
    sort(ALL(values));
    values.resize(unique(ALL(values)) - values.begin());

/// have to set start_b = INF because have to exist 1 id before J to build bridges connect from id -> j;
/// if set = 0, it will skip that id if values of it > Line(0, 0);
    dp[1] = 0;
    FOR(i, 1, n) {
        if (i > 1) dp[i] = 1e18;
        minimize(dp[i], pre[i - 1] + 1LL * h[i] * h[i] + lct.get(1, 0, (int) values.size() - 1, POS(h[i], values)));

        ll line_a = -2 * h[i];
        ll line_b = 1LL * h[i] * h[i] - pre[i] + dp[i];

        lct.update(1, 0, (int) (values.size()) - 1, Line(line_a, line_b));
    }

    cout << dp[n];

    return 0;
}

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