Submission #89361

#	Time	Username	Problem	Language	Result	Execution time	Memory
89361		nicksona	Building Bridges (CEOI17_building)	C++14	100 / 100	57 ms	11604 KiB

building

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
struct Str {
	int k;
	int b;
};
Str T[8000001];
double Cross (int k1,int b1,int k2,int b2){
	if (k1==k2) return 1000000000;
	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;
	//cout<<K<<endl;
	if (r<l){
		return ;
	}
	
	if(T[p].b==0&&T[p].k==0){
		T[p].k=k;
		T[p].b=b;		
		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(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);	
		}
	}
}

int 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;
	}
	//cout<<T[p].k<<" "<<T[p].b<<endl;
	if (r==l){
		return x*T[p].k+T[p].b;
	}
	if (r<=l){
		return 1000000000000000000;
	}
	
	if (x>mid){
		return min(x*T[p].k+T[p].b,f(p+p+1,mid+1,r,x));
	}
	else{
		return min((x*T[p].k+T[p].b),f(p+p,l,mid,x));	
	}
}
int n;
int h[1000001],w[1000001];
int dp[1000001];
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];	
	int N=1000000;	
	update (1,1,N,k,b);
		
	for (int i=2;i<=n;i++){
		int 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;
}
/*
2
0 1000000
-20 20
  _   _   _          _
 | \ | | (_)        | |
 |  \| |  _    ___  | | __  ___    ___    _ __     __ _
 | . ` | | |  / __| | |/ / / __|  / _ \  | '_ \   / _` |
 | |\  | | | | (__  |   <  \__ \ | (_) | | | | | | (_| |
 |_| \_| |_|  \___| |_|\_\ |___/  \___/  |_| |_|  \__,_|

*/

Compilation message (stderr)

building.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
building.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
building.cpp: In function 'long long int f(long long int, long long int, long long int, long long int)':
building.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
building.cpp: At global scope:
building.cpp:88:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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