oj.uz

Submission #939315

# Submission time Handle Problem Language Result Execution time Memory
939315 2024-03-06T09:04:07 Z iskhakkutbilim Building Bridges (CEOI17_building) C++17
100 / 100
 106 ms 52808 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int inf = 1e9;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
struct Line{
	int k, b;
	int operator * (int x){
		return k * x + b;
	}
	int operator ^ (Line x){
		return ceil((b - x.b) / (x.k - k));
	};
};

struct LiChao{
	Line tree[N * 30];
	int last, L[N * 30], R[N * 30];
	LiChao(){
		last = 0;
		for(int i=0;i<(N*30);i++) tree[i] = {inf, inf * inf};
	}
	
	void add(Line v, int lx = 0, int rx = mod, int x = 0){
		if(lx == rx){
			if(tree[x] * lx > v * lx) swap(tree[x], v);
			return;
		}
		if(v.k == tree[x].k){
			tree[x].b = min(tree[x].b, v.b);
			return;
		}
		
		int m = (lx + rx) >> 1;
		int ix = tree[x] ^ v;
		if(ix <= m){
			if(tree[x] * (m + 1) > v * (m + 1)) swap(tree[x], v);
			add(v, lx, m, (L[x] ? L[x] : L[x] = ++last));
		} else {
			if(tree[x] * m > v * m) swap(tree[x], v);
			add(v, m + 1, rx, (R[x] ? R[x] : R[x] = ++last));
		}
	}
	
	int get(int i, int lx = 0, int rx = mod, int x = 0){
		if(lx == rx) return tree[x] * i;
		int m = (lx + rx) >> 1;
		if(i <= m && L[x]) return min(tree[x] * i, get(i, lx, m, L[x]));
		if(m < i && R[x]) return min(tree[x] * i, get(i, m + 1, rx, R[x]));
		return tree[x] * i;
	}
}tree;
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
signed main(){
	int n; cin >> n;
	vector<int> h(n+1);
	for(int i = 1;i <= n; i++) cin >> h[i];
	vector<int> w(n+1, 0);
	for(int i = 1;i <= n; i++){
		cin >> w[i];
		w[i]+= w[i-1];
	}
	
	vector<int> dp(n+1);
	dp[1] = 0;
	tree.add({-2 * h[1], dp[1] - w[1] + h[1] * h[1]});
	for(int i = 2;i <= n; i++){
			
		// kx + b
		/*
		
			new_dp[i] = (h[i] - h[j])^2 + dp[j]
			(h[i] - h[j]) * (h[i] - h[j]) = kx
			h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j]
			dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
		
		*/
		/*
		for(int j = 1; j < i; j++){
			//dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
		}
		*/
		int mn = tree.get(h[i]);
		
		dp[i] = mn + h[i]*h[i] + w[i-1];
		tree.add({-2 * h[i], dp[i] - w[i] + h[i] * h[i]});
	}
	cout << dp[n];
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47708 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 8 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 51276 KB Output is correct
2 Correct 92 ms 51320 KB Output is correct
3 Correct 102 ms 51284 KB Output is correct
4 Correct 80 ms 51024 KB Output is correct
5 Correct 71 ms 52308 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47708 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 8 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 94 ms 51276 KB Output is correct
7 Correct 92 ms 51320 KB Output is correct
8 Correct 102 ms 51284 KB Output is correct
9 Correct 80 ms 51024 KB Output is correct
10 Correct 71 ms 52308 KB Output is correct
11 Correct 99 ms 52680 KB Output is correct
12 Correct 106 ms 52428 KB Output is correct
13 Correct 84 ms 51252 KB Output is correct
14 Correct 100 ms 52672 KB Output is correct
15 Correct 68 ms 52808 KB Output is correct
16 Correct 72 ms 52304 KB Output is correct
17 Correct 49 ms 51024 KB Output is correct
18 Correct 47 ms 51024 KB Output is correct