oj.uz

Submission #540176

# Submission time Handle Problem Language Result Execution time Memory
540176 2022-03-19T14:03:04 Z xuliu Building Bridges (CEOI17_building) C++17
100 / 100
 111 ms 28620 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const ll inf = 1e18 + 4;

struct Line {
	ll a, b; // ax + b
	Line() { a = 0; b = inf; }
	Line(ll _a, ll _b) { a = _a; b = _b; }
	ll operator()(ll x) { return a*x + b; }
};

const int N = 1e9 + 4;
int chg(int x) { return x-N; }
int chgg(int x) { return x+N; }

struct node {
	ll l, r;
	Line line;
	node *left = NULL, *right = NULL;
	node(int lb, int rb) {
		l = lb; r = rb;
	}
	void extend() {
		if(!left && l != r) {
			ll m = (l+r)/2;
			left = new node(l, m);
			right = new node(m+1, r);
		}
	}
	void add(Line seg) {
		debug cerr<<"adding seg.a = "<<seg.a<<", seg.b = "<<seg.b<<"\n";
		if(l == r) {
			if(seg(chg(l)) < line(chg(l))) line = seg;
			return;
		}
		extend();
		ll m = (l+r)/2;
		if(line.a < seg.a) swap(line, seg);
		if(line(chg(m)) > seg(chg(m))) {
			swap(line, seg);
			left->add(seg);
		}
		else right->add(seg);
	}
	ll get(ll x) {
		if(l == r) return line(chg(x));
		extend();
		int m = (l+r)/2;
		if(x <= m) return min(line(chg(x)), left->get(x));
		else return min(line(chg(x)), right->get(x));
	}
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	node root(0, 2*N+4);
	vector<ll> h(n), w(n);
	ll W = 0;
	for(int i=0; i<n; i++) cin>>h[i];
	for(int i=0; i<n; i++) { cin>>w[i]; W += w[i]; }
	vector<ll> dp(n, inf);
	dp[0] = -w[0];
	root.add(Line(-2LL*h[0], dp[0]+h[0]*h[0]));
	for(int i=1; i<n; i++) {
		dp[i] = h[i]*h[i] - w[i];
		dp[i] += root.get(chgg(h[i]));
		root.add(Line(-2LL*h[i], dp[i]+h[i]*h[i]));
	}
	cout<<dp[n-1]+W;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5208 KB Output is correct
2 Correct 62 ms 4968 KB Output is correct
3 Correct 62 ms 4932 KB Output is correct
4 Correct 51 ms 4044 KB Output is correct
5 Correct 64 ms 25176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 60 ms 5208 KB Output is correct
7 Correct 62 ms 4968 KB Output is correct
8 Correct 62 ms 4932 KB Output is correct
9 Correct 51 ms 4044 KB Output is correct
10 Correct 64 ms 25176 KB Output is correct
11 Correct 110 ms 17000 KB Output is correct
12 Correct 111 ms 16732 KB Output is correct
13 Correct 65 ms 12620 KB Output is correct
14 Correct 102 ms 16728 KB Output is correct
15 Correct 63 ms 28620 KB Output is correct
16 Correct 68 ms 25164 KB Output is correct
17 Correct 37 ms 3820 KB Output is correct
18 Correct 35 ms 3948 KB Output is correct