Submission #556706

#	Time	Username	Problem	Language	Result	Execution time	Memory
556706		status_coding	Building Bridges (CEOI17_building)	C++14	100 / 100	111 ms	66512 KiB

building

#include <bits/stdc++.h>

using namespace std;

struct lineS
{
    long long m=0, n=1e18;

    lineS(){}

    lineS(long long m, long long n)
    {
        this->m=m;
        this->n=n;
    }
};

vector<lineS> lichao;

long long n;
long long h[100005], val[100005];

long long dp[100005];

long long f(long long x, lineS lin)
{
    return x * lin.m + lin.n;
}

void addLine(long long st, long long dr, long long p, lineS nou)
{
    long long mij = (st+dr)/2;

    if( f(mij, nou) < f(mij, lichao[p]) )
        swap(nou, lichao[p]);

    if(dr - st == 1)
        return;

    if( f(st, nou) < f(st, lichao[p]) )
        addLine(st, mij, 2*p, nou);

    if( f(dr, nou) < f(dr, lichao[p]))
        addLine(mij, dr, 2*p+1, nou);
}

long long query(long long x, long long st, long long dr, long long p)
{
    //cout<<st<<' '<<dr<<' '<<x<<'\n';

    if(dr - st == 1)
        return f(x, lichao[p]);

    long long mij = (st+dr)/2;

    if(x < mij)
        return min( f(x, lichao[p]), query(x, st, mij, 2*p) );
    else
        return min( f(x, lichao[p]), query(x, mij, dr, 2*p+1) );
}

int main()
{
    long long maxH = 1e6 + 1;
    lichao.resize(4 * maxH + 4);

    cin>>n;

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

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

    for(int i=1;i<=n;i++)
    {
        if(i == 1)
            dp[i] = -val[i];
        else
        {
            //cout<<"query "<<h[i]<<' '<<query(h[i], 0, maxH, 1)<<'\n';
            dp[i] = query(h[i], 0, maxH, 1) + h[i]*h[i] - val[i];
        }


        //cout<<"add "<<-2 * h[i]<<' '<<dp[i] + h[i]*h[i]<<'\n';
        addLine(0, maxH, 1, lineS(-2 * h[i], dp[i] + h[i]*h[i]));
    }

    long long ans = dp[n];
    for(int i=1;i<=n;i++)
        ans += val[i];

    cout<<ans;
    return 0;
}

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