Submission #1135056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135056		LeonidCuk	Building Bridges (CEOI17_building)	C++20	100 / 100	88 ms	65340 KiB

building

#include <bits/stdc++.h>
using namespace std;
struct line
{
    long long int a,b;
};
vector<line>st;
long long int najdi(line l,long long int k)
{
    return l.a*k+l.b;
}
void update(int i,int l,int r,line k)
{
    int m=(l+r)/2;
    if(k.a>st[i].a)swap(k,st[i]);
    if(najdi(k,m)<najdi(st[i],m))
    {
        swap(k,st[i]);
        if(l!=r)update(2*i,l,m,k);
    }
    else if(l!=r)
    {
        update(2*i+1,m+1,r,k);
    }
}
long long int getsum(int i,int l,int r,long long int x)
{
    int m=(l+r)/2;
    if(l==r)return najdi(st[i],x);
    if(x<=m)return min(najdi(st[i],x),getsum(i*2,l,m,x));
    else return min(najdi(st[i],x),getsum(i*2+1,m+1,r,x));
}
int main()
{
    long long int n,a,sum=0;
    cin>>n;
    vector<long long int>v[2],dp;
    dp.resize(n);
    for(int i=0;i<n;i++)
    {
        cin>>a;
        v[0].push_back(a);
    }
    for(int i=0;i<n;i++)
    {
        cin>>a;
        v[1].push_back(a);
    }
    st.resize(4*1000001+1,{-2*v[0][0],v[0][0]*v[0][0]-v[1][0]});
    sum=v[1][0];
    for(int i=1;i<n;i++)
    {
        dp[i]=v[0][i]*v[0][i]+sum+getsum(1,0,1000000,v[0][i]);
        sum+=v[1][i];
        line temp={-2*v[0][i],dp[i]+v[0][i]*v[0][i]-sum};
        update(1,0,1000000,temp);
    }
    cout<<dp[n-1];
    return 0;
}

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