oj.uz

Submission #598155

# Submission time Handle Problem Language Result Execution time Memory
598155 2022-07-17T18:00:31 Z devedude Building Bridges (CEOI17_building) C++17
0 / 100
 31 ms 2580 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 ((cur = pre) != begin() && (--pre)->max_x >= cur->max_x) {
            isect(pre, erase(cur));
        }
    }
    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 sumw;
//ll W[100005];
ll dp[100005];

void run() {
    cin >> N;
    FOR(i, 0, N) cin >> h[i];
    FOR(i, 0, N) {
        cin >> w[i];
        sumw += w[i];
        //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]);
        dp[i] = h[i]*h[i] - w[i] + lc.min_y(h[i]);
    }
    cout << dp[N-1] + sumw << '\n';
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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