Submission #1118511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118511		Icelast	Building Bridges (CEOI17_building)	C++17	60 / 100	82 ms	10060 KiB

building

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
// segment add min get, returns INF if no segment added
struct Line{
    ll a = 0, b = INF;
};
struct Lichao {
    vector<Line> L;
    vector<ll> x;
    int N, m;
    Lichao(vector<ll> dom){
        N = 1;
        x = dom;
        m = x.size();
        sort(x.begin(), x.end());
        while(N < m) N*=2;
        for(int i = m; i <= N; i++){
            x.push_back(INF);
        }
        for(int i = N; i >= 1; i--){
            x[i] = x[i-1];
        }
        L.resize(N*2+1, Line());
    };
    bool better(Line a, Line b, ll x){
        return a.a*x + a.b < b.a*x + b.b;
    }
    void addline(int node, int low, int high, Line e){
        int mid = (low+high)/2;
        if(better(e, L[node], x[mid])){
            swap(e, L[node]);
        }
        if(low == high) return;
        bool doml = better(e, L[node], x[low]);
        bool domm = better(e, L[node], x[mid]);
        if(doml != domm){
            addline(node*2, low, mid, e);
        }else{
            addline(node*2+1, mid+1, high, e);
        }
    }
    void add(Line e){
        addline(1, 1, N, e);
    }
    ll query(ll v){
        int k = lower_bound(x.begin()+1, x.end(), v) - x.begin();
        k = k+N-1;
        ll res = INF;
        while(k > 0){
            res = min(res, L[k].a*v + L[k].b);
            k /=2;
        }
        return res;
    }
};
void solve(){
    int n;
    cin >> n;
    vector<ll> h(n+1), w(n+1);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    ll tot = 0;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        tot += w[i];
    }
    vector<ll> dom;
    for(int i = 1; i <= n; i++){
        dom.push_back(h[i]);
    }
    Lichao T(dom);
    vector<ll> f(n+1, 0);
    f[1] = -w[1];
    T.add({-h[1]*2, f[1]+h[1]*h[1]});
    for(int i = 2; i <= n; i++){
        f[i] = T.query(h[i]) + h[i]*h[i] - w[i];
        T.add({-h[i]*2, f[i]+h[i]*h[i]});
    }
    cout << f[n]+tot;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

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