Submission #672368

#	Time	Username	Problem	Language	Result	Execution time	Memory
672368		Eae02	Aliens (IOI16_aliens)	C++17	12 / 100	133 ms	2288 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 = 1E10;
	
	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;
		for (ll i = (ll)st.size() - 1; i >= 0; i--) {
			ll ans = dp[i + 1][remk - 1] + square(st[i].second - st[i].first + 1);
			for (ll ie = i + 1; ie < (ll)st.size(); ie++) {
				ll ex = st[ie].second;
				ll bx = ie+1 == (ll)st.size() ? (ll)1E10 : st[ie+1].first;
				ans = min(ans,
					dp[ie + 1][remk - 1] + square(ex - st[i].first + 1) - square(max(ex - bx + 1, 0LL))
				);
			}
			dp[i][remk] = ans;
		}
	}
	return dp[0][K];
}

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