Submission #1179896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179896		Ludissey	Building Bridges (CEOI17_building)	C++20	60 / 100	82 ms	96584 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef complex<long long> line;
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
#define m real
#define q imag

int f(line a, int x){
    return a.m()*x+a.q();
}

struct node {
    line l;
    node* left;
    node* right;
    int val(int x){
        return f(l,x);
    }
};
struct segtree{
    node* root;
    int N;
    void build(node* v, int l, int r){
        if(l==r){
            v->l={0,(int)1e17};
            return;
        }
        int mid=(l+r)/2;
        v->left=new node{{0,(int)1e17},NULL,NULL};
        v->right=new node{{0,(int)1e17},NULL,NULL};
        build(v->left,l,mid);
        build(v->right,mid+1,r);
    }
    
    void update(node* v, int l, int r, line ln){
        int mid=(l+r)/2;
        bool mb=v->val(mid)>f(ln,mid);
        bool lb=v->val(l)>f(ln,l);
        if(mb) swap(ln,v->l);
        if(l==r) return;
        if(lb!=mb) {
            update(v->left,l,mid,ln);
        }else {
            update(v->right,mid+1,r,ln);
        }
    }
    
    int query(node* v, int l, int r, int x){
        int mid=(l+r)/2;
        if(l==r) return v->val(x);
        int rt=0;
        if(x>mid) rt=query(v->right,mid+1,r,x);
        else rt=query(v->left,l,mid,x);
        return min(rt,v->val(x));
    }
    segtree(int n){
        root=new node{{0,(int)1e17},NULL,NULL};
        N=n;
        build(root,0,N-1);
    }
    int query(int x){
        return query(root,0,N-1,x);
    }
    void update(line l){
        update(root,0,N-1,l);
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> h(n);
    vector<int> w(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> w[i];
    int sm=accumulate(all(w),0);
    vector<int> dp(n,1e17);
    dp[0]=-w[0];
    int mx=*max_element(all(h));
    segtree seg(mx+2);
    seg.update({-2*h[0],h[0]*h[0]+dp[0]});
    for (int i = 1; i < n; i++)
    {
        dp[i]=seg.query(h[i])+h[i]*h[i]-w[i];
        seg.update({-2*h[i],h[i]*h[i]+dp[i]});
    }
    cout << dp[n-1]+sm << "\n";
    
    return 0;
}

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