Submission #985909

#	Time	Username	Problem	Language	Result	Execution time	Memory
985909		alexdd	Building Bridges (CEOI17_building)	C++17	100 / 100	48 ms	35676 KiB

building

#include<iostream>
using namespace std;
#define int long long
const int INF = 1e18;
struct line
{
    int b,m;
    int eval(int x){return b + x*m;}
};
line lichao[2100000];
void upd(int nod, int st, int dr, line newv)
{
    int mij=(st+dr)/2;
    if(newv.eval(mij) < lichao[nod].eval(mij))
        swap(lichao[nod],newv);
    if(st==dr)
        return;
    if(newv.eval(st) < lichao[nod].eval(st))
        upd(nod*2,st,mij,newv);
    else
        upd(nod*2+1,mij+1,dr,newv);
}
int qry(int nod, int st, int dr, int poz)
{
    int mnm = lichao[nod].eval(poz);
    if(st==dr)
        return mnm;
    int mij=(st+dr)/2;
    if(poz<=mij) mnm = min(mnm, qry(nod*2,st,mij,poz));
    else mnm = min(mnm, qry(nod*2+1,mij+1,dr,poz));
    return mnm;
}
int n;
int h[100005],prefw[100005];
int dp[100005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int i=1;i<2100000;i++)
        lichao[i] = {INF,0};
    for(int i=1;i<=n;i++)
    {
        cin>>prefw[i];
        prefw[i] += prefw[i-1];
        if(i==1)
        {
            dp[i]=0;
        }
        else
        {
            dp[i] = (h[i]*h[i]+prefw[i-1]) + qry(1,0,1000000,h[i]);
        }
        line aux = {dp[i] + h[i]*h[i] - prefw[i], -2*h[i]};
        upd(1,0,1000000,aux);
    }
    cout<<dp[n];
    return 0;
}

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