제출 #159259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159259		nvmdava	Building Bridges (CEOI17_building)	C++17	100 / 100	81 ms	9848 KiB

building

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40