oj.uz

Submission #159259

# Submission time Handle Problem Language Result Execution time Memory
159259 2019-10-21T16:36:12 Z nvmdava Building Bridges (CEOI17_building) C++17
100 / 100
 81 ms 9848 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 100005
#define INF 0x3f3f3f3f3f3f3f3f
ll h[N], p[N];
ll dp[N];

struct Line{
	mutable ll x;
	ll y, d;
	bool operator<(const Line& rhs) const {
		return d < rhs.d;
	}
	bool operator<(const ll rhs) const {
		return x < rhs;
	}
	Line(ll _y, ll _d){
		y = _y;
		d = _d;
	}
};

struct LineContainer : multiset<Line, less<>> {
	ll query(ll x){
		auto it = lower_bound(x);
		return it -> y - it -> d * x;
	}
	bool fix(iterator l, iterator r){
		if(r == end()){
			l -> x = INF;
			return 0;
		}

		if(l -> d == r -> d)
			l -> x = (l -> y <= r -> y ? INF : -INF); 
		else
			l -> x = (r -> y - l -> y) / (r -> d - l -> d);
		return l -> x >= r -> x;
	}

	void update(ll y, ll d){
		auto it = insert(Line(y, d));
		auto l = it++;
		while(fix(l, it))
			it = erase(it);
		if(l == begin())
			return;
		it = l--;
		if(fix(l, it))
			fix(l, erase(it));

		while((it = l) != begin() && (--l) -> x >= it -> x)
			fix(l, erase(it));
	}
} ch;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin>>n;

	for(int i = 1; i <= n; i++)
		cin>>h[i];
	for(int i = 1; i <= n; i++){
		cin>>p[i];
		p[i] += p[i - 1];
	}

	ch.update(h[1] * h[1] - p[1], 2 * h[1]);

	for(int i = 2; i <= n; i++){
		dp[i] = p[i - 1] + h[i] * h[i] + ch.query(h[i]);
		ch.update(dp[i] + h[i] * h[i] - p[i], 2 * h[i]);
	}

	cout<<dp[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2780 KB Output is correct
2 Correct 57 ms 2808 KB Output is correct
3 Correct 58 ms 3788 KB Output is correct
4 Correct 53 ms 3596 KB Output is correct
5 Correct 48 ms 4828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 57 ms 2780 KB Output is correct
7 Correct 57 ms 2808 KB Output is correct
8 Correct 58 ms 3788 KB Output is correct
9 Correct 53 ms 3596 KB Output is correct
10 Correct 48 ms 4828 KB Output is correct
11 Correct 56 ms 3884 KB Output is correct
12 Correct 58 ms 3836 KB Output is correct
13 Correct 45 ms 3832 KB Output is correct
14 Correct 60 ms 4088 KB Output is correct
15 Correct 81 ms 9848 KB Output is correct
16 Correct 48 ms 4856 KB Output is correct
17 Correct 32 ms 3796 KB Output is correct
18 Correct 31 ms 3832 KB Output is correct