Submission #305137

#	Time	Username	Problem	Language	Result	Execution time	Memory
305137		miss_robot	Building Bridges (CEOI17_building)	C++14	100 / 100	83 ms	11384 KiB

building

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

const int N = 1e5, INF = 1e12;
int n;
int dp[N], p[N], h[N];

struct segment{
	mutable int l, r;
	int m, a, mode;
	bool operator<(const segment &o) const{
		if(mode || o.mode) return m > o.m;
		return l < o.l;
	}
}; set<segment> s;

int qry(int x){
	segment t = *--s.upper_bound({x, 0, 0, 0, 0});
	return x*t.m + t.a;
}

double isect(int m1, int m2, int a1, int a2){
	return (double)(a1-a2)/(double)(m2-m1);
}

void upd(int m, int a){
	auto st = s.lower_bound({0, 0, m, 0, 1});
	if(st != s.end() && st->m == m){
		if(st->a < a) return;
		st = s.erase(st);
	}
	if(st != s.begin()){
		st--;
		while(isect(m, st->m, a, st->a) < st->r){
			double x = isect(m, st->m, a, st->a);
			if(x <= st->l) st = --s.erase(st);
			else st->r = floor(x);
		}
	}
	else st = s.end();
	auto en = s.upper_bound({0, 0, m, 0, 1});
	while(en != s.end() && isect(m, en->m, a, en->a) > en->l){
		double x = isect(m, en->m, a, en->a);
		if(x >= en->r) en = s.erase(en);
		else en->l = ceil(x);
	}
	if(st == s.end() || en == s.end() || en->l-st->r > 1)
		s.insert({st == s.end()? -INF:st->r+1, en == s.end()? INF:en->l-1, m, a, 0});
}

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

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40