oj.uz

Submission #948220

# Submission time Handle Problem Language Result Execution time Memory
948220 2024-03-17T23:03:38 Z amirhoseinfar1385 Building Bridges (CEOI17_building) C++17
100 / 100
 46 ms 6800 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long inf=1e17;
struct func{
	long long x,y;
	func(){
		x=inf;
		y=0;
	}
	long long get(long long w){
		return x+w*y;
	}
	bool operator ==(func f){
		return (f.x==x&&f.y==y);
	}
}fakefunc;

struct lichao{
	struct node{
		long long l,r;
		node(){
			l=r=-1;
		}
		func f;
	};
	node seg[maxn];
	int te=1;
	int gor(int i){
		if(seg[i].r==-1){
			seg[i].r=te;
			te++;
		}
		return seg[i].r;
	}
	int gol(int i){
		if(seg[i].l==-1){
			seg[i].l=te;
			te++;
		}
		return seg[i].l;
	}
	void add(func f,long long i=0,long long l=0,long long r=1e6){
		if(l==r){
			return ;
		}
		if(seg[i].f==fakefunc){
			seg[i].f=f;
			return ;
		}
		long long m=(l+r)/2;
		if(seg[i].f.get(l)>f.get(l)){
			swap(seg[i].f,f);
		}
		if(l==r-1){
			return ;
		}
		if(seg[i].f.get(m)<=f.get(m)){
			add(f,gor(i),m,r);
		}else{
			swap(seg[i].f,f);
			add(f,gol(i),l,m);
		}
	}
	long long pors(long long w,long long i=0,long long l=0,long long r=1e6){
		if(l==r){
			return 0;
		}
		long long ret=seg[i].f.get(w);
		long long m=(l+r)>>1;
		if(w>=m&&seg[i].r!=-1){
			ret=min(ret,pors(w,seg[i].r,m,r));
		}
		if(w<m&&seg[i].l!=-1){
			ret=min(ret,pors(w,seg[i].l,l,m));
		}
		return ret;
	}
}lich;
long long dp[maxn],n,w[maxn],h[maxn],ps[maxn];


void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>h[i];
	}
	for(long long i=1;i<=n;i++){
		cin>>w[i];
	}
	for(long long i=1;i<=n;i++){
		ps[i]=ps[i-1]+w[i];
	}
}

void add(long long i){
	func f;
	f.x=dp[i]-ps[i]+h[i]*h[i];
	f.y=-2*h[i];
	lich.add(f);
}

void upd(long long i){
	dp[i]=+ps[i-1]+h[i]*h[i]+lich.pors(h[i]);
}

void solve(){
	dp[1]=0;
	add(1);
	for(long long i=2;i<=n;i++){
		upd(i);
		add(i);
	}
}

void khor(){
	cout<<dp[n]<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6540 KB Output is correct
2 Correct 36 ms 6492 KB Output is correct
3 Correct 46 ms 6492 KB Output is correct
4 Correct 35 ms 6492 KB Output is correct
5 Correct 25 ms 6492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 36 ms 6540 KB Output is correct
7 Correct 36 ms 6492 KB Output is correct
8 Correct 46 ms 6492 KB Output is correct
9 Correct 35 ms 6492 KB Output is correct
10 Correct 25 ms 6492 KB Output is correct
11 Correct 38 ms 6492 KB Output is correct
12 Correct 43 ms 6540 KB Output is correct
13 Correct 30 ms 6488 KB Output is correct
14 Correct 36 ms 6488 KB Output is correct
15 Correct 25 ms 6492 KB Output is correct
16 Correct 26 ms 6492 KB Output is correct
17 Correct 19 ms 6536 KB Output is correct
18 Correct 19 ms 6800 KB Output is correct