oj.uz

Submission #1050816

# Submission time Handle Problem Language Result Execution time Memory
1050816 2024-08-09T14:50:35 Z AlphaBruh Building Bridges (CEOI17_building) C++17
100 / 100
 94 ms 13404 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
#define SIZE 100005
#define inf 3000000000000000000
// basic
int n;
ll h[SIZE],w[SIZE],dp[SIZE],sw=0;
// cdq stuff
int qry[19][SIZE];
void srt(int l=1, int r=n, int id=0){
	if(l==r){
		qry[id][l]=l;
		return;
	}
	int md=(l+r)>>1;
	srt(l,md,id+1);
	srt(md+1,r,id+1);
	int lp=l,rp=md+1,cnt=l;
	int *bd = qry[id+1];
	while(lp<=md){
		while((rp<=r)&&(h[bd[rp]]<h[bd[lp]])){
			qry[id][cnt]=bd[rp];
			cnt++;
			rp++;
		}
		qry[id][cnt]=bd[lp];
		cnt++;
		lp++;
	}
	while(rp<=r){
		qry[id][cnt]=bd[rp];
		cnt++;
		rp++;
	}
}
ll X[SIZE],Y[SIZE];
int ed=0,stk[SIZE];
void clear(){ed=0;}
void pb(int id){
	ll dx1,dx2,dy1,dy2;
	while(ed>1){
		int cur=stk[ed];
		dx1=X[id]-X[cur];
		dy1=Y[id]-Y[cur];
		dx2=X[cur]-X[stk[ed-1]];
		dy2=Y[cur]-Y[stk[ed-1]];
		if(dy1*dx2<=dy2*dx1) ed--;
		else break;
	}
	stk[++ed]=id;
}
ll cal(int id, ll k){return Y[id]-(X[id]*k);}
queue<int> cdq(int l=1, int r=n, int id=0){
	if(l==r){
		X[l]=2*h[l];
		Y[l]=dp[l]+h[l]*h[l];
		queue<int>ret;
		ret.push(l);
		return ret;
	}
	int md=(l+r)>>1;
	queue<int>crv(cdq(l,md,id+1));
	queue<int>lft(crv);
	int cur=crv.front();
	crv.pop();
	for(int i=md+1;i<=r;i++){
		int nq = qry[id+1][i];
		while((!crv.empty()) && (cal(cur,h[nq]) >= cal(crv.front(),h[nq]))){
			cur=crv.front();
			crv.pop();
		}
		dp[nq] = min(dp[nq],cal(cur,h[nq])+h[nq]*h[nq]-w[nq]);
	}
	queue<int>rgt(cdq(md+1,r,id+1));
	clear();
	int L,R;
	while(lft.size()){
		L=lft.front();
		while(rgt.size()){
			R=rgt.front();
			if(X[R] < X[L]){
				pb(R);
				rgt.pop();
			}
			else break;
		}
		pb(L);
		lft.pop();
	}
	while(rgt.size()){
		pb(rgt.front());
		rgt.pop();
	}
	queue<int>ret;
	for(int i=1;i<=ed;i++) ret.push(stk[i]);
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++){
		cin>>w[i];
		sw+=w[i];
		dp[i]=inf;
	}
	if(n==1){
		printf("%lld\n",w[1]);
		return 0;
	}
	srt(1,n,0);
	dp[1]=-w[1];
	cdq(1,n,0);
	cout<<dp[n]+sw<<endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 13036 KB Output is correct
2 Correct 68 ms 12928 KB Output is correct
3 Correct 67 ms 12880 KB Output is correct
4 Correct 61 ms 12880 KB Output is correct
5 Correct 49 ms 13112 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 68 ms 13036 KB Output is correct
7 Correct 68 ms 12928 KB Output is correct
8 Correct 67 ms 12880 KB Output is correct
9 Correct 61 ms 12880 KB Output is correct
10 Correct 49 ms 13112 KB Output is correct
11 Correct 69 ms 13108 KB Output is correct
12 Correct 94 ms 12944 KB Output is correct
13 Correct 57 ms 12884 KB Output is correct
14 Correct 80 ms 13140 KB Output is correct
15 Correct 51 ms 13404 KB Output is correct
16 Correct 48 ms 13144 KB Output is correct
17 Correct 47 ms 12880 KB Output is correct
18 Correct 45 ms 12884 KB Output is correct