Submission #1260413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260413		kunzaZa183	Aliens (IOI16_aliens)	C++20	0 / 100	2092 ms	328 KiB

aliens

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

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	vector<pair<int, int>> all;
	for (int i = 0; i < n; i++)
		all.emplace_back(minmax(r[i], c[i]));
	sort(all.begin(), all.end(), [&](pair<int, int> a, pair<int, int> b) {
		if (a.first != b.first)
			return a.first < b.first;
		return a.second > b.second;
		});

	vector<pair<int, int>> segs;
	for (auto [l, r] : all)
		if (segs.empty()) {
			segs.emplace_back(l, r);
		}
		else {
			auto [l2, r2] = segs.back();
			if (r2 < r) {
				segs.emplace_back(l, r);
			}
		}

	auto sq = [&](ll x) { return x * x; };

	ll binl = 0, binr = m * m;
	n = segs.size();

	while (binl < binr) {
		ll mid = (binl + binr) / 2;

		vector<ll> dp(n + 1), ct(n + 1, INT_MAX);
		ct[0] = 0;

		deque<array<ll, 3>> lin;
		lin.push_back({ -2 * (segs[0].first),
									 dp[0] + sq(segs[0].first) - 2 * (segs[0].first),
									 0ll }); // slope, offset, in

		auto qry = [&](array<ll, 3> all, ll x) { return all[0] * x + all[1]; };

		for (int i = 1; i <= n; i++) {

			while (lin.size() > 1) {
				ll a = qry(lin[0], segs[i - 1].second),
					b = qry(lin[1], segs[i - 1].second);
				if (a > b) {
					lin.pop_front();
				}
				else if (a == b) {
					if (ct[lin[0][2]] >= ct[lin[1][2]])
						lin.pop_front();
					else break;
				}
				else {
					break;
				}
			}

			auto [m, b, in] = lin.front();

			dp[i] = segs[i - 1].second * m + b + sq(segs[i - 1].second) +
				2 * segs[i - 1].second + 1 + mid;
			ct[i] = ct[in] + 1;

			if (i < n)
				lin.push_back(
					{ -2 * segs[i].first, dp[i] - 2 * segs[i].first + sq(segs[i].first), i });
		}

		if (ct[n] > k) {
			binl = mid + 1;
		}
		else {
			binr = mid;
		}
	}

	vector<ll> dp(n + 1), ct(n + 1, INT_MAX);
	ct[0] = 0;

	deque<array<ll, 3>> lin;
	lin.push_back({ -2 * (segs[0].first),
								 dp[0] + sq(segs[0].first) - 2 * (segs[0].first),
								 0ll }); // slope, offset, in

	auto qry = [&](array<ll, 3> all, ll x) { return all[0] * x + all[1]; };

	for (int i = 1; i <= n; i++) {

		while (lin.size() > 1) {
			ll a = qry(lin[0], segs[i - 1].second),
				b = qry(lin[1], segs[i - 1].second);
			if (a > b) {
				lin.pop_front();
			}
			else if (a == b) {
				if (ct[lin[0][2]] >= ct[lin[1][2]])
					lin.pop_front();
			}
			else {
				break;
			}
		}

		auto [m, b, in] = lin.front();

		dp[i] = segs[i - 1].second * m + b + sq(segs[i - 1].second) +
			2 * segs[i - 1].second + 1 + binl;
		ct[i] = ct[in] + 1;

		if (i < n)
			lin.push_back(
				{ -2 * segs[i].first, dp[i] - 2 * segs[i].first + sq(segs[i].first) + sq(max(0, segs[i - 1].second - segs[i].first + 1)), i });
	}

	return dp.back() - k * binl;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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