Submission #711364

#	Time	Username	Problem	Language	Result	Execution time	Memory
711364		Pacybwoah	Building Bridges (CEOI17_building)	C++14	100 / 100	122 ms	66400 KiB

building

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    ll m,b;
    ll val(ll x){
        return m*x+b;
    }
    node(ll _m,ll _b){
        m=_m;
        b=_b;
    }
};
vector<node> seg(4000014,node(0,1e18));
void insert(ll l,ll r,node line,int ind){
    if(l==r){
        if(seg[ind].val(l)>line.val(l)) seg[ind]=line;
        return ;
    }
    ll mid=(l+r)>>1;
    if(seg[ind].m<line.m) swap(seg[ind],line);
    if(line.val(mid)<seg[ind].val(mid)){
        insert(l,mid,seg[ind],ind*2);
        seg[ind]=line;
    }
    else{
        insert(mid+1,r,line,ind*2+1);
    }
}
ll query(int l,int r,ll pos,int ind){
    int mid=(l+r)>>1;
    if(l==r) return seg[ind].val(pos);
    if(pos<=mid){
        return min(query(l,mid,pos,ind*2),seg[ind].val(pos));
    }
    else{
        return min(query(mid+1,r,pos,ind*2+1),seg[ind].val(pos));
    }
}
int main(){
    int n;
    cin>>n;
    vector<ll> dp(n),h(n),w(n);
    ll sum=0;
    for(int i=0;i<n;i++) cin>>h[i];
    for(int i=0;i<n;i++) cin>>w[i],sum+=w[i];
    dp[0]=-w[0];
    insert(0,1000000,node(-2*h[0],dp[0]+h[0]*h[0]),1);
    for(int i=1;i<n;i++){
        dp[i]=query(0,1000000,h[i],1)+h[i]*h[i]-w[i];
        insert(0,1000000,node(-2*h[i],dp[i]+h[i]*h[i]),1);
    }
    cout<<dp[n-1]+sum<<"\n";
    //for(auto x:dp) cout<<x<<" ";
}

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