oj.uz

Submission #250635

# Submission time Handle Problem Language Result Execution time Memory
250635 2020-07-18T14:45:44 Z oolimry Building Bridges (CEOI17_building) C++14
100 / 100
 101 ms 27384 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) 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) 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3644 KB Output is correct
2 Correct 58 ms 3536 KB Output is correct
3 Correct 56 ms 3764 KB Output is correct
4 Correct 50 ms 2808 KB Output is correct
5 Correct 64 ms 19576 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 56 ms 3644 KB Output is correct
7 Correct 58 ms 3536 KB Output is correct
8 Correct 56 ms 3764 KB Output is correct
9 Correct 50 ms 2808 KB Output is correct
10 Correct 64 ms 19576 KB Output is correct
11 Correct 101 ms 14584 KB Output is correct
12 Correct 97 ms 14272 KB Output is correct
13 Correct 52 ms 3068 KB Output is correct
14 Correct 91 ms 14456 KB Output is correct
15 Correct 66 ms 27384 KB Output is correct
16 Correct 67 ms 19580 KB Output is correct
17 Correct 39 ms 2560 KB Output is correct
18 Correct 40 ms 2560 KB Output is correct