Submission #3951206


Source Code Expand

Copy
#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

Submission Time
Task Z - Frog 3
User Vasiljko
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2255 Byte
Status
Exec Time 81 ms
Memory 12800 KB

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 100 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 1_25, 1_26, 1_27, 1_28, 1_29, 1_30, 1_31, 1_32, 1_33, 1_34, 1_35
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 74 ms 12800 KB
1_03 75 ms 12544 KB
1_04 81 ms 12672 KB
1_05 79 ms 11776 KB
1_06 56 ms 8320 KB
1_07 75 ms 12672 KB
1_08 74 ms 9984 KB
1_09 75 ms 9856 KB
1_10 79 ms 9984 KB
1_11 78 ms 9856 KB
1_12 78 ms 9600 KB
1_13 78 ms 9344 KB
1_14 77 ms 9344 KB
1_15 76 ms 9216 KB
1_16 67 ms 8192 KB
1_17 59 ms 6912 KB
1_18 50 ms 5760 KB
1_19 62 ms 9600 KB
1_20 63 ms 8576 KB
1_21 63 ms 8320 KB
1_22 55 ms 6144 KB
1_23 58 ms 7296 KB
1_24 53 ms 6016 KB
1_25 62 ms 8448 KB
1_26 68 ms 9344 KB
1_27 60 ms 7168 KB
1_28 63 ms 8192 KB
1_29 63 ms 8192 KB
1_30 71 ms 8448 KB
1_31 61 ms 8192 KB
1_32 51 ms 5632 KB
1_33 70 ms 10368 KB
1_34 57 ms 7040 KB
1_35 58 ms 7040 KB