제출 #502309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502309		flappybird	Aliens (IOI16_aliens)	C++14	100 / 100	1216 ms	14000 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll N, M, K;
vector<pll> arr;
ll S[MAX];
ll E[MAX];
bool cmp(pll a, pll b) {
	if (a.first == b.first) return a.second > b.second;
	else return a.first < b.first;
}
void trans(vector<pll>& v) {
	sort(v.begin(), v.end(), cmp);
	v.erase(unique(v.begin(), v.end()), v.end());
	N = v.size();
	ll i;
	for (i = 0; i < N; i++) {
		if (arr.empty()) arr.push_back(v[i]);
		else if (arr.back().first == v[i].first) continue;
		else if (arr.back().second >= v[i].second) continue;
		else arr.push_back(v[i]);
	}
	N = arr.size();
	for (i = 0; i < N; i++) S[i] = arr[i].first, E[i] = arr[i].second;
}
struct Line {
	ll a, b, num;
	Line(ll a, ll b, ll num) :a(a), b(b), num(num) {}
	Line() {}
	ll get(ll x) { return a * x + b; }
};
ll dp[MAX];
ll path[MAX];
vector<Line> linev;
void add(Line l) {
	if (linev.size() < 2) {
		linev.push_back(l);
		return;
	}
	while (linev.size() >= 2) {
		Line p1, p2;
		p1 = linev.back();
		linev.pop_back();
		p2 = linev.back();
		if ((p1.b - p2.b) * (l.a - p2.a) >= (l.b - p2.b) * (p1.a - p2.a)) {
			linev.push_back(p1);
			break;
		}
	}
	linev.push_back(l);
}
ll mul(ll x, ll y) {
	if (log10(x) + log10(y) > 18) return 1000000000000000001;
	else return x * y;
}
pll get(ll x) {
	ll l, r;
	l = 0;
	r = linev.size();
	ll i;
	while (r - l > 5) {
		ll mid = (l + r) / 2;
		Line l1, l2;
		l1 = linev[mid];
		l2 = linev[mid + 1];
		if (-(l1.b - l2.b) >= mul(x, (l1.a - l2.a))) r = mid + 1;
		else l = mid - 1;
	}
	ll mn = linev[l].get(x);
	ll mv = linev[l].num;
	for (i = l; i < r; i++) if (mn > linev[i].get(x)) mn = linev[i].get(x), mv = linev[i].num;
	return { mn, mv };
}
ll sq(ll x) {
	return x * x;
}
ll cht(ll lambda) {
	linev.clear();
	dp[0] = 2 * sq(E[0] - S[0] + 1) + lambda;
	add(Line(-4 * S[0], 2 * (sq(S[0]) - 2 * S[0] + 1), 0));
	ll i;
	for (i = 0; i < N; i++) path[i] = -1;
	for (i = 1; i < N; i++) {
		pll res = get(E[i]);
		dp[i] = res.first;
		dp[i] += 4 * E[i];
		dp[i] += 2 * sq(E[i]);
		path[i] = res.second;
		if (dp[i] > 2 * sq(E[i] - S[i] + 1) + dp[i - 1] - 2 * sq(max(0LL, E[i - 1] - S[i] + 1))) dp[i] = 2 * sq(E[i] - S[i] + 1) + dp[i - 1] - 2 * sq(max(0LL, E[i - 1] - S[i] + 1)), path[i] = i;
		dp[i] += lambda;
		add(Line(-4 * S[i], dp[i - 1] + 2 * (sq(S[i]) - 2 * S[i] + 1) - 2 * sq(max(0LL, E[i - 1] - S[i] + 1)), i));
	}
	ll v = N - 1;
	ll cnt = 0;
	while (v >= 0) {
		cnt++;
		v = path[v] - 1;
	}
	return cnt;
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	N = n;
	M = m;
	K = k;
	vector<pll> all;
	ll i;
	for (i = 0; i < N; i++) all.push_back(pll(r[i], c[i]));
	for (i = 0; i < N; i++) if (all[i].first > all[i].second) swap(all[i].first, all[i].second);
	trans(all);
	K = min(K, N);
	ll low, high;
	low = -1, high = 10000000000000;
	while (high - low > 1) {
		ll mid = (low + high + 1) / 2;
		if (cht(mid) > K) low = mid;
		else high = mid;
	}
	cht(high);
	return (dp[N - 1] - K * high) / 2;
}

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