Submission #169268

#	Time	Username	Problem	Language	Result	Execution time	Memory
169268		kostia244	Building Bridges (CEOI17_building)	C++17	100 / 100	194 ms	66580 KiB

building

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40