Submission #1172097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172097		AlgorithmWarrior	Building Bridges (CEOI17_building)	C++20	100 / 100	80 ms	64584 KiB

building

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=1e6+5;

struct line{
    long long a,b;
    line(){
        a=0;
        b=INF;
    }
    long long eval(long long x){
        return a*x+b;
    }
};

struct LiChao{
    line v[4*MAX];
    void update(int nod,int st,int dr,line ec){
        int mij=(st+dr)/2;
        if(ec.eval(mij)<v[nod].eval(mij))
            swap(ec,v[nod]);
        if(st<dr){
            if(ec.eval(st)<v[nod].eval(st))
                update(2*nod,st,mij,ec);
            else
                update(2*nod+1,mij+1,dr,ec);
        }
    }
    long long query(int nod,int st,int dr,int poz){
        long long ans=v[nod].eval(poz);
        if(st<dr){
            int mij=(st+dr)/2;
            long long rez;
            if(poz<=mij)
                rez=query(2*nod,st,mij,poz);
            else
                rez=query(2*nod+1,mij+1,dr,poz);
            if(ans>rez)
                ans=rez;
        }
        return ans;
    }
}lichao;

int n;
int h[MAX],w[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>h[i];
    for(i=1;i<=n;++i)
        cin>>w[i];
}

long long dp[MAX];

long long get_dp(){
    int i;
    dp[1]=-w[1];
    line add;
    add.a=-2*h[1];
    add.b=dp[1]+1LL*h[1]*h[1];
    lichao.update(1,0,MAX-5,add);
    for(i=2;i<=n;++i){
        dp[i]=lichao.query(1,0,MAX-5,h[i])+1LL*h[i]*h[i]-w[i];
        add.a=-2*h[i];
        add.b=dp[i]+1LL*h[i]*h[i];
        lichao.update(1,0,MAX-5,add);
    }
    return dp[n];
}

long long solve(){
    long long rez=get_dp();
    int i;
    for(i=1;i<=n;++i)
        rez+=w[i];
    return rez;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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