Submission #464590

#	Time	Username	Problem	Language	Result	Execution time	Memory
464590		pikel_rik	Aliens (IOI16_aliens)	C++17	12 / 100	8 ms	296 KiB

aliens

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

long long take_photos(int n, int m, int k, vector<int> r, vector<int> l) {
	for (int i = 0; i < n; i++) {
		if (r[i] < l[i]) {
			swap(r[i], l[i]);
		}
	}

	vector<int> ind(n);
	iota(ind.begin(), ind.end(), 0);
	sort(ind.begin(), ind.end(), [&](int i, int j) {
		return l[i] < l[j] || (l[i] == l[j] && r[i] > r[j]);
	});

	int mx = INT_MIN;
	ind.erase(remove_if(ind.begin(), ind.end(), [&](int i) {
		if (r[i] <= mx) {
			return true;
		} else {
			mx = r[i];
			return false;
		}
	}), ind.end());

	int sz = (int) ind.size();
	sort(ind.begin(), ind.end(), [&](int i, int j) {
		return r[i] < r[j];
	});

	k = min(k, sz);

	vector<pair<long long, long long>> lines;

	auto add_line = [&](long long m, long long c) -> void {
		while (lines.size() > 1) {
			auto [m1, c1] = lines[(int) lines.size() - 1];
			auto [m2, c2] = lines[(int) lines.size() - 2];
			//(c - c2) / (m2 - m) >= (c1 - c2) / (m2 - m1)
			if ((c - c2) * (m2 - m1) >= (c1 - c2) * (m2 - m)) {
				lines.pop_back();
			} else {
				break;
			}
		}
		lines.emplace_back(m, c);
	};

	auto query = [&](long long x) -> long long {
		int lo = 0, hi = (int) lines.size() - 1;
		while (lo < hi) {
			int mid = lo + (hi - lo) / 2;
			auto [m1, c1] = lines[mid];
			auto [m2, c2] = lines[mid + 1];
			//x <= (c1 - c2) / (m2 - m1)
			if (x * (m2 - m1) <= c1 - c2) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
		return lines[lo].first * x + lines[lo].second;
	};

	{
		vector<int> new_r(sz), new_l(sz);
		for (int i = 0; i < sz; i++) {
			new_r[i] = r[ind[i]];
			new_l[i] = l[ind[i]];
		}

		r.swap(new_r);
		l.swap(new_l);
	}

	vector<long long> dp(sz);
	long long ans = LLONG_MAX;

	for (int j = 1; j <= k; j++) {
		lines.clear();
		add_line(2 * r[sz - j], (long long)-r[sz - j] * r[sz - j] - (j == 1 ? 0 : dp[sz - j + 1]));
		for (int i = sz - j; i >= 0; i--) {
			long long old_dp = dp[i];
			dp[i] = (long long)(l[i] - 1) * (l[i] - 1) - query(l[i] - 1);
			if (j != 1 && i > 0) {
				add_line(2 * r[i - 1], (long long)-r[i - 1] * r[i - 1] - old_dp);
			}
		}
		ans = min(ans, dp[0]);
	}
	return ans;
}

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