Submission #3951206

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;
const int N = 2e5+5;
const ll M = 1e12+5;

template<ll SZ>
struct LiChao_min{
    struct Line{
        ll k,m;
        Line(){k=0,m=0;}
        Line(ll _k,ll _m){k=_k,m=_m;}
        ll Get(ll x){return k*x+m;}
    };

    struct node{
        node *l, *r;
        Line p;

        node(){p=Line(),l=nullptr,r=nullptr;}
        node(ll k,ll m){p=Line(k,m),l=nullptr,r=nullptr;}
        node(Line _p){p=_p,l=nullptr,r=nullptr;}
    };
    typedef node* pnode;

    pnode root = nullptr;

    void Reset(){root=nullptr;}
    void Set(ll k,ll m){
        Line p = Line(k,m);
        Set(root,0,SZ,p);
    }
    void Set(Line p){
        Set(root,0,SZ,p);
    }
    ll Get(ll x){return Get(root,0,SZ,x);}

    void Set(pnode &v,ll ss,ll se,Line t){
        if(!v){
            v = new node(t);
            return;
        }

        if(t.Get(ss)<v->p.Get(ss)&&t.Get(se)<v->p.Get(se)){v->p=t;return;}
        if(t.Get(ss)>=v->p.Get(ss)&&t.Get(se)>=v->p.Get(se))return;

        ll mid=(ss+se)>>1LL;

        if(t.Get(ss)>v->p.Get(ss)&&t.Get(mid)<v->p.Get(mid)){
            swap(t,v->p);
            Set(v->l,ss,mid,t);
        }else if(t.Get(ss)>v->p.Get(ss)&&t.Get(mid)>v->p.Get(mid)){
            Set(v->r,mid+1,se,t);
        }else if(t.Get(ss)<v->p.Get(ss)&&t.Get(mid)>v->p.Get(mid)){
            Set(v->l,ss,mid,t);
        }else{
            swap(t,v->p);
            Set(v->r,mid+1,se,t);
        }
    }

    ll Get(pnode &v,ll ss,ll se,ll x){
        if(v==nullptr)return INF;
        if(ss==se)return v->p.Get(x);

        ll mid=(ss+se)>>1LL;
        if(x<=mid)return min(v->p.Get(x),Get(v->l,ss,mid,x));
        return min(v->p.Get(x),Get(v->r,mid+1,se,x));
    }
};

LiChao_min<M>tree;
int n;
ll c,h[N],dp[N];

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>c;

    for(int i=1;i<=n;i++)cin>>h[i];

    dp[1]=0;
    tree.Set(-2LL*h[1],h[1]*h[1]);

    for(int i=2;i<=n;i++){
        dp[i]=tree.Get(h[i])+h[i]*h[i]+c;
        tree.Set(-2LL*h[i],dp[i]+h[i]*h[i]);
    }
    cout<<dp[n];
    return 0;
}

Submission Info

Judge Result