Submission #299040

#	Time	Username	Problem	Language	Result	Execution time	Memory
299040		SeDunion	Aliens (IOI16_aliens)	C++17	100 / 100	670 ms	12292 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 123;
const ll INF = 1e18;
const ll inf = 1e10;
const ld eps = 1e-12;

ll x[N], y[N];

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

struct line {
	ll k, b;
	int cnt;
	ll f (ll x) {
		return k * x + b;
	}
};

ld inter (line a, line b) {
	return ld(b.b - a.b) / ld(a.k - b.k);
}

struct cht {
	vector<line> v;
	void add (line a) {
		while (v.size() > 1 && inter (v.back(), v[v.size() - 2]) > inter (v[v.size() - 2], a)) {
			v.pop_back();
		}
		v.push_back (a);
	}
	pair<ll,int> get (ll x) {
		if (v.empty()) return {-INF, 0};
		int l = 0, r = int(v.size()) - 2;
		pair<ll,int> ans = {v.back().f(x), -v.back().cnt};
		while (l <= r) {
			int m = (l + r) >> 1;
			ans = max (ans, {v[m].f(x), -v[m].cnt});
			if (inter (v[m], v[m + 1]) < x) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		if (l < (int)v.size())
			ans = max (ans, {v[l].f(x), -v[l].cnt});
		if (r >= 0)
			ans = max (ans, {v[r].f(x), -v[r].cnt});
		return {ans.first, ans.second * -1};
	}
};

pair<ll,int> calc (int n, int m, int k, ll hph) {
	vector<ll> dp(n + 1, INF);
	vector<int> cnt(n + 1, -1);
	cht ok;
//	cout << hph << " hph\n";
	for (int i = 1 ; i <= n ; ++ i) {
		ok.add ({2 * x[i], -dp[i - 1] - sq(x[i]) + 2 * x[i] - 1 + sq(max(0ll,y[i-1]-x[i]+1)), cnt[i-1]});
		auto gt = ok.get (y[i]);
		dp[i] = sq(y[i]) + 2 * y[i] - gt.first + hph;
		cnt[i] = gt.second + 1;
	//	cout << gt.first << " " << gt.second << " " << dp[i] << " ";
		if (dp[i] > sq(y[i] - x[1] + 1) + hph) {
			dp[i] = sq(y[i] - x[1] + 1) + hph;
			cnt[i] = 1;
		}
	//	cout << dp[i] << " " << cnt[i] << "\n";
	}
	return {dp[n], cnt[n]};
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	vector<pair<int,int>> a(n);
	for (int i = 0 ; i < n ; ++ i) {
		if (r[i] > c[i]) swap (r[i], c[i]);
		a[i] = {r[i], c[i]};
	}
	sort (a.begin(), a.end());
	int n_ = 0;
	for (int i = 0, ymx = -1 ; i < n ; ++ i) {
		bool rm = false;
		if (i + 1 < n && a[i].first == a[i + 1].first) {
			rm = true;
		}
		if (a[i].second <= ymx) {
			rm = true;
		}
		if (!rm) {
			++n_;
			x[n_] = a[i].first;
			y[n_] = a[i].second;
		}
		if (i + 1 > n || a[i].first != a[i + 1].first)
			ymx = max (ymx, a[i].second);
	}
	n = n_;
	k = min (n, k);
	{
		ll l = 0, r = m*1ll*m;
		ll res = -1;
		while (l <= r) {
			ll hph = (l + r) / 2;
			auto now = calc (n, m, k, hph);
			if (now.second > k) {
				l = hph + 1;
			} else {
				res = hph;
				r = hph - 1;
			}
		}
		auto now = calc (n, m, k, res);
		//cout << now.first << " " << now.second << " " << l << "\n";
		return now.first - l * k;
	}
}

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