Submission #1126483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126483		vladilius	Building Bridges (CEOI17_building)	C++20	100 / 100	94 ms	65352 KiB

building

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();

struct DS{
    struct line{
        ll k, b;
        ll operator ()(int x){
            return k * x + b;
        }
    };
    vector<line> t;
    ll mn;
    int n;
    void init(){
        mn = inf;
        n = 1e6;
        t.assign(4 * n, {0, inf});
    }
    void add(int v, int tl, int tr, line f){
        if (tl == tr){
            if (f(tl) < t[v](tl)){
                t[v] = f;
            }
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (t[v].k > f.k) swap(f, t[v]);
        if (f(tm) < t[v](tm)){
            swap(t[v], f);
            add(vv + 1, tm + 1, tr, f);
        }
        else {
            add(vv, tl, tm, f);
        }
    }
    void add(ll k, ll b){
        line f = {k, b};
        mn = min(mn, b);
        add(1, 1, n, f);
    }
    ll get(int v, int tl, int tr, int& x){
        if (tl == tr) return t[v](x);
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (x <= tm){
            return min(t[v](x), get(vv, tl, tm, x));
        }
        return min(t[v](x), get(vv + 1, tm + 1, tr, x));
    }
    ll get(int x){
        if (!x){
            return mn;
        }
        return get(1, 1, n, x);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> h(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>h[i];
    }
    vector<ll> p(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>w[i];
        p[i] = p[i - 1] + w[i];
    }

    auto sq = [&](int x){
        return 1LL * x * x;
    };
    
    vector<ll> dp(n + 1);
    DS T; T.init();
    T.add(-2 * h[1], sq(h[1]) - w[1]);
    for (int i = 2; i <= n; i++){
        dp[i] = (p[i - 1] + sq(h[i])) + T.get(h[i]);
        T.add(-2 * h[i], dp[i] + sq(h[i]) - p[i]);
    }
    cout<<dp[n]<<"\n";
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40