Submission #1046861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046861		Gromp15	Aliens (IOI16_aliens)	C++17	100 / 100	100 ms	8872 KiB

aliens

#include "aliens.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ll long long
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
const ll INF = 1e18;
const int nax = 1e5 + 5;
ar<ll, 4> d[nax]; 

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	vector<ar<int, 2>> a(n);
	for (int i = 0; i < n; i++) {
		a[i] = {r[i], c[i]};
		if (r[i] > c[i]) swap(a[i][0], a[i][1]);
	}
	sort(all(a));
	int mx = -1;
	vector<ar<int, 2>> b;
	for (int i = 0; i < n; i++) {
		int r = i;
		while (r+1 < n && a[r+1][0] == a[r][0]) r++;
		if (a[r][1] > mx) {
			b.push_back({a[r][0], a[r][1]});
			mx = a[r][1];
		}
		i = r;
	}
	swap(a, b);
	n = sz(a);
	ll L = 0, R = 1e12, ans = -1;
	while (L <= R) {
		ll mid = (L+R)/2;
		vector<ar<ll, 3>> dp(n+1, {INF, INF, -INF});
		dp[0] = {0, 0, 0};
		auto sq = [&](int x) { return (ll)x * x; };
		auto f = [&](int j) {
			return dp[j][0] + sq(a[j][0]) - 2 * a[j][0] - (j ? sq(max(0, a[j-1][1] - a[j][0] + 1)) : 0);
		};
		int dl = -1, dr = 0;
		d[++dl] = {-2 * a[0][0], f(0), 0, 0};
		auto query = [&](int p, int pos) {
			return d[p][0] * pos + d[p][1];
		};
		auto inter = [&](const ar<ll, 4>& x1, const ar<ll, 4>& x2) {
			return (double)(x2[1] - x1[1]) / (x1[0] - x2[0]);
		};
		for (int i = 1; i <= n; i++) {
			ll C = sq(a[i-1][1]) + 2 * a[i-1][1] + 1 + mid;
			int cur = a[i-1][1];
			while (dl+1 <= dr && query(dl+1, cur) < query(dl, cur)) dl++;
			dp[i][0] = query(dl, cur) + C;
			for (int j = dl; j <= dr; j++) {
				if (query(j, cur) == query(dl, cur)) {
					ckmin(dp[i][1], d[j][2] + 1);
					ckmin(dp[i][2], d[j][3] + 1);
				}
				else break;
			}
			if (i < n) {
				ar<ll, 4> nw{-2 * a[i][0], f(i), dp[i][1], dp[i][2]};
				while (dr-dl >= 1 && inter(d[dr-1], nw) <= inter(d[dr-1], d[dr])) dr--;
				d[++dr] = nw;
			}
		}
		if (dp[n][1] <= k) {
			int u = min(k, int(dp[n][2]));
			ans = dp[n][0] - u * mid;
			R = mid-1;
		}
		else L = mid+1;
	}
	return ans;
}

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