Submission #672371

#	Time	Username	Problem	Language	Result	Execution time	Memory
672371		Eae02	Aliens (IOI16_aliens)	C++17	60 / 100	2082 ms	360644 KiB

aliens

#include "aliens.h"

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

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && 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(ll k, ll m) {
		auto z = insert({k, m, 0}), 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));
	}
	ll query(ll x) { assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};


ll 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";
	//}
	
	constexpr ll inf = LLONG_MAX;
	
	auto square = [&] (ll x) { return x * x; };
	
	vector<vector<ll>> dp(st.size() + 1, vector<ll>(K + 1));
	dp[st.size()][0] = 0;
	for (ll i = (ll)st.size() - 1; i >= 0; i--)
		dp[i][0] = inf;
	for (ll remk = 1; remk <= K; remk++) {
		dp[st.size()][remk] = 0;
		LineContainer lc;
		auto addToLC = [&] (ll ie) {
			if (ie == 0) return;
			if (dp[ie][remk - 1] == inf) return;
			ll ex = st[ie-1].second + 1;
			ll bx = st[ie].first;
			ll k = -2 * ex;
			ll m =
				dp[ie][remk - 1]
				+ square(ex)
				- square(max(ex - bx, 0LL));
			lc.add(-k, -m);
		};
		for (ll i = (ll)st.size() - 1; i >= 0; i--) {
			ll ans = dp[st.size()][remk - 1] + square(st.back().second - st[i].first + 1);
			/*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())
				ans = min(ans, -lc.query(st[i].first) + square(st[i].first));
			dp[i][remk] = ans;
			addToLC(i);
		}
	}
	
	return dp[0][K];
}

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