oj.uz

답안 #233855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233855 2020-05-22T02:44:45 Z kshitij_sodani Building Bridges (CEOI17_building) C++17
100 / 100
 337 ms 9172 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n;
vector<pair<llo,llo>> cht;
vector<pair<llo,llo>> cur;
vector<pair<llo,llo>> cht2;
vector<pair<llo,llo>> cht3;
llo bl=350;
llo inf=1e19;
llo val(pair<llo,llo> x,llo y){
	return x.a*y+x.b;
}
bool cmp(pair<llo,llo> x,pair<llo,llo> y){
	if(x.a<y.a){
		return 1;
	}
	else if(y.a<x.a){
		return 0;
	}
	return x.b>y.b;
}
void update(){
	if(cur.size()>bl){
		
		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		llo ind=0;
		llo ind2=0;
		while(ind<cur.size() and ind2<cht.size()){
			if(cur[ind].a>cht[ind2].a or  (cur[ind].a==cht[ind2].a and cur[ind].b>cht[ind2].b )){
				cht2.pb(cur[ind]);
				ind+=1;
			}
			else{
				cht2.pb({cht[ind2]});
				ind2+=1;
			}
		}
		while(ind<cur.size() ){
			cht2.pb(cur[ind]);
			ind+=1;
		}
		while(ind2<cht.size() ){
			cht2.pb(cht[ind2]);
			ind2+=1;
		}
		cht.clear();
		cur.clear();

		for(auto j:cht2){
			while(cht.size()>1){
				if(cht[cht.size()-1].a==j.a){
					cht.pop_back();
					continue;
				}
				
				if((cht[cht.size()-1].a-cht[cht.size()-2].a)*(cht[cht.size()-2].b-j.b)<=(-cht[cht.size()-2].a+j.a)*(cht[cht.size()-2].b-cht[cht.size()-1].b)){
					cht.pop_back();
				}	
				else{
					break;
				}
			}
			cht.pb(j);
		}
		cht2.clear();
		cht3.clear();
		cht3.pb({-inf,-inf});
		for(int j=1;j<cht.size();j++){
			cht3.pb({cht[j].b-cht[j-1].b,cht[j-1].a-cht[j].a});
			if(cht3.back().b<0){
				cht3.back().a=-cht3.back().a;
				cht3.back().b=-cht3.back().b;

			}
		}
	}
}
void insert(llo aa,llo bb){
	cur.pb({aa,bb});
	update();
}

llo bin(llo x){
	llo low=0;
	llo high=cht.size()-1;
	llo ans=inf;
	while(low<high-1){
		int mid=(low+high)/2;
		ans=min(ans,val(cht[mid],x));
		if(x*cht3[mid].b>=cht3[mid].a){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	for(llo i=low;i<high+1;i++){
		ans=min(ans,val(cht[i],x));
	}
	return ans;
}
llo query(llo x){
	llo mi=inf;
	for(auto j:cur){
		mi=min(mi,val(j,x));
	}
	mi=min(mi,bin(x));
	return mi;
}
llo aa[100001];
llo bb[100001];
llo dp[100001];
llo pre[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>aa[i];
	}
	for(llo i=0;i<n;i++){
		cin>>bb[i];
	}
	pre[0]=bb[0];
	for(llo i=1;i<n;i++){
		pre[i]=pre[i-1]+bb[i];
	}
	dp[0]=0;
	insert(-2*aa[0],dp[0]+aa[0]*aa[0]-pre[0]);
	for(llo i=1;i<n;i++){
		dp[i]=query(aa[i])+pre[i-1]+aa[i]*aa[i];
		insert(-2*aa[i],dp[i]+aa[i]*aa[i]-pre[i]);
		
	}
	cout<<dp[n-1]<<endl;





	return 0;
}

Compilation message

building.cpp:14:9: warning: overflow in implicit constant conversion [-Woverflow]
 llo inf=1e19;
         ^~~~
building.cpp: In function 'void update()':
building.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cur.size()>bl){
     ~~~~~~~~~~^~~
building.cpp:34:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() and ind2<cht.size()){
         ~~~^~~~~~~~~~~
building.cpp:34:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() and ind2<cht.size()){
                            ~~~~^~~~~~~~~~~
building.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<cur.size() ){
         ~~~^~~~~~~~~~~
building.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<cht.size() ){
         ~~~~^~~~~~~~~~~
building.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<cht.size();j++){
               ~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 4700 KB Output is correct
2 Correct 72 ms 4600 KB Output is correct
3 Correct 69 ms 4600 KB Output is correct
4 Correct 65 ms 4528 KB Output is correct
5 Correct 123 ms 5604 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 72 ms 4700 KB Output is correct
7 Correct 72 ms 4600 KB Output is correct
8 Correct 69 ms 4600 KB Output is correct
9 Correct 65 ms 4528 KB Output is correct
10 Correct 123 ms 5604 KB Output is correct
11 Correct 71 ms 4728 KB Output is correct
12 Correct 71 ms 4600 KB Output is correct
13 Correct 59 ms 4600 KB Output is correct
14 Correct 70 ms 4728 KB Output is correct
15 Correct 337 ms 9172 KB Output is correct
16 Correct 123 ms 5488 KB Output is correct
17 Correct 51 ms 4600 KB Output is correct
18 Correct 51 ms 4600 KB Output is correct