제출 #1166779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166779		Warinchai	Building Bridges (CEOI17_building)	C++20	0 / 100	43 ms	9028 KiB

building

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h[100005];
int w[100005];
int sum[100005];
int querymode=0;
int inf=1e9;
struct line{
    mutable int m,c,p;
    line(int _m=0,int _c=0,int _p=0){
        m=_m,c=_c,p=_p;
    }
    friend bool operator<(line a,line b){
        return querymode?a.p<b.p:a.m>b.m;
    }
};
struct convexhull:multiset<line>{
    int div(int a,int b){
        if(a%b==0||(a^b)>=0)return a/b;
        return a/b-1;
    }
    bool isect(iterator a,iterator b){
        if(b==end())return a->p=inf,false;
        if(a->m==b->m)a->p=(a->c<b->c?inf:-inf);
        else a->p=div(b->c-a->c,a->m-b->m);
        return a->p>=b->p;
    }
    void add(line a){
        auto x=insert(a),y=next(x);
        while(isect(x,y))y=erase(y);
        if((y=x)!=begin()&&isect(--x,y))isect(x,erase(y));
        while((y=x)!=begin()&&isect(--x,y))isect(x,erase(y));
    }
    int query(int x){
        if(empty())return 0;
        querymode=1;
        auto ans=lower_bound(line(0,0,x));
        querymode=0;
        return ans->m*x+ans->c;
    }
}hull;
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)cin>>w[i],sum[i]+=sum[i-1]+w[i];
    hull.insert(line(h[1],h[1]*h[1]-sum[1],0));
    int ans=0;
    for(int i=2;i<=n;i++){
        ans=hull.query(-2*h[i])+h[i]*h[i]-sum[i-1];
        hull.insert(line(h[i],ans+h[i]*h[i]+sum[i],0));
    }
    cout<<ans;
}

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