oj.uz

Submission #250349

# Submission time Handle Problem Language Result Execution time Memory
250349 2020-07-17T13:29:51 Z oolimry Building Bridges (CEOI17_building) C++14
30 / 100
 160 ms 127864 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);
	
	int 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 108 ms 125560 KB Output is correct
2 Correct 105 ms 125560 KB Output is correct
3 Correct 104 ms 125560 KB Output is correct
4 Correct 102 ms 125560 KB Output is correct
5 Correct 104 ms 125688 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 126812 KB Output is correct
2 Correct 160 ms 127864 KB Output is correct
3 Correct 155 ms 127736 KB Output is correct
4 Correct 153 ms 127736 KB Output is correct
5 Incorrect 156 ms 127736 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 125560 KB Output is correct
2 Correct 105 ms 125560 KB Output is correct
3 Correct 104 ms 125560 KB Output is correct
4 Correct 102 ms 125560 KB Output is correct
5 Correct 104 ms 125688 KB Output is correct
6 Correct 157 ms 126812 KB Output is correct
7 Correct 160 ms 127864 KB Output is correct
8 Correct 155 ms 127736 KB Output is correct
9 Correct 153 ms 127736 KB Output is correct
10 Incorrect 156 ms 127736 KB Output isn't correct