oj.uz

Submission #106829

# Submission time Handle Problem Language Result Execution time Memory
106829 2019-04-20T16:19:19 Z Frankenween Building Bridges (CEOI17_building) C++17
100 / 100
 129 ms 66472 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod = (ll)1e9 + 7;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = 3.141592653;
const ld EPS = 1e-9;


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


struct line {
    ll k, b;

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


struct lichao {
    vector<line> t;

    lichao(ll n) {
        t.resize(4 * n, {0, inf});
    }

    void add(ll v, ll l, ll r, line cnt) {
        ll mid = (l + r) / 2;
        bool le = cnt.val(l) < t[v].val(l);
        bool m = cnt.val(mid) < t[v].val(mid);
        if (m) {
            swap(t[v], cnt);
        }
        if (l == r) {
            return;
        }
        if (le != m) {
            add(v * 2, l, mid, cnt);
        } else {
            add(v * 2 + 1, mid + 1, r, cnt);
        }
    }

    ll get_min(ll v, ll l, ll r, ll x) {
        if (l == r) {
            return t[v].val(x);
        }
        ll mid = (l + r) / 2;
        if (x <= mid) {
            return min(t[v].val(x), get_min(v * 2, l, mid, x));
        } else {
            return min(t[v].val(x), get_min(v * 2 + 1, mid + 1, r, x));
        }
    }
};


void solve() {
    ll n;
    cin >> n;
    vector<ll> h(n), w(n);
    cin >> h >> w;
    ll MAXH = 1000000;
    lichao kek(MAXH + 1);
    vector<ll> dp(n);
    dp[0] = 0;
    kek.add(1, 0, MAXH, {-2 * h[0], h[0] * h[0] - w[0]});
    for (int i = 1; i < n; i++) {
        dp[i] = kek.get_min(1, 0, MAXH, h[i]) + h[i] * h[i] - w[i];
        kek.add(1, 0, MAXH, {-2 * h[i], dp[i] + h[i] * h[i]});
    }
    cout << dp[n - 1] + accumulate(all(w), 0LL);
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    ll seed = time(0);
    //cerr << "Seed: " << seed << "\n";
    srand(seed);
    solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 51 ms 62968 KB Output is correct
3 Correct 51 ms 62968 KB Output is correct
4 Correct 53 ms 62984 KB Output is correct
5 Correct 54 ms 62968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 65436 KB Output is correct
2 Correct 96 ms 65400 KB Output is correct
3 Correct 109 ms 65452 KB Output is correct
4 Correct 95 ms 65400 KB Output is correct
5 Correct 102 ms 65244 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 51 ms 62968 KB Output is correct
3 Correct 51 ms 62968 KB Output is correct
4 Correct 53 ms 62984 KB Output is correct
5 Correct 54 ms 62968 KB Output is correct
6 Correct 100 ms 65436 KB Output is correct
7 Correct 96 ms 65400 KB Output is correct
8 Correct 109 ms 65452 KB Output is correct
9 Correct 95 ms 65400 KB Output is correct
10 Correct 102 ms 65244 KB Output is correct
11 Correct 120 ms 65320 KB Output is correct
12 Correct 125 ms 65528 KB Output is correct
13 Correct 98 ms 65272 KB Output is correct
14 Correct 129 ms 65348 KB Output is correct
15 Correct 95 ms 65340 KB Output is correct
16 Correct 95 ms 65372 KB Output is correct
17 Correct 109 ms 65400 KB Output is correct
18 Correct 97 ms 66472 KB Output is correct