oj.uz

Submission #585513

# Submission time Handle Problem Language Result Execution time Memory
585513 2022-06-29T03:26:39 Z amunduzbaev Building Bridges (CEOI17_building) C++17
100 / 100
 83 ms 66416 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 1e5 + 5; 
const int M = 1e6 + 5;
const int inf = 1e9 + 7;

struct node{
	int m, b;
	double operator * (node x){
		return (b - x.b) * 1. / (x.m - m);
	}
	int get(int x){
		return m * x + b;
	}
};

struct LiChao{
	node tree[M << 2];
	LiChao(){
		for(int i=0;i<(M << 2);i++){
			tree[i] = {inf, inf * inf};
		}
	}
	
	void add(node v, int lx = 0, int rx = M, int x = 1){
		if(lx == rx){
			if(v.get(lx) > tree[x].get(lx)) tree[x] = v;
			return;
		}
		if(v.m == tree[x].m){
			tree[x].b = min(tree[x].b, v.b);
			return;
		}
		
		double is = tree[x] * v;
		int m = (lx + rx) >> 1;
		if(is < m + 1){
			if(tree[x].get(m + 1) > v.get(m + 1)) swap(tree[x], v);
			add(v, lx, m, x << 1);
		} else {
			if(tree[x].get(m) > v.get(m)) swap(tree[x], v);
			add(v, m + 1, rx, x << 1 | 1);
		}
	} 
	
	int get(int i, int lx = 0, int rx = M, int x = 1){
		if(lx == rx){
			return tree[x].get(i);
		}
		
		int m = (lx + rx) >> 1;
		if(i <= m) return min(get(i, lx, m, x << 1), tree[x].get(i));
		else return min(get(i, m + 1, rx, x << 1 | 1), tree[x].get(i));
	}
}tree;

int h[N], w[N], dp[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		w[i] += w[i-1];
	}
	
	tree.add({-2 * h[1], h[1] * h[1] - w[1]});
	for(int i=2;i<=n;i++){
		dp[i] = tree.get(h[i]) + h[i] * h[i] + w[i-1];
		tree.add({-2 * h[i], dp[i] + h[i] * h[i] - w[i]});
	}
	cout<<dp[n]<<"\n";
}

/*

6
3 8 7 1 6 6
0 -1 9 1 2 0

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62848 KB Output is correct
2 Correct 29 ms 62852 KB Output is correct
3 Correct 25 ms 62892 KB Output is correct
4 Correct 26 ms 62920 KB Output is correct
5 Correct 32 ms 62844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 65204 KB Output is correct
2 Correct 69 ms 65196 KB Output is correct
3 Correct 68 ms 65208 KB Output is correct
4 Correct 63 ms 65172 KB Output is correct
5 Correct 57 ms 65164 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62848 KB Output is correct
2 Correct 29 ms 62852 KB Output is correct
3 Correct 25 ms 62892 KB Output is correct
4 Correct 26 ms 62920 KB Output is correct
5 Correct 32 ms 62844 KB Output is correct
6 Correct 78 ms 65204 KB Output is correct
7 Correct 69 ms 65196 KB Output is correct
8 Correct 68 ms 65208 KB Output is correct
9 Correct 63 ms 65172 KB Output is correct
10 Correct 57 ms 65164 KB Output is correct
11 Correct 81 ms 66384 KB Output is correct
12 Correct 83 ms 66400 KB Output is correct
13 Correct 67 ms 66284 KB Output is correct
14 Correct 74 ms 66416 KB Output is correct
15 Correct 61 ms 66056 KB Output is correct
16 Correct 57 ms 66108 KB Output is correct
17 Correct 51 ms 66396 KB Output is correct
18 Correct 45 ms 66236 KB Output is correct