oj.uz

Submission #948216

# Submission time Handle Problem Language Result Execution time Memory
948216 2024-03-17T23:01:53 Z amirhoseinfar1385 Building Bridges (CEOI17_building) C++17
100 / 100
 41 ms 6716 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=-2e6,long long r=2e6){
		if(l==r){
			return ;
		}
		if(seg[i].f==fakefunc){
			seg[i].f=f;
			return ;
		}
		if(l==r-1){
			return ;
		}
		long long m=(l+r)/2;
		if(seg[i].f.get(l)>f.get(l)){
			swap(seg[i].f,f);
		}
		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=-2e6,long long r=2e6){
		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 2 ms 6492 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 41 ms 6544 KB Output is correct
2 Correct 35 ms 6492 KB Output is correct
3 Correct 35 ms 6492 KB Output is correct
4 Correct 32 ms 6492 KB Output is correct
5 Correct 25 ms 6488 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 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 41 ms 6544 KB Output is correct
7 Correct 35 ms 6492 KB Output is correct
8 Correct 35 ms 6492 KB Output is correct
9 Correct 32 ms 6492 KB Output is correct
10 Correct 25 ms 6488 KB Output is correct
11 Correct 36 ms 6492 KB Output is correct
12 Correct 37 ms 6488 KB Output is correct
13 Correct 29 ms 6544 KB Output is correct
14 Correct 37 ms 6488 KB Output is correct
15 Correct 26 ms 6716 KB Output is correct
16 Correct 26 ms 6492 KB Output is correct
17 Correct 20 ms 6492 KB Output is correct
18 Correct 21 ms 6644 KB Output is correct