oj.uz

Submission #169268

# Submission time Handle Problem Language Result Execution time Memory
169268 2019-12-19T12:08:13 Z kostia244 Building Bridges (CEOI17_building) C++17
100 / 100
 194 ms 66580 KB 
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
struct func {
    ll k, b;
    func(ll k = 0, ll b = 1e18) :k(k), b(b){
    }
    ll operator()(ll x) {
        return k*x+b;
    }
};
const int maxn = 1e6 + 55;
func tree[4*maxn];
void upd(int v, int l, int r, func f) {
    // cout << v << " " << l << " " << r << "\n";
    int m = (l+r)>>1;
    int L = f(l) < tree[v](l);
    int M = f(m) < tree[v](m);
    if(M) {
        swap(f, tree[v]);
    }
    if(r-l<2) return;

    if(L!=M)
        upd(v<<1, l, m, f);
    else
        upd(v<<1|1, m, r, f);
}
ll get(int v, int l, int r, int x) {
    ll m = (l+r)>>1;
    if(r-l<2) return tree[v](x);
    if(x<m)
        return min(tree[v](x), get(v<<1, l, m, x));
    
    return min(tree[v](x), get(v<<1|1, m, r, x));
}
void add(func f) {
    upd(1, 0, 1e6 + 1, f);
}
ll get(ll x) {
    return get(1, 0, 1e6 + 1, x);
}
ll n, h[maxn], w[maxn], pref[maxn];
int main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        pref[i] = pref[i-1]+w[i];
    }
    ll t = 0;
    add(func(-2*h[1], h[1]*h[1]-pref[1]));
    // return 0;
    for(int i = 2; i <= n; i++) {
        t = get(h[i]) + h[i]*h[i] + pref[i-1];
        add(func(-2*h[i], t + h[i]*h[i] - pref[i]));
    }
    cout << t;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 53 ms 62968 KB Output is correct
3 Correct 53 ms 63096 KB Output is correct
4 Correct 54 ms 62968 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 173 ms 65272 KB Output is correct
2 Correct 173 ms 66384 KB Output is correct
3 Correct 173 ms 66580 KB Output is correct
4 Correct 165 ms 66164 KB Output is correct
5 Correct 164 ms 66168 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62968 KB Output is correct
2 Correct 53 ms 62968 KB Output is correct
3 Correct 53 ms 63096 KB Output is correct
4 Correct 54 ms 62968 KB Output is correct
5 Correct 54 ms 62968 KB Output is correct
6 Correct 173 ms 65272 KB Output is correct
7 Correct 173 ms 66384 KB Output is correct
8 Correct 173 ms 66580 KB Output is correct
9 Correct 165 ms 66164 KB Output is correct
10 Correct 164 ms 66168 KB Output is correct
11 Correct 194 ms 66464 KB Output is correct
12 Correct 181 ms 66296 KB Output is correct
13 Correct 177 ms 66500 KB Output is correct
14 Correct 191 ms 66552 KB Output is correct
15 Correct 164 ms 66248 KB Output is correct
16 Correct 164 ms 66352 KB Output is correct
17 Correct 164 ms 66312 KB Output is correct
18 Correct 164 ms 66428 KB Output is correct