oj.uz

Submission #598146

# Submission time Handle Problem Language Result Execution time Memory
598146 2022-07-17T17:41:01 Z devedude Building Bridges (CEOI17_building) C++17
0 / 100
 38 ms 3660 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef tuple<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

const ll inf = LLONG_MAX;

void run();

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    run();
}

inline ll sqr(ll x) {
    return x * x;
}

struct Line {
    ll a, b;
    mutable ll max_x;
    bool operator<(const Line &o) const {
        return a > o.a;
    }
    bool operator<(ll x) const {
        return max_x < x;
    }
};

struct LineContainer : multiset<Line, less<>> {
    ll div(ll n, ll d) {
        return n / d - ((n ^ d) < 0 && n % d);
    }
    bool isect(iterator l, iterator m) {
        if (m == end()) {
            l->max_x = inf;
            return false;
        }
        if (l->a == m->a) {
            l->max_x = (l->b <= m->b) ? inf : -inf;
        } else {
            l->max_x = div(m->b - l->b, l->a - m->a);
        }
        return l->max_x >= m->max_x;
    }
    void add(ll a, ll b) {
        auto cur = insert({a, b, 0}), pre = cur, nex = cur;
        ++nex;
        while (isect(cur, nex)) nex = erase(nex);
        if (cur != begin() && isect(--pre, cur)) {
            cur = erase(cur);
        }
        while ((pre = cur) != begin() && isect(--pre, cur)) {
            erase(pre);
        }
    }
    ll min_y(ll x) {
        auto l = lower_bound(x);
        //cerr << "Minimal for x = " << x << " is line a = " << l->a << " b = " << l->b << " at y = " << l->y(x) << '\n';
        return l->a * x + l->b;
    }
};

int N;
ll h[100005];
ll W[100005];
ll dp[100005];

void run() {
    cin >> N;
    FOR(i, 0, N) cin >> h[i];
    FOR(i, 0, N) {
        ll w; cin >> w;
        W[i+1] = W[i] + w;
    }
    LineContainer lc;
    FOR(i, 1, N) {
        lc.add(-2*h[i-1], dp[i-1] + h[i-1]*h[i-1] - W[i]);
        dp[i] = h[i]*h[i] + W[i] + lc.min_y(h[i]);
    }
    cout << dp[N-1] << '\n';
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 3660 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 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -