oj.uz

Submission #571658

# Submission time Handle Problem Language Result Execution time Memory
571658 2022-06-02T13:09:40 Z piOOE Building Bridges (CEOI17_building) C++17
100 / 100
 71 ms 7616 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;
typedef long double ld;
typedef double db;


mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int N = 100001, infI = 1e9 + 7;
const ll infL = 3e18;

struct line {
    ll k = infI, b = infL;

    ll f(int x) {
        return k * x + b;
    }

    line() = default;

    line(ll a, ll bb) {
        k = a, b = bb;
    }
};

vector<line> t;
int sz = 1;
vector<int> X;

void add_line(line nw, int x = 1, int lx = 0, int rx = sz) {
    int mid = (lx + rx) >> 1;
    if (nw.f(X[mid]) < t[x].f(X[mid])) {
        swap(nw, t[x]);
    }
    if (lx + 1 == rx) {
        return;
    }
    if (t[x].k >= nw.k) {
        add_line(nw, x << 1 | 1, mid, rx);
    } else {
        add_line(nw, x << 1, lx, mid);
    }
}

ll get(int i) {
    int x = i + sz;
    ll ans = infL;
    while (x) {
        ans = min(ans, t[x].f(X[i]));
        x >>= 1;
    }
    return ans;
}

int h[N], w[N];

ll dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (sz < n) {
        sz <<= 1;
    }
    t.resize(sz << 1);
    X.resize(sz);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
        X[i] = h[i];
    }

    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }
    sort(begin(X), begin(X) + n);
    for (int i = n; i < sz; ++i)
        X[i] = X[i - 1];
    dp[0] = 0;
    add_line({-2 * h[0], h[0] * (ll)h[0] - w[0]});
    ll sum = w[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = get(lower_bound(all(X), h[i]) - begin(X)) + h[i] * (ll)h[i] + sum;
        sum += w[i];
        add_line({-2 * h[i], h[i] * (ll)h[i] + dp[i] - sum});
    }
    cout << dp[n - 1];
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6456 KB Output is correct
2 Correct 60 ms 7444 KB Output is correct
3 Correct 65 ms 7492 KB Output is correct
4 Correct 64 ms 7404 KB Output is correct
5 Correct 31 ms 7416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 56 ms 6456 KB Output is correct
7 Correct 60 ms 7444 KB Output is correct
8 Correct 65 ms 7492 KB Output is correct
9 Correct 64 ms 7404 KB Output is correct
10 Correct 31 ms 7416 KB Output is correct
11 Correct 60 ms 7608 KB Output is correct
12 Correct 59 ms 7500 KB Output is correct
13 Correct 71 ms 7556 KB Output is correct
14 Correct 70 ms 7616 KB Output is correct
15 Correct 36 ms 7372 KB Output is correct
16 Correct 30 ms 7328 KB Output is correct
17 Correct 26 ms 7500 KB Output is correct
18 Correct 26 ms 7568 KB Output is correct