oj.uz

Submission #948218

# Submission time Handle Problem Language Result Execution time Memory
948218 2024-03-17T23:02:58 Z amirhoseinfar1385 Building Bridges (CEOI17_building) C++17
100 / 100
 44 ms 6916 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 ;
		}
		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=-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 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6488 KB Output is correct
2 Correct 37 ms 6492 KB Output is correct
3 Correct 41 ms 6916 KB Output is correct
4 Correct 36 ms 6488 KB Output is correct
5 Correct 27 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 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 37 ms 6488 KB Output is correct
7 Correct 37 ms 6492 KB Output is correct
8 Correct 41 ms 6916 KB Output is correct
9 Correct 36 ms 6488 KB Output is correct
10 Correct 27 ms 6492 KB Output is correct
11 Correct 38 ms 6492 KB Output is correct
12 Correct 44 ms 6492 KB Output is correct
13 Correct 30 ms 6492 KB Output is correct
14 Correct 38 ms 6488 KB Output is correct
15 Correct 27 ms 6540 KB Output is correct
16 Correct 26 ms 6492 KB Output is correct
17 Correct 19 ms 6540 KB Output is correct
18 Correct 19 ms 6492 KB Output is correct