Submission #766091

#	Time	Username	Problem	Language	Result	Execution time	Memory
766091		SanguineChameleon	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	212 KiB

aliens

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

const int maxN = 5e2 + 20;
const long long inf = 1e18L + 20;
pair<int, int> ranges[maxN];
int L[maxN];
int R[maxN];
long long over[maxN];
long long dp[maxN][maxN];
int N, K;

long long take_photos(int _N, int M, int _K, vector<int> row, vector<int> col) {
	N = _N;
	K = _K;
	for (int i = 1; i <= N; i++) {
		if (row[i - 1] <= col[i - 1]) {
			ranges[i].first = row[i - 1];
			ranges[i].second = -col[i - 1];
		}
		else {
			ranges[i].first = col[i - 1];
			ranges[i].second = -row[i - 1];
		}
	}
	sort(ranges + 1, ranges + N + 1);
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		if (cnt == 0 || (L[cnt] != ranges[i].first && -ranges[i].second > R[cnt])) {
			cnt++;
			L[cnt] = ranges[i].first - 1;
			R[cnt] = -ranges[i].second;
		}
	}
	N = cnt;
	for (int i = 2; i <= N; i++) {
		assert(L[i - 1] < L[i] && R[i - 1] < R[i]);
		if (R[i - 1] >= L[i]) {
			//assert(false);
			over[i] = 1LL * (R[i - 1] - L[i] + 1) * (R[i - 1] - L[i] + 1);
		}
	}
	K = min(K, N);
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= K; j++) {
			dp[i][j] = inf;
		}
	}
	dp[0][0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			for (int x = 1; x <= i; x++) {
				dp[i][j] = min(dp[i][j], dp[x - 1][j - 1] + 1LL * (R[i] - L[x]) * (R[i] - L[x]) - over[x]);
			}
		}
	}
	return dp[N][K];
}

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