제출 #712280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712280		SanguineChameleon	Aliens (IOI16_aliens)	C++17	12 / 100	106 ms	4176 KiB

aliens

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

const int maxn = 1e5 + 20;
const long long inf = 1e18L + 20;
int lt[maxn];
int rt[maxn];
long long over[maxn];
long long dp[520][1020];

long long take_photos(int n, int m, int k, std::vector<int> rows, std::vector<int> cols) {
	vector<pair<int, int>> p, q;
	for (int i = 0; i < n; i++) {
		if (rows[i] > cols[i]) {
			swap(rows[i], cols[i]);
		}
		p.push_back({rows[i], cols[i]});
	}
	sort(p.begin(), p.end());
	for (auto x: p) {
		while (!q.empty() && (q.back().first == x.first || x.second <= q.back().second)) {
			q.pop_back();
		}
		q.push_back(x);
	}
	n = q.size();
	k = min(k, n);
	for (int i = 0; i < n; i++) {
		lt[i + 1] = q[i].first;
		rt[i + 1] = q[i].second;
	}
	over[0] = 0;
	for (int i = 1; i <= n - 1; i++) {
		int sz = max(rt[i] - lt[i + 1] + 1, 0);
		over[i] = 1LL * sz * sz;
	}
	dp[0][0] = 0;
	for (int i = 1; i <= k; i++) {
		dp[0][i] = inf;
	}
	for (int i = 1; i <= n; i++) {
		dp[i][0] = inf;
		for (int j = 1; j <= k; j++) {
			dp[i][j] = inf;
			for (int x = 0; x < i; x++) {
				if (dp[x][j - 1] == inf) {
					continue;
				}
				dp[i][j] = min(dp[i][j], dp[x][j - 1] + 1LL * (rt[i] - lt[x + 1] + 1) * (rt[i] - lt[x + 1] + 1) - over[x]);
			}
		}
	}
	long long res = inf;
	for (int i = 1; i <= k; i++) {
		res = min(res, dp[n][i]);
	}
	return res;
}

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