Submission #858371

#	Time	Username	Problem	Language	Result	Execution time	Memory
858371		Tenis0206	Building Bridges (CEOI17_building)	C++11	100 / 100	53 ms	67320 KiB

building

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;
const int hmax = 1e6;
const int oo = LLONG_MAX;

int n;
int h[nmax + 5], w[nmax + 5];
int sp[nmax + 5];

int dp[nmax + 5];

pair<int,int> lc[4 * hmax + 5];

int get_val(pair<int,int> f, int x)
{
    if(f.first==oo)
    {
        return oo;
    }
    return f.first * x + f.second;
}

bool is_smaller(pair<int,int> f, pair<int,int> g, int x)
{
    return get_val(f, x) < get_val(g, x);
}

int query(int poz, int nod, int st, int dr)
{
    if(st==dr)
    {
        return get_val(lc[nod], poz);
    }
    int mij = (st + dr) >> 1;
    if(poz <= mij)
    {
        return min(get_val(lc[nod],poz), query(poz,nod*2,st,mij));
    }
    return min(get_val(lc[nod],poz), query(poz,nod*2+1,mij+1,dr));
}

void update(pair<int,int> f, int nod, int st, int dr)
{
    int mij = (st + dr) >> 1;
    bool okst = is_smaller(f, lc[nod], st);
    bool okmij = is_smaller(f, lc[nod], mij);
    if(okmij)
    {
        swap(f,lc[nod]);
    }
    if(st==dr)
    {
        return;
    }
    if(okst!=okmij)
    {
        update(f,nod*2,st,mij);
    }
    else
    {
        update(f,nod*2+1,mij+1,dr);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        sp[i] = sp[i - 1] + w[i];
    }
    for(int i=1;i<=4*hmax;i++)
    {
        lc[i] = {oo,oo};
    }
    dp[1] = 0;
    update({-2 * h[1],dp[1] + 1LL * h[1] * h[1] - sp[1]},1,1,hmax);
    for(int i=2;i<=n;i++)
    {
        dp[i] = query(h[i],1,1,hmax) + 1LL * h[i] * h[i] + sp[i - 1];
        update({-2 * h[i],dp[i] + 1LL * h[i] * h[i] - sp[i]},1,1,hmax);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

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