oj.uz

Submission #250350

# Submission time Handle Problem Language Result Execution time Memory
250350 2020-07-17T13:31:52 Z oolimry Building Bridges (CEOI17_building) C++14
100 / 100
 238 ms 127992 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, *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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 125560 KB Output is correct
2 Correct 111 ms 125560 KB Output is correct
3 Correct 104 ms 125564 KB Output is correct
4 Correct 103 ms 125560 KB Output is correct
5 Correct 110 ms 125568 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 126744 KB Output is correct
2 Correct 166 ms 126712 KB Output is correct
3 Correct 163 ms 126712 KB Output is correct
4 Correct 156 ms 126840 KB Output is correct
5 Correct 163 ms 126712 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 125560 KB Output is correct
2 Correct 111 ms 125560 KB Output is correct
3 Correct 104 ms 125564 KB Output is correct
4 Correct 103 ms 125560 KB Output is correct
5 Correct 110 ms 125568 KB Output is correct
6 Correct 163 ms 126744 KB Output is correct
7 Correct 166 ms 126712 KB Output is correct
8 Correct 163 ms 126712 KB Output is correct
9 Correct 156 ms 126840 KB Output is correct
10 Correct 163 ms 126712 KB Output is correct
11 Correct 238 ms 127992 KB Output is correct
12 Correct 207 ms 127820 KB Output is correct
13 Correct 156 ms 127956 KB Output is correct
14 Correct 216 ms 127992 KB Output is correct
15 Correct 167 ms 127608 KB Output is correct
16 Correct 159 ms 127736 KB Output is correct
17 Correct 226 ms 127864 KB Output is correct
18 Correct 150 ms 127992 KB Output is correct