oj.uz

Submission #349211

# Submission time Handle Problem Language Result Execution time Memory
349211 2021-01-17T05:32:25 Z Bill_00 Building Bridges (CEOI17_building) C++14
100 / 100
 123 ms 69612 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define N 1000001
using namespace std;
struct line{
	ll k,b;
	ll operator*(ll x){
		return k*x+b;
	}
};
ll n,h[N],w[N],dp[N];
line lines[20*N+4],nw;
void build(line nw,ll id,ll l,ll r){
	lines[id]=nw;
	if(r-l==1){
		return;
	}
	ll m=(l+r)>>1;
	build(nw,id*2,l,m);
	build(nw,id*2+1,m,r);
}
ll search(ll x,ll id,ll l,ll r){
	ll m=(l+r)>>1;
	if(r-l==1){
		return lines[id]*x;
	}
	if(x<m){
		return min(search(x,id*2,l,m),lines[id]*x);
	}
	else return min(search(x,id*2+1,m,r),lines[id]*x);
}
void ins(line nw,ll id,ll l,ll r){
	ll m=(l+r)>>1;
	bool lef=((nw*l)<(lines[id]*l));
	bool mid=((nw*m)<(lines[id]*m));
	if(mid) swap(lines[id],nw);
	if(r-l==1) return;
	if(lef!=mid){
		ins(nw,id*2,l,m);
	}
	else ins(nw,id*2+1,m,r);
}
ll lol;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> h[i];
	}
	for(int i=1;i<=n;i++){
		cin >> w[i];
		lol+=w[i];
	}
	dp[1]=-w[1];
	nw={h[1],dp[1]+h[1]*h[1]};
	build(nw,1,-2*N,1);
	for(int i=2;i<n;i++){
		ll k=search(-2*h[i],1,-2*N,1);
		dp[i]=h[i]*h[i]+k-w[i];
		nw={h[i],dp[i]+h[i]*h[i]};
		ins(nw,1,-2*N,1);
	}
	ll k=search(-2*h[n],1,-2*N,1);
	dp[n]=h[n]*h[n]+k-w[n];
	cout << dp[n]+lol;


}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66028 KB Output is correct
2 Correct 48 ms 66028 KB Output is correct
3 Correct 48 ms 66028 KB Output is correct
4 Correct 56 ms 66028 KB Output is correct
5 Correct 49 ms 66028 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 69356 KB Output is correct
2 Correct 98 ms 69356 KB Output is correct
3 Correct 99 ms 69504 KB Output is correct
4 Correct 93 ms 69356 KB Output is correct
5 Correct 93 ms 69356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 66028 KB Output is correct
2 Correct 48 ms 66028 KB Output is correct
3 Correct 48 ms 66028 KB Output is correct
4 Correct 56 ms 66028 KB Output is correct
5 Correct 49 ms 66028 KB Output is correct
6 Correct 108 ms 69356 KB Output is correct
7 Correct 98 ms 69356 KB Output is correct
8 Correct 99 ms 69504 KB Output is correct
9 Correct 93 ms 69356 KB Output is correct
10 Correct 93 ms 69356 KB Output is correct
11 Correct 122 ms 69604 KB Output is correct
12 Correct 123 ms 69356 KB Output is correct
13 Correct 104 ms 69484 KB Output is correct
14 Correct 119 ms 69612 KB Output is correct
15 Correct 90 ms 69228 KB Output is correct
16 Correct 94 ms 69356 KB Output is correct
17 Correct 93 ms 69496 KB Output is correct
18 Correct 92 ms 69484 KB Output is correct