Submission #964356

#	Time	Username	Problem	Language	Result	Execution time	Memory
964356		sheldon	Building Bridges (CEOI17_building)	C++14	100 / 100	55 ms	5712 KiB

building

#include <bits/stdc++.h>

using namespace std;

struct line {
    long long m, b;

    long long eval (int x) {
        return m * x + b;
    }
};

struct Node {
    line ln;

    Node *lchild, *rchild;
    Node (line _l) : ln (_l) , lchild (nullptr), rchild (nullptr) {}
};

void insert (Node *node, int l, int r, line lnn) {
    if (l == r) {
        if (node->ln.eval (l) > lnn.eval (l)) {
            node->ln = lnn;
        }
        return;
    }

    int mid = (l + r) / 2;
    if (node->ln.m > lnn.m) {
        swap (node->ln, lnn);
    }
    if (node->ln.eval (mid) > lnn.eval (mid)) {
        swap (node->ln, lnn);

        if (!node->rchild) {
            node->rchild = new Node (lnn);
        } else
        insert (node->rchild, mid + 1, r, lnn);
    } else {
        if (!node->lchild) {
            node->lchild = new Node (lnn);
        } else
        insert (node->lchild, l, mid, lnn);
    }
}


long long query (Node *node, int l, int r, int x) {
    if (l == r) {
        return node->ln.eval (l);
    }

    int mid = (l + r) / 2;

    if (x <= mid) {
        if (node->lchild) {
            return min (node->ln.eval (x), query (node->lchild, l, mid, x));
        }
    } else {
        if (node->rchild) {
            return min (node->ln.eval (x), query (node->rchild, mid + 1, r, x));
        }
    }
    return node->ln.eval (x);
}


void solve() {
    int n;
    cin >> n;
    vector<long long> h (n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    int we;
    cin >> we;
    line li = line {-2 * h[0], -we + h[0] * h[0]};
    Node *root = new Node (li);
    long long pref = we;
    long long ans = 2e18;
    for (int i = 1; i < n; ++i) {
        cin >> we;
        pref += we;
        ans = 1LL * h[i] * h[i] + pref - we + query (root, (int) 0, (int) 1e6, h[i]);
        insert (root, 0, 1e6, line {-2 * h[i], h[i] * h[i] - pref + ans}); 
    }
    cout << ans;
}   

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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