Submission #306847

#	Time	Username	Problem	Language	Result	Execution time	Memory
306847		miss_robot	Building Bridges (CEOI17_building)	C++14	100 / 100	160 ms	10616 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 1e9;

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

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

int qry(int x, set<segment> &s){
	auto it = --s.upper_bound({x, 0, 0, 0, 0});
	return it->m * x + it->a;
}

void upd(int m, int a, set<segment> &s){
	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 = s.end();
	else{
		st--;
		while(isect(m, a, st->m, st->a) < st->r){
			double tmp = isect(m, a, st->m, st->a);
			if(tmp < st->l) st = --s.erase(st);
			else st->r = floor(tmp);
		}
	}
	auto en = s.upper_bound({0, 0, m, 0, 1});
	while(en != s.end() && isect(m, a, en->m, en->a) > en->l){
		double tmp = isect(m, a, en->m, en->a);
		if(tmp > en->r) en = s.erase(en);
		else en->l = ceil(tmp);
	}
	if(st == s.end() || en == s.end() || st->r+1 < en->l)
		s.insert({(st==s.end()?-INF:st->r+1), (en==s.end()?INF:en->l-1), m, a, 0});
}

signed main(){
	int n;
	cin >> n;
	vector<int> h(n), w(n);
	for(int &x : h) cin >> x;
	for(int &x : w) cin >> x;
	w[0] = 0;
	for(int i = 1; i < n-1; i++) w[i] += w[i-1];
	set<segment> s;
	upd(-2*h[0], h[0]*h[0], s);
	for(int i = 1; i < n-1; i++)
		upd(-2*h[i], h[i]*h[i]-w[i]+qry(h[i], s)+h[i]*h[i]+w[i-1], s);
	cout << qry(h[n-1], s)+h[n-1]*h[n-1]+w[n-2] << "\n";
}

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