제출 #988661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988661		Aviansh	Building Bridges (CEOI17_building)	C++17	30 / 100	68 ms	68444 KiB

building

#include <bits/stdc++.h>

using namespace std;

struct line{
    double m,c;
    double eval(double x){
        return (m*x)+c;
    }
    double intersect(line l){
        return (l.c-c)/(m-l.m);
    }
};

template<class T> class liChaoTree{
    private:
        int n;
        line *st;
        line def = {0,INT_MAX};
    public:
        liChaoTree(int siz){
            int x = (int) pow(2,ceil(log2(siz)));
            n=siz-1;
            st=new line[2*x];
            realST(0,n,0);
        }
        void realST(int l, int r, int ind){
            st[ind]=def;
            if(l!=r){
                int mid = (l+r)/2;
                realST(l,mid,ind*2+1);
                realST(mid+1,r,ind*2+2);
            }
        }
        double realQuer(double x, int l, int r, int ind){
            int mid = (l+r)/2;
            if(r-l==1){
                return st[ind].eval(x);
            }
            else if(x<mid){
                return min(st[ind].eval(x),realQuer(x,l,mid,ind*2+1));
            }
            else{
                return min(st[ind].eval(x),realQuer(x,mid,r,ind*2+2));
            }
        }
        double quer(double x){
            return realQuer(x,0,n,0);
        }
        void realUpdate(int s, int e, line nw, int ind){
            int mid = (s+e)/2;
            bool lef = st[ind].eval(s) > nw.eval(s);
            bool mi = st[ind].eval(mid) > nw.eval(mid);
            if(mi){
                swap(st[ind],nw);
            }
            if(e-s==1){
                return;
            }
            else if(lef!=mi){
                realUpdate(s,mid,nw,ind*2+1);
            }
            else{
                realUpdate(mid,e,nw,ind*2+2);
            }
        }
        void addLine(line l){
            realUpdate(0,n,l,0);
        }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin >> n;
    long long h[n],w[n];
    long long tot = 0;
    for(long long i = 0;i<n;i++){
        cin >> h[i];
    }
    for(long long i = 0;i<n;i++){
        cin >> w[i];
        tot+=w[i];
    }
    long long dp[n];
    dp[0]=-w[0];
    liChaoTree<long long> lct(2e6+50);
    for(long long i = 1;i<n;i++){
        line l;
        l.m=-2*h[i-1];
        l.c=dp[i - 1] + h[i - 1] * h[i - 1];
        lct.addLine(l);
        dp[i]=lct.quer(h[i]) - w[i]+h[i]*h[i];
    }
    cout << tot+dp[n-1];
    return 0;
}

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