제출 #349406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349406		doowey	Building Bridges (CEOI17_building)	C++14	0 / 100	58 ms	4716 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const ll inf = (ll)1e18;
const ld INF = (ld)4e18;
int h[N];
ll w[N];
ll dp[N];

ll sq(ll x){
    return (x * 1ll * x);
}

bool Q;

struct Line{
    ld ai;
    ld bi;
    mutable ld lim;
    // y = ax + b
    bool operator< (const Line &F) const {
        if(!Q){
            return ai < F.ai;
        }
        else{
            return lim < F.lim;
        }
    }
};

struct Hull : multiset<Line>{
    ld intersect(Line A, Line B){
        return (A.bi-B.bi)/(B.ai-A.ai);
    }
    bool check(iterator vv){
        auto pv = vv;
        auto nx = vv;
        if(pv == begin()) return true;
        nx ++ ;
        if(nx == end()) return true;
        if(intersect(*pv,*nx) <= intersect(*pv,*vv)){
            return false;
        }
        return true;
    }
    void upd(iterator &Q){
        auto nx = Q;
        nx ++ ;
        if(nx == end()){
            Q->lim = INF;
        }
        else{
            Q->lim=intersect(*Q, *nx);
        }
    }
    void ins(ld aa, ld bb){ // we construct lower hull
        aa=-aa;
        bb=-bb;
        Q = false;
        auto it = lower_bound({aa, bb, 0});
        if(it != end()){
            if(it->ai == aa){
                if(bb <= it->bi){
                    return;
                }
                else{
                    erase(it);
                }
            }
        }
        it = insert({aa,bb,0});
        if(!check(it)){
            erase(it);
            return;
        }
        auto pv = it;
        while(pv != begin()){
            pv--;
            if(check(pv)) break;
            pv=erase(pv);
        }
        pv = it;
        pv++;
        while(pv != end()){
            if(check(pv)) break;
            pv=erase(pv);
        }
        upd(it);
        if(it != begin()){
            it--;
            upd(it);
        }
    }
    ll get(ld X){
        Q=true;
        auto it = lower_bound({0,0,X});
        return -(X*1ll*(it->ai)+(it->bi));
    }

};

ll ax[N];
ll bx[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> h[i];
    }
    for(int i = 1; i <= n; i ++ ){
        cin >> w[i];
        w[i] += w[i - 1];
        dp[i]=inf;
    }
    dp[1]=0;
    Hull dpv;
    for(int i = 1; i <= n; i ++ ){
        if(i > 1){
            dp[i]=dpv.get(h[i])+sq(h[i])+w[i-1];
        }
        ax[i]=-2ll*h[i];
        bx[i]=sq(h[i])-w[i]+dp[i];
        dpv.ins(ax[i],bx[i]);
    }
    cout << dp[n];
    return 0;
}

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