제출 #250350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250350		oolimry	Building Bridges (CEOI17_building)	C++14	100 / 100	238 ms	127992 KiB

building

#include <bits/stdc++.h>
#define m first
#define c second;
using namespace std;
typedef pair<long long,long long> line;

const long long inf = 102345678901234567;

long long get(line L, int x){ return L.m * x + L.c; }

long long H[100005];
int C[100005];

struct lichao{
	int s, e, m;
	lichao *l, *r;
	line val = line(0,inf);
	
	lichao(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s == e-1) return;
		l = new lichao(s, m);
		r = new lichao(m, e);
	}
	
	void insert(line L){
		if(get(L, m) < get(val, m)) swap(L, val); ///make val the dominant one
		
		if(s == e-1) return;
		
		if(get(L, s) < get(val, s)) l->insert(L); ///L has some chance in l
		else r->insert(L); ///L has some chance in r
	}
	
	long long query(int x){
		if(s == e-1) return get(val, x);
		else if(x >= m) return min(get(val,x), r->query(x));
		else return min(get(val,x), l->query(x));
	}
	
} *root;

signed main(){
	ios_base::sync_with_stdio(false);
	
	long long ans = 0;
	
	int n; cin >> n;
	for(int i = 0;i < n;i++) cin >> H[i];
	for(int i = 0;i < n;i++){
		cin >> C[i];
		ans += C[i];
		C[i] *= -1;
	}
	
	root = new lichao(0, 1000001);
	
	long long dp = C[0];
	root->insert(line(-2*H[0], dp + H[0]*H[0]));
	
	for(int i = 1;i < n;i++){
		dp = root->query(H[i]);
		dp += H[i]*H[i] + C[i];
		
		root->insert(line(-2*H[i], dp + H[i]*H[i]));
		
	}
	cout << dp + ans << "\n";
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40