제출 #349412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349412		doowey	Building Bridges (CEOI17_building)	C++14	100 / 100	91 ms	11628 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{
  ll ai;
  ll bi;
  mutable ld lim;
  bool operator< (const Line &T) const {
    if(Q) return ai < T.ai;
    else return lim < T.lim;
  }
};

struct Hull : multiset<Line>{
    ld intersect(Line F1, Line F2){
        return ld(F1.bi-F2.bi)/ld(F2.ai-F1.ai);
    }
    bool valid(iterator aq){
        iterator pv = aq;
        if(pv == begin()) return true;
        pv -- ;
        iterator nx = aq;
        nx ++ ;
        if(nx == end()) return true;
        return intersect(*pv,*nx) > intersect(*pv,*aq);
    }
    void upd(iterator &it){
        iterator nx = it;
        nx ++ ;
        if(nx == end()){
            it->lim=INF;
        }
        else{
            it->lim=intersect(*it,*nx);
        }
    }
    void add(ll aa, ll bb){
        aa=-aa;
        bb=-bb;
        Q=true;
        Line cur = {aa,bb,INF};
        auto it = lower_bound(cur);
        if(it != end()){
            if(it->ai == aa){
                if(it->bi >= bb){
                    return;
                }
                else{
                    erase(it);
                }
            }
        }
        it = insert(cur);
        if(!valid(it)){
            erase(it);
            return;
        }
        while(1){
            auto nx = it;
            nx++;
            if(nx==end()) break;
            if(valid(nx)) break;
            erase(nx);
        }
        while(it!=begin()){
            auto nx = it;
            nx--;
            if(valid(nx)) break;
            erase(nx);
        }
        upd(it);
        auto pv = it;
        if(pv != begin()){
            pv--;
            upd(pv);
        }
    }
    ll query(ld x){
        Q = false;
        auto it = lower_bound({0,0,x});
        return -((it->ai)*x+(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.query(h[i])+sq(h[i])+w[i-1];
        }
        ax[i]=-2ll*h[i];
        bx[i]=sq(h[i])-w[i]+dp[i];
        dpv.add(ax[i],bx[i]);
    }
    cout << dp[n];
    return 0;
}

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