Submission #964362

#	Time	Username	Problem	Language	Result	Execution time	Memory
964362		sheldon	Building Bridges (CEOI17_building)	C++14	100 / 100	51 ms	6748 KiB

building

    #include <bits/stdc++.h>
     
    using namespace std;
     
    struct line {
        long long m, b;
     
        long long eval (long long x) {
            return m * x + b;
        }
    };
     
    struct Node {
        line li;
     
        Node *lchild, *rchild;
     
        Node (line ln) : li (ln), lchild (nullptr), rchild (nullptr) {}
    };
     
    void insert (Node *node, int l, int r, line ln) {
        if (l == r) {
            if (node->li.eval (l) > ln.eval (l)) {
                node->li = ln;
            }
            return;
        }
     
        int mid = (l + r) / 2;
     
        if (node->li.m > ln.m) {
            swap (node->li, ln);
        }
        
        if (ln.eval (mid) < node->li.eval (mid)) {
            swap (node->li, ln);
            if (!node->rchild) {
                node->rchild = new Node (ln);
            } else {
                insert (node->rchild, mid + 1, r, ln);
            }
        } else {
            if (!node->lchild) {
                node->lchild = new Node (ln);
            } else {
                insert (node->lchild, l, mid, ln);
            }
        }
    }
     
    long long query (Node *node, int l, int r, int x) {
        if (l == r) {
            return node->li.eval (l);
        }
     
        int mid = (l + r) / 2;
        if (x <= mid) {
            if (node->lchild)
            return min (node->li.eval (x), query (node->lchild, l, mid, x));
        } else if (node->rchild) {
            return min (node->li.eval (x), query (node->rchild, mid + 1, r, x));
        }
     
        return node->li.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, 0, (int) 1e6 + 5, h[i]);
            insert (root, 0, (int) 1e6 + 5 , 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