oj.uz

답안 #250633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250633 2020-07-18T14:44:42 Z oolimry Building Bridges (CEOI17_building) C++14
0 / 100
 147 ms 131076 KB 
#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 = nullptr, *r = nullptr;
	line val = line(0,inf);
	
	lichao(int S, int E){
		s = S, e = E, m = (s+e)/2;
	}
	
	void create(){
		l = new lichao(s, m);
		r = new lichao(m+1, e);
	}
	
	void insert(line L){
		if(get(L, m+1) < get(val, m+1)) swap(L, val); ///make val the dominant one
		
		if(s == e-1) return;
		
		if(l == nullptr) create();
		
		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(l == nullptr) create();
			
			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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 111 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 147 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 111 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -