Submission #766172

#	Time	Username	Problem	Language	Result	Execution time	Memory
766172		SanguineChameleon	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	428 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;

struct line {
	long long a, b, cnt;

	line(): a(0), b(0), cnt(0) {};

	line(long long _a, long long _b, int _cnt): a(_a), b(_b), cnt(_cnt) {};

	long long eval(int x) {
		return a * x + b;
	}
};

struct CHT {
	vector<line> Q;

	void add(line L) {
		Q.push_back(L);
	}

	line get(int x) {
		line best = Q[0];
		for (int i = 1; i < (int)Q.size(); i++) {
			if (Q[i].eval(x) < best.eval(x)) {
				best = Q[i];
			}
		}
		return best;
	}
};

void calc(long long cost) {
	CHT C;
	dp[0] = make_pair(0, 0);
	C.add(line(-2 * L[1], 1LL * L[1] * L[1] - over[1], 0));
	for (int i = 1; i <= N; i++) {
		auto best = C.get(R[i]);
		dp[i].first = best.eval(R[i]) + 1LL * R[i] * R[i];
		dp[i].second = best.cnt + 1;
		C.add(line(-2 * L[i + 1], dp[i].first + 1LL * L[i + 1] * L[i + 1] - over[i + 1] + cost, dp[i].second));
	}
}

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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40