Submission #47998

#	Time	Username	Problem	Language	Result	Execution time	Memory
47998		jun6873	Aliens (IOI16_aliens)	C++11	0 / 100	6 ms	1416 KiB

aliens

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

using lint = long long;
using pint = pair<int, int>;
#define x first
#define y second

const int maxn = 100004;
const lint inf = (lint)4.29e12;
vector<pint> ra, a;
lint m[maxn];
int p[maxn];

lint sq(int x) { return x*(lint)x; }
lint cost(int x, int y) {
	lint ret = sq(a[y].y - a[x+1].x + 1);
	if (x>=0 and a[x].y >= a[x+1].x) ret -= sq(a[x].y - a[x+1].x + 1);
	return ret;
}
void fill_dp(int s, int e, int l, int r, lint x) {
	if (s>e) return;

	int k = (s+e)/2;
	for (int i=l; i<k and i<r; i++) {
		lint now = cost(i, k) + x;
		if (i>=0) now += m[i];
		if (m[k] < now) m[k] = now, p[k] = i;
	}
	fill_dp(s, k-1, l, p[k], x);
	fill_dp(k+1, e, p[k], r, x);
}
int f(lint k) {
	fill(m, m+maxn, -inf);
	fill_dp(0, a.size()-1, -1, a.size()-1, k);
	int ret = 0;
	for (int i=a.size()-1; ~i; i=p[i]) ret++;
	return ret;
}

lint take_photos(int n, int M, int k, vector<int> R, vector<int> c) {
	for (int i=0; i<n; i++) ra.emplace_back(min(R[i], c[i]), max(R[i], c[i]));

	sort(ra.begin(), ra.end(), [](pint a, pint b) { return a.x < b.x or (a.x == b.x and a.y > b.y); });

	int mx = 0;
	for (pint& i : ra) {
		if (i.y <= mx) continue;
		mx = i.y;
		a.push_back(i);
	}

	lint l = 0, r = inf;
	while (l+1<r) {
		lint m = (l+r) / 2;
		if (f(m) >= k) r = m;
		else l = m;
	}

	k = f(r);
    return m[a.size()-1] - r * 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