oj.uz

Submission #258033

# Submission time Handle Problem Language Result Execution time Memory
258033 2020-08-05T08:38:30 Z dolphingarlic Building Bridges (CEOI17_building) C++14
0 / 100
 48 ms 4344 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;
    ll operator()(ll x) { return m * x + c; }
    bool operator==(Line B) { return B.m == m && B.c == c; }
} segtree[4000000];

void insert(Line seg, int node = 1, int l = 0, int r = 1000000) {
    if (segtree[node] == seg) return;
    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 0 ms 384 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Incorrect 1 ms 512 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3064 KB Output is correct
2 Correct 47 ms 3192 KB Output is correct
3 Correct 48 ms 3064 KB Output is correct
4 Correct 47 ms 2936 KB Output is correct
5 Incorrect 43 ms 4344 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 0 ms 384 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Incorrect 1 ms 512 KB Output isn't correct