oj.uz

Submission #964360

# Submission time Handle Problem Language Result Execution time Memory
964360 2024-04-16T17:47:42 Z sheldon Building Bridges (CEOI17_building) C++14
30 / 100
 44 ms 2908 KB 
    #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 && node->lchild) {
            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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 44 ms 2908 KB Output isn't correct
7 Halted 0 ms 0 KB -