Submission #89371

#	Time	Username	Problem	Language	Result	Execution time	Memory
89371		semiauto	Building Bridges (CEOI17_building)	C++14	0 / 100	113 ms	35776 KiB

building

#include <bits/stdc++.h>
using namespace std;
int n,i,j;
long long x,s[100001],h[100001],dp[100001];
pair <long long,long long> tree[20000001];
long long solve(long long x)
	{
	long long p=x+1-1024*1024,ret=100000000000000000;
	while (x)
		{
		ret=min(ret,tree[x].first*p+tree[x].second);
		x/=2;
		}
	return ret;
	}
void add_line(long long a,long long b,int p,int l,int r)
	{
	long long x;
	if ((r-l)==1)
		{
		x=r-1024*1024;
		if (a*x+b<tree[l].first*x+tree[l].second)
			tree[l]=make_pair(a,b);
		return;
		}
	
	bool L=false,M=false;
	l+=1-1024*1024;
	r+=1-1024*1024;
	long long mid=(r+l)/2;
	if (a*l+b<tree[p].first*l+tree[l].second)
		L=true;
	if (a*mid+b<tree[p].first*mid+tree[l].second)
		M=true;
	l-=1-1024*1024;
	r-=1-1024*1024;
	mid=(l+r)/2;
	if (M)
		{
		long long i=a,j=b;
		a=tree[p].first;
		b=tree[p].second;
		tree[p]=make_pair(i,j);
		}
	if (L!=M)
		add_line(a,b,p,l,mid);
	if (L==M)
		add_line(a,b,p,mid,r);
	}
int main()
	{
	cin>>n;
	for (i=1;i<=n;i++)
		cin>>h[i];
	for (i=1;i<=n;i++)
		{
		cin>>x;
		s[i]=s[i-1]+x;
		dp[i]=100000000000000000;
		}
	dp[1]=0;
	for (i=1;i<(2048*1024);i++)
		tree[i]=make_pair(-2*h[1],h[1]*h[1]-s[1]);
	for (i=2;i<=n;i++)
		{
		dp[i]=s[i-1]+h[i]*h[i]+solve(h[i]+1024*1024-1);
		add_line(-2*h[i],h[i]*h[i]+dp[i]-s[i],1,1024*1024,2048*1024);
		}
	cout<<dp[n]<<endl;
	}

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