Submission #203535

#	Time	Username	Problem	Language	Result	Execution time	Memory
203535		wendy_virgo	Building Bridges (CEOI17_building)	C++14	100 / 100	91 ms	35964 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define taskname "CEOI17_building"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front

template<typename TH>
void _dbg(const char* sdbg, TH h)
{
	cerr << sdbg << " = " << h << "\n";
}

template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
	while (*sdbg != ',') cerr << *sdbg++;
	cerr << " = " << h << ",";
	_dbg(sdbg + 1, t...);
}

#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";

const int N=1e5+5,H=1e6+6;
const int64_t LINF=1e18;

int n,h[N],w[N];
int64_t f[N];

struct Line
{
    int64_t a,b;
};

Line st[4*H];

int64_t Get(Line d,int64_t x)
{
    return d.a*x+d.b;
}

void Build(int id,int l,int r)
{
    if(l==r)
    {
        st[id]={0,LINF};
        return;
    }
    Build(id*2,l,(l+r)/2);
    Build(id*2+1,(l+r)/2+1,r);
    st[id]={0,LINF};
}

void Update(int id,int l,int r,int i,int j,Line val)
{
    if(r<i||l>j)
    {
        return;
    }
    int mid=(l+r)/2;
    if(i<=l&&r<=j)
    {
        if(Get(st[id],l)<=Get(val,l)&&Get(st[id],r)<=Get(val,r))
        {
            return;
        }
        if(Get(st[id],l)>=Get(val,l)&&Get(st[id],r)>=Get(val,r))
        {
            st[id]=val;
            return;
        }
        if(Get(st[id],l)<=Get(val,l)&&Get(st[id],mid)<=Get(val,mid))
        {
            Update(id*2+1,mid+1,r,i,j,val);
            return;
        }
        if(Get(st[id],l)>=Get(val,l)&&Get(st[id],mid)>=Get(val,mid))
        {
            Update(id*2+1,mid+1,r,i,j,st[id]);
            st[id]=val;
            return;
        }
        if(Get(st[id],mid+1)<=Get(val,mid+1)&&Get(st[id],r)<=Get(val,r))
        {
            Update(id*2,l,mid,i,j,val);
            return;
        }
        if(Get(st[id],mid+1)>=Get(val,mid+1)&&Get(st[id],r)>=Get(val,r))
        {
            Update(id*2,l,mid,i,j,st[id]);
            st[id]=val;
            return;
        }
        return;
    }
    Update(id*2,l,mid,i,j,val);
    Update(id*2+1,mid+1,r,i,j,val);
}

int64_t Query(int id,int l,int r,int64_t x)
{
    if(r<x||l>x)
    {
        return LINF;
    }
    int64_t res=Get(st[id],x);
    if(l==r)
    {
        return res;
    }
    res=min(res,Query(id*2,l,(l+r)/2,x));
    res=min(res,Query(id*2+1,(l+r)/2+1,r,x));
    return res;
}

void Sub1()
{
    int64_t sumW=0;
    forinc(i,1,n)
    {
        sumW+=w[i];
    }
    f[1]=-w[1];
    forinc(i,2,n)
    {
        f[i]=LINF;
        forinc(j,1,i-1)
        {
            f[i]=min(f[i],f[j]+(int64_t)(h[i]-h[j])*(h[i]-h[j])-w[i]);
        }
    }
    cout<<f[n]+sumW;
}

void Sub3()
{
    Build(1,0,H-1);
    int64_t sumW=0;
    forinc(i,1,n)
    {
        sumW+=w[i];
    }
    //f[j]+h[i]^2-2*h[i]*h[j]+h[j]^2-w[i]
    //f[j]-2*h[j]+h[j]^2
    f[1]=-w[1];
    Update(1,0,H-1,0,H-1,{(int64_t)-2*h[1],f[1]+(int64_t)h[1]*h[1]});
    forinc(i,2,n)
    {
        f[i]=LINF;
//        forinc(j,1,i-1)
//        {
//            f[i]=min(f[i],f[j]+(int64_t)(h[i]-h[j])*(h[i]-h[j])-w[i]);
//        }
        f[i]=Query(1,0,H-1,h[i])+(int64_t)h[i]*h[i]-w[i];
        Update(1,0,H-1,0,H-1,{(int64_t)-2*h[i],f[i]+(int64_t)h[i]*h[i]});
    }
    cout<<f[n]+sumW;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
//	freopen(taskname".INP","r",stdin);
	#endif // ONLINE_JUDGE
	cin>>n;
	forinc(i,1,n)
	{
	    cin>>h[i];
	}
	forinc(i,1,n)
	{
	    cin>>w[i];
	}
	Sub3();
    return 0;
}

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