Submission #30841

#	Time	Username	Problem	Language	Result	Execution time	Memory
30841		khsoo01	Aliens (IOI16_aliens)	C++11	100 / 100	249 ms	11384 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, inf = 1e12;

ll n, m, k;
pll dt[N];

vector<pll> raw, a;

struct hull {
	deque<pair<pll, ll> > v;
	void clear () {v.clear();}
	bool well (pll &A, pll &B, pll &C) {
		return (B.Y - A.Y) * (A.X - C.X) < (C.Y - A.Y) * (A.X - B.X);
	}
	ll val (pll &T, ll P) {return T.X*P+T.Y;}
	void upd (pair<pll, ll> A) {
		for(ll i=v.size();i-->1;) {
			if(well(v[i-1].X, v[i].X, A.X)) break;
			else v.pop_back();
		}
		v.push_back(A);
	}
	pll get (ll P) {
		while(v.size() > 1) {
			if(val(v[0].X, P) <= val(v[1].X, P)) break;
			else v.pop_front();
		}
		return pll(val(v[0].X, P), v[0].Y+1);
	}
} h;

ll sq (ll X) {return X*X;}

pll solve (ll L) {
	h.clear();
	h.upd({pll(-2*(a[0].X-1), sq(a[0].X-1) + L), 0});
	for(ll i=0;i<n;i++) {
		auto T = h.get(a[i].Y);
		dt[i] = {T.X + sq(a[i].Y), T.Y};
		if(i+1 == n) continue;
		h.upd({{-2*(a[i+1].X-1), sq(a[i+1].X-1) - sq(max(0ll, a[i].Y-a[i+1].X+1)) + dt[i].X + L}, T.Y});
	}
	return dt[n-1];
}

ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) {
	m = _m; k = _k;
	for(ll i=0;i<_n;i++) {
		if(r[i] < c[i]) raw.push_back(pll(r[i], c[i]));
		else raw.push_back(pll(c[i], r[i]));
	}
	sort(raw.begin(), raw.end());
	for(auto &T : raw) {
		if(a.empty() || a.back().Y < T.Y) a.push_back(T);
	}
	n = a.size();
	ll S = 0, E = inf;
	while(S<E) {
		ll M = (S+E)/2;
		solve(M).Y <= k ? E = M : S = M+1;
	}
	return solve(S).X - k * S;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40