Submission #89822

#	Time	Username	Problem	Language	Result	Execution time	Memory
89822		giorgikob	Building Bridges (CEOI17_building)	C++14	0 / 100	67 ms	3976 KiB

building

#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define mod 1000000007
#define ll long long
using namespace std;
ll n, m, k, x, y, a, b, t, q, ans;

ll W[500001],H[500001],dp[500001],sum[500001];
struct tree{
	tree* L;
	tree* R;
	ll k,b;
	tree(){
		k=b=0LL;
		L=R=NULL;
	}
};
tree* root=new tree();
double cross(double k,double b,double K,double B){
	return (b-B)/(K-k);
}
void update(tree* node,ll l,ll r,ll K,ll B){
	ll K1=node->k;
	ll B1=node->b;
	if(K1==0 && B1==0){
		node->k=K;
		node->b=B;
		return ;
	}
	double x=cross(K1,B1,K,B);
	ll y=x-10;
	bool ok=( y*K+B < y*K1+B1 );
	
	
	if(ok){
		if(x<l)return;
		if(x>r){
			node->k=K;
			node->b=B;
			return ;	
		}
		
		ll mid=(l+r)/2;
		if(x<=mid) {
			if(node->L == NULL)
				node->L = new tree();
			update(node->L,l,mid,K,B);
		} else 
		if(x>mid) {
			if(node->R == NULL)
				node->R = new tree();
			node->k=K;
			node->b=B;
			update(node->R,mid+1,r,K1,B1);
		}
	} else {
		if(x>r)return;
		if(x<l){
			node->k=K;
			node->b=B;
			return ;	
		}
		
		ll mid=(l+r)/2;
		if(x>mid) {
			if(node->R == NULL)
				node->R = new tree();
			update(node->R,mid+1,r,K,B);
		} else 
		if(x<=mid) {
			if(node->L == NULL)
				node->L = new tree();
			node->k=K;
			node->b=B;
			update(node->L,l,mid,K1,B1);
		}	
	}
}
ll get(tree* node,ll l,ll r,ll x){
	if(l==r)
		return node->k*x+node->b;
	ll mid=(l+r)/2;
	if(x<=mid){
		if(node->L==NULL)
			return node->k*x+node->b;
		else{
			ll y=get(node->L,l,mid,x);
			return min(y,node->k*x+node->b);		
		}
	} else {
		if(node->R==NULL)
			return node->k*x+node->b;
		else{
			ll y=get(node->R,mid+1,r,x);
			return min(y,node->k*x+node->b);
		}
	}	
}
main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>H[i];
	
	for(int i=1;i<=n;i++)
		cin>>W[i],sum[i]=sum[i-1]+W[i];
	
	update(root,0,1e6,-2*H[1],H[1]*H[1]-sum[1]);
	for(int i=2;i<=n;i++){
		dp[i]=H[i]*H[i]+sum[i-1]+get(root,0,1e6,H[i]);
		//cout<<get(root,0,1e6,H[i])<<" ";
		update(root,0,1e6,-2*H[i],H[i]*H[i]+dp[i]-sum[i]);
		//cout<<dp[i]<<endl;
	}
	
	cout<<dp[n]<<endl;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Compilation message (stderr)

building.cpp:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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