oj.uz

Submission #948214

# Submission time Handle Problem Language Result Execution time Memory
948214 2024-03-17T23:00:28 Z amirhoseinfar1385 Building Bridges (CEOI17_building) C++17
100 / 100
 2985 ms 8180 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(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];
	//cout<<"add: "<<f.x<<" "<<f.y<<endl;
	lich.add(f);
}

void upd(long long i){
	dp[i]=+ps[i-1]+h[i]*h[i]+lich.pors(h[i]);
	//cout<<"upd: "<<dp[i]<<endl;
}

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 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 3 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 85 ms 7516 KB Output is correct
2 Correct 78 ms 7980 KB Output is correct
3 Correct 84 ms 7724 KB Output is correct
4 Correct 150 ms 7512 KB Output is correct
5 Correct 29 ms 7424 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 3 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 85 ms 7516 KB Output is correct
7 Correct 78 ms 7980 KB Output is correct
8 Correct 84 ms 7724 KB Output is correct
9 Correct 150 ms 7512 KB Output is correct
10 Correct 29 ms 7424 KB Output is correct
11 Correct 120 ms 7772 KB Output is correct
12 Correct 72 ms 7708 KB Output is correct
13 Correct 2985 ms 8180 KB Output is correct
14 Correct 72 ms 7772 KB Output is correct
15 Correct 31 ms 7512 KB Output is correct
16 Correct 27 ms 7516 KB Output is correct
17 Correct 20 ms 7772 KB Output is correct
18 Correct 2383 ms 7776 KB Output is correct