Submission #1046820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046820		Gromp15	Aliens (IOI16_aliens)	C++17	12 / 100	81 ms	2392 KiB

aliens

#include "aliens.h"
#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; }

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];
		}
	}
	swap(a, b);
	n = sz(a);
	vector<vector<ll>> dp(n+1, vector<ll>(k+1, 1e18));
	dp[0][0] = 0;
	auto sq = [&](int x) { return (ll)x * x; };
	for (int i = 1; i <= n; i++) for (int t = 1; t <= k; t++) {
		int mnx = 1e9, mxy = -1;
		for (int j = i-1; j >= 0; j--) {
			// use [j, i-1]
			ckmin(mnx, a[j][0]), ckmax(mxy, a[j][1]);
			ckmin(dp[i][t], dp[j][t-1] + sq(mxy - mnx + 1));
		}
	}
	return *min_element(all(dp[n]));
}

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