Submission #89358

#	Time	Username	Problem	Language	Result	Execution time	Memory
89358		nicksona	Building Bridges (CEOI17_building)	C++14	0 / 100	25 ms	2680 KiB

building

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
struct Str {
	int k;
	int b;
};
Str T[100001];
double Cross (int k1,int b1,int k2,int b2){
	return ((double) (b2-b1)/(k1-k2));
}
void update (int p,int l,int r,int k,int b){
	double  K=Cross (k,b,T[p].k,T[p].b);
	int mid = l + r >> 1;
	
	if (r<l){
		return ;
	}
	
	if((K<l||K>r)||(l==r)){
		if (l*T[p].k+T[p].b>k*l+b){
			T[p].k=k;
			T[p].b=b;
		}
		return ;
	}
	
	if(T[p].b==0&&T[p].k==0){
		T[p].k=k;
		T[p].b=b;		
		return ;
	}
	
	if(K>mid){
		if (l*T[p].k+T[p].b>k*l+b){
			int tempk,tempb;
			tempk=T[p].k;
			tempb=T[p].b;
			T[p].k=k;
			T[p].b=b;
			update (p+p+1,mid+1,r,tempk,tempb);
		}
		else{
			update (p+p+1,mid+1,r,k,b);	
		}
	}	
	else{
		if (r*T[p].k+T[p].b>k*r+b){
			int tempk,tempb;
			tempk=T[p].k;
			tempb=T[p].b;
			T[p].k=k;
			T[p].b=b;
			update (p+p,l,mid,tempk,tempb);
		}
		else{
			update (p+p,l,mid,k,b);	
		}
	}
}

ll f (int p,int l,int r,int x){
	int mid = l + r >> 1;
	if (T[p].k==0&&T[p].b==0){
		return 1000000000000000000;
	}
	if (r==l){
		return x*T[p].k+T[p].b;
	}
	if (r<=l){
		return 1000000000000000000;
	}
	
	if (x>mid){
		return min((ll) (x*T[p].k+T[p].b),f(p+p+1,mid+1,r,x));
	}
	else{
		return min((ll) (x*T[p].k+T[p].b),f(p+p,l,mid,x));	
	}
}
int n;
int h[100001],w[100001];
int dp[100001];
main () {
	ios::sync_with_stdio(false);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>h[i];
	}
	
	for (int i=1;i<=n;i++){
		cin>>w[i];
		w[i]+=w[i-1];
	}
		
	int k,b;
	
	dp[1]=0;
	b=h[1]*h[1]-w[1];
	k=-2*h[1];	
		
	update (1,1,n,k,b);
		
	for (int i=2;i<=n;i++){
		ll ans=f (1,1,n,h[i]);
		dp[i]=h[i]*h[i]+w[i-1]+ans;
		b=dp[i]+h[i]*h[i]-w[i];
		k=-2*h[i];	
		update (1,1,n,k,b);
	}
	cout<<dp[n]<<endl;
	return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
  _   _   _          _
 | \ | | (_)        | |
 |  \| |  _    ___  | | __  ___    ___    _ __     __ _
 | . ` | | |  / __| | |/ / / __|  / _ \  | '_ \   / _` |
 | |\  | | | | (__  |   <  \__ \ | (_) | | | | | | (_| |
 |_| \_| |_|  \___| |_|\_\ |___/  \___/  |_| |_|  \__,_|

*/

Compilation message (stderr)

building.cpp: In function 'void update(int, int, int, int, int)':
building.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
building.cpp: In function 'long long int f(int, int, int, int)':
building.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
building.cpp: At global scope:
building.cpp:85:7: 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