oj.uz

Submission #89360

# Submission time Handle Problem Language Result Execution time Memory
89360 2018-12-12T09:04:32 Z nicksona Building Bridges (CEOI17_building) C++14
30 / 100
 59 ms 7388 KB 
#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 10000000;
	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((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);	
		}
	}
}

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[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];	
	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;
}
/*
6
3 8 7 1 6 7
0 -1 9 1 0 0
  _   _   _          _
 | \ | | (_)        | |
 |  \| |  _    ___  | | __  ___    ___    _ __     __ _
 | . ` | | |  / __| | |/ / / __|  / _ \  | '_ \   / _` |
 | |\  | | | | (__  |   <  \__ \ | (_) | | | | | | (_| |
 |_| \_| |_|  \___| |_|\_\ |___/  \___/  |_| |_|  \__,_|

*/

Compilation message

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:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
building.cpp: At global scope:
building.cpp:87:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3232 KB Output is correct
2 Correct 57 ms 4244 KB Output is correct
3 Correct 59 ms 5340 KB Output is correct
4 Correct 57 ms 6160 KB Output is correct
5 Incorrect 31 ms 7388 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 57 ms 3232 KB Output is correct
7 Correct 57 ms 4244 KB Output is correct
8 Correct 59 ms 5340 KB Output is correct
9 Correct 57 ms 6160 KB Output is correct
10 Incorrect 31 ms 7388 KB Output isn't correct