oj.uz

Submission #106828

# Submission time Handle Problem Language Result Execution time Memory
106828 2019-04-20T16:16:49 Z Frankenween Building Bridges (CEOI17_building) C++17
60 / 100
 133 ms 66572 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), 0);
}


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 52 ms 62968 KB Output is correct
2 Correct 58 ms 63096 KB Output is correct
3 Correct 52 ms 62968 KB Output is correct
4 Correct 61 ms 62968 KB Output is correct
5 Correct 53 ms 63036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 66300 KB Output is correct
2 Correct 105 ms 66296 KB Output is correct
3 Correct 105 ms 66432 KB Output is correct
4 Correct 103 ms 66264 KB Output is correct
5 Correct 106 ms 66268 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 58 ms 63096 KB Output is correct
3 Correct 52 ms 62968 KB Output is correct
4 Correct 61 ms 62968 KB Output is correct
5 Correct 53 ms 63036 KB Output is correct
6 Correct 109 ms 66300 KB Output is correct
7 Correct 105 ms 66296 KB Output is correct
8 Correct 105 ms 66432 KB Output is correct
9 Correct 103 ms 66264 KB Output is correct
10 Correct 106 ms 66268 KB Output is correct
11 Correct 131 ms 66572 KB Output is correct
12 Correct 133 ms 66444 KB Output is correct
13 Correct 98 ms 66484 KB Output is correct
14 Correct 131 ms 66552 KB Output is correct
15 Correct 104 ms 66240 KB Output is correct
16 Correct 93 ms 66204 KB Output is correct
17 Incorrect 106 ms 66460 KB Output isn't correct
18 Halted 0 ms 0 KB -