Submission #672377

#	Time	Username	Problem	Language	Result	Execution time	Memory
672377		Eae02	Aliens (IOI16_aliens)	C++17	25 / 100	98 ms	1108 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>
using namespace std;
using ll = __int128_t;
using ld = long double;
#define all(x) begin(x),end(x)

struct Line {
	mutable ld k, m, p;
	ll howManyPhotos;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ld x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	const ld inf = INFINITY;
	ld div(ld a, ld b) { // floored division
		return a / b;
	}
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ld k, ld m, ll howManyPhotos) {
		auto z = insert({k, m, 0.0, howManyPhotos}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
	}
	pair<ld, ll> query(ld x) { assert(!empty());
		auto l = *lower_bound(x);
		return make_pair(l.k * x + l.m, l.howManyPhotos);
	}
};

long long take_photos(int n, int m, int K, vector<int> r, vector<int> c) {
	vector<pair<ll, ll>> intvs;
	for (int i = 0; i < n; i++) {
		intvs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
	}
	sort(all(intvs));
	
	vector<pair<ll, ll>> st;
	for (auto [l, r] : intvs) {
		if (st.empty() || -r > st.back().second)
			st.emplace_back(l, -r);
	}
	
	//for (auto [l, r] : st) {
	//	cerr << "intv " << l << " " << r << "\n";
	//}
	
	auto square = [&] (ll x) { return x * x; };
	
	auto alienTrick = [&] (ld cost) -> pair<ld, ll> { // (ans, howManyPhotos)
		vector<pair<ld, ll>> dp(st.size() + 1);
		dp[st.size()] = {0.0,0};
		LineContainer lc;
		auto addToLC = [&] (ll ie) {
			if (ie == 0) return;
			ll ex = st[ie-1].second + 1;
			ll bx = st[ie].first;
			ld k = -2 * ex;
			ld m =
				dp[ie].first
				+ square(ex)
				- square(max(ex - bx, (ll)0LL));
			lc.add(-k, -m, dp[ie].second);
		};
		for (ll i = (ll)st.size() - 1; i >= 0; i--) {
			pair<ld, ll> ans = {
				dp[st.size()].first + square(st.back().second - st[i].first + 1) + cost,
				1LL
			};
			/*for (ll ie = i + 1; ie < (ll)st.size(); ie++) {
				ll ex = st[ie-1].second + 1;
				ll bx = st[ie].first;
				ans = min(ans,
					dp[ie][remk - 1]
					+ square(ex)
					- 2 * ex * st[i].first
					+ square(st[i].first)
					- square(max(ex - bx, 0LL))
				);
			}*/
			if (!lc.empty()) {
				auto lcq = lc.query(st[i].first);
				ans = min(ans, make_pair(-lcq.first + square(st[i].first) + cost, lcq.second + 1));
			}
			dp[i] = ans;
			addToLC(i);
		}
		return dp[0];
	};
	
	ld lo = 0;
	ld hi = 1E9;
	for (ll it = 0; it < 100; it++) {
		ld mid = (lo + hi) / 2.0;
		auto [ans, howManyPhotos] = alienTrick(mid);
		if (howManyPhotos > K)
			lo = mid;
		else
			hi = mid;
	}
	auto [ans, howManyPhotos] = alienTrick(lo);
	return (long long)round(ans - lo * K);
}

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