oj.uz

Submission #159248

# Submission time Handle Problem Language Result Execution time Memory
159248 2019-10-21T16:08:22 Z nvmdava Building Bridges (CEOI17_building) C++17
0 / 100
 58 ms 3832 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 : set<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)).ff;
		auto l = it++;
		while(fix(l, it))
			it = erase(it);
		if(l == begin())
			return;
		it = l--;
		if(fix(l, it))
			fix(l, it = 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(0 + 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
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 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3724 KB Output is correct
2 Incorrect 58 ms 3832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -