oj.uz

Submission #89371

# Submission time Handle Problem Language Result Execution time Memory
89371 2018-12-12T12:18:58 Z semiauto Building Bridges (CEOI17_building) C++14
0 / 100
 113 ms 35776 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33144 KB Output is correct
2 Incorrect 30 ms 33268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 35696 KB Output is correct
2 Incorrect 113 ms 35776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33144 KB Output is correct
2 Incorrect 30 ms 33268 KB Output isn't correct
3 Halted 0 ms 0 KB -