Submission #766154

#	Time	Username	Problem	Language	Result	Execution time	Memory
766154		SanguineChameleon	Aliens (IOI16_aliens)	C++17	41 / 100	2065 ms	3172 KiB

aliens

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

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

void calc(long long cost) {
	dp[0] = make_pair(0, 0);
	for (int i = 1; i <= N; i++) {
		dp[i] = make_pair(inf, -1);
		for (int j = 1; j <= i; j++) {
			dp[i] = min(dp[i], make_pair(dp[j - 1].first + 1LL * (R[i] - L[j]) * (R[i] - L[j]) - over[j] + cost, dp[j - 1].second + 1));
		}
	}
}

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++) {
		if (R[i - 1] > L[i]) {
			over[i] = 1LL * (R[i - 1] - L[i]) * (R[i - 1] - L[i]);
		}
	}
	K = min(K, N);
	long long lt = 0;
	long long rt = max_cost;
	long long res = inf;
	while (lt <= rt) {
		long long mt = (lt + rt) / 2;
		calc(mt);
		if (dp[N].second <= K) {
			res = dp[N].first - mt * K;
			rt = mt - 1; 
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

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