oj.uz

Submission #585526

# Submission time Handle Problem Language Result Execution time Memory
585526 2022-06-29T04:07:22 Z talant117408 Building Bridges (CEOI17_building) C++17
100 / 100
 169 ms 80284 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 1e6 + 7;

struct line {
    ll m, b;
    line() {
        m = 0;
        b = 1e18;
    }
    line(ll _m, ll _b) {
        m = _m; 
        b = _b;
    }
    ll operator()(ll x) {
        return m * x + b;
    }
} tree[N * 4];

void update(int v, int l, int r, line seg) {
    if (l == r - 1) {
        if (seg(l) < tree[v](l))
            tree[v] = seg;
        return;
    }
    int mid = (l + r) >> 1;
    if (seg.m > tree[v].m) 
        swap(seg, tree[v]);
    if (tree[v](mid) > seg(mid)) {
        swap(seg, tree[v]);
        update(v * 2, l, mid, seg);
    }
    else {
        update(v * 2 + 1, mid, r, seg);
    }
}

ll get(int v, int l, int r, ll x) {
    if (l == r - 1) {
        return tree[v](x);
    }
    int mid = (l + r) >> 1;
    if (x < mid) return min(tree[v](x), get(v * 2, l, mid, x));
    else return min(tree[v](x), get(v * 2 + 1, mid, r, x));
}

void solve() {
    int n;
    cin >> n;
    vector <ll> h(n), w(n), pref(n);
    for (auto &to : h) cin >> to;
    for (auto &to : w) cin >> to;
    pref[0] = w[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + w[i];
    }
    
    vector <vector <ll>> dp(n, vector <ll> (2, 2e18));
    dp[0][1] = 0;
    multiset <ll> st;
    st.insert(-pref[0]);
    /*
    m = -2 * h[j]
    x = h[i]
    b = dp[j][1] - pref[j] + h[j]^2 
    c = pref[i - 1] + h[i]^2
    */
    update(1, 0, N, line(-2 * h[0], dp[0][1] - pref[0] + h[0] * h[0]));
    for (int i = 1; i < n; i++) {
        dp[i][0] = (*st.begin()) + pref[i];
        dp[i][1] = get(1, 0, N, h[i]) + pref[i - 1] + h[i] * h[i];
        st.insert(dp[i][0] - pref[i]);
        st.insert(dp[i][1] - pref[i]);
        update(1, 0, N, line(-2 * h[i], dp[i][1] - pref[i] + h[i] * h[i]));
    }
    cout << dp[n - 1][1];
}

// (h[i] - h[j]) ^ 2 = h[i] ^ 2 - 2 * h[i] * h[j] + h[j] ^ 2

/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62796 KB Output is correct
2 Correct 29 ms 62932 KB Output is correct
3 Correct 27 ms 62924 KB Output is correct
4 Correct 25 ms 62992 KB Output is correct
5 Correct 26 ms 63056 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 80052 KB Output is correct
2 Correct 131 ms 80068 KB Output is correct
3 Correct 152 ms 80096 KB Output is correct
4 Correct 136 ms 80040 KB Output is correct
5 Correct 110 ms 80204 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62796 KB Output is correct
2 Correct 29 ms 62932 KB Output is correct
3 Correct 27 ms 62924 KB Output is correct
4 Correct 25 ms 62992 KB Output is correct
5 Correct 26 ms 63056 KB Output is correct
6 Correct 132 ms 80052 KB Output is correct
7 Correct 131 ms 80068 KB Output is correct
8 Correct 152 ms 80096 KB Output is correct
9 Correct 136 ms 80040 KB Output is correct
10 Correct 110 ms 80204 KB Output is correct
11 Correct 169 ms 80068 KB Output is correct
12 Correct 163 ms 80096 KB Output is correct
13 Correct 103 ms 80144 KB Output is correct
14 Correct 169 ms 80064 KB Output is correct
15 Correct 120 ms 80140 KB Output is correct
16 Correct 115 ms 80068 KB Output is correct
17 Correct 104 ms 80284 KB Output is correct
18 Correct 114 ms 80140 KB Output is correct