oj.uz

답안 #992716

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
992716 2024-06-05T05:35:17 Z PoPularPlusPlus Building Bridges (CEOI17_building) C++17
0 / 100
 44 ms 69468 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vf first
#define vs second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

struct Line {
	ll m = 0 , c = 1e18;
};

ll value(Line a , int x){
	return a.m * x + a.c;
}

struct Lichao {
	vector<Line> v;
	int siz;
	
	void init(int n){
		siz = 1;
		while(siz < n){
			siz *= 2;
		}
		
		v.resize(siz * 2);
	}
	
	void set(Line l, int x , int lx , int rx){
		if(rx - lx == 0){
			if(value(l,lx) < value(v[x],lx)){
				v[x] = l;
			}
			return;
		}
		int m = (lx + rx)/2;
		
		if(v[x].m < l.m)swap(v[x],l);
		
		
		if(value(l,m) < value(v[x] , m)){
			swap(l,v[x]);
			set(l , 2 * x , lx , m);
		}
		else {
			set(l , 2 * x + 1 , m + 1 ,rx);
		}
	}
	
	ll query(int x_val , int x , int lx, int rx){
		ll ans = value(v[x],x_val);
		if(rx == lx)return ans;
		int mid = (lx + rx)/2;
		if(x_val <= mid){
			ans = min(ans , query(x_val , 2 *x, lx,mid));
		}
		else ans = min(ans , query(x_val, 2 * x + 1 , mid + 1 ,rx));
		return ans;
	}
};

void solve(){
	int n;
	cin >> n;
	ll h[n];
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}
	ll w[n];
	for(int i = 0; i < n; i++){
		cin >> w[i];
	}
	
	ll dp[n];
	
	Lichao li;
	li.init(2000005);
	
	dp[0] = -w[0];
	li.set({-2*h[0] , h[0]*h[0] - w[0]},0,0,li.siz-1);
	
	ll ans = 0;
	for(int i = 0; i < n; i++){
		ans += w[i];
	}
	
	for(int i = 1; i < n; i++){
		dp[i] = li.query(h[i],0,0,li.siz-1) + h[i] * h[i] - w[i];
		
		li.set({-2*h[i] , h[i]*h[i] +dp[i]},0,0,li.siz-1);
	}
	
	cout << dp[n-1] + ans << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;
	//cin >> t;
	//	while(t--)
	solve();
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 65884 KB Output is correct
2 Incorrect 9 ms 65916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 68444 KB Output is correct
2 Correct 44 ms 69468 KB Output is correct
3 Correct 40 ms 69456 KB Output is correct
4 Correct 37 ms 69200 KB Output is correct
5 Incorrect 32 ms 69212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 65884 KB Output is correct
2 Incorrect 9 ms 65916 KB Output isn't correct
3 Halted 0 ms 0 KB -