Submission #766202

#	Time	Username	Problem	Language	Result	Execution time	Memory
766202		SanguineChameleon	Aliens (IOI16_aliens)	C++17	100 / 100	157 ms	12716 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;
	}
};

long long floor_div(long long a, long long b) {
	return a / b;
}

long long inter(line L1, line L2) {
	return floor_div(L2.b - L1.b, L1.a - L2.a);
}

struct CHT {
	vector<line> Q;
	int pt = 0;

	void add(line L) {
		while ((int)Q.size() >= 2 && inter(Q.end()[-2], Q.back()) >= inter(Q.back(), L)) {
			Q.pop_back();
		}
		Q.push_back(L);
	}

	line get(int x) {
		pt = min(pt, (int)Q.size() - 1);
		while (pt + 1 < (int)Q.size() && Q[pt].eval(x) > Q[pt + 1].eval(x)) {
			pt++;
		}
		return Q[pt];
	}
};

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] + cost, 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;
		if (i == N) {
			break;
		}
		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: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40