Submission #1135018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135018		LeonidCuk	Building Bridges (CEOI17_building)	C++20	0 / 100	53 ms	65332 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(najdi(k,m)<najdi(st[i],m))
    {
        swap(k,st[i]);
        if(l!=r)update(i*2+1,m+1,r,k);
    }
    else if(najdi(k,m)==najdi(st[i],m))
    {
        if(najdi(k,l)<najdi(st[i],l))swap(k,st[i]);
        if(l!=r)update(i*2+1,m+1,r,k);
    }
    else if(l!=r)
    {
        update(i*2,l,m,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 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;
}

Compilation message (stderr)

building.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>>
      |                         ^
building.cpp: In function 'long long int getsum(int, int, int, long long int)':
building.cpp:35:35: warning: control reaches end of non-void function [-Wreturn-type]
   35 |     else min(najdi(st[i],x),getsum(i*2+1,m+1,r,x));
      |                             ~~~~~~^~~~~~~~~~~~~~~

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