oj.uz

Submission #258026

# Submission time Handle Problem Language Result Execution time Memory
258026 2020-08-05T08:29:09 Z dolphingarlic Building Bridges (CEOI17_building) C++14
0 / 100
 49 ms 4600 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Line {
    ll m, c;
    inline ll operator()(ll x) { return m * x + c; }
} segtree[4000001];

void insert(Line seg, int node = 1, int l = 0, int r = 1000000) {
    if (l == r) {
        if (seg(l) < segtree[node](l)) segtree[node] = seg;
    } else {
        int mid = (l + r) / 2;
        if (segtree[node].m <= seg.m) swap(segtree[node], seg);
        if (segtree[node](mid) > seg(mid)) {
            swap(segtree[node], seg);
            insert(seg, node * 2, l, mid);
        } else insert(seg, node * 2 + 1, mid + 1, r);
    }
}

ll query(ll x, int node = 1, int l = 0, int r = 1000000) {
    if (l == r) return segtree[node](x);
    int mid = (l + r) / 2;
    if (x < mid) return min(segtree[node](x), query(x, node * 2, l, mid));
    return min(segtree[node](x), query(x, node * 2 + 1, mid + 1, r));
}

ll h[100001], w[100001], tot = 0, dp[100001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n + 1) cin >> h[i];
    FOR(i, 1, n + 1) {
        cin >> w[i];
        tot += w[i];
    }

    dp[1] = -w[1];
    FOR(i, 2, n + 1) {
        insert({-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]});
        dp[i] = query(h[i]) - w[i] + h[i] * h[i];
    }

    cout << tot + dp[n];
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Incorrect 2 ms 1792 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4216 KB Output is correct
2 Correct 49 ms 4216 KB Output is correct
3 Correct 47 ms 4152 KB Output is correct
4 Correct 45 ms 3832 KB Output is correct
5 Incorrect 40 ms 4600 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Incorrect 2 ms 1792 KB Output isn't correct