Submission #48079

#	Time	Username	Problem	Language	Result	Execution time	Memory
48079		jun6873	Aliens (IOI16_aliens)	C++11	4 / 100	5 ms	1356 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);
	ret *= 2;
	if (x>=0) ret += m[x];
	return ret;
}
int f(lint k) {
	fill(m, m+maxn, -inf);
	for (int i=0, j=-1; i<a.size(); i++) {
		while (j+1<i and cost(j, i) < cost(j+1, i)) j++;
		m[i] = cost(j, i) + k;
		p[i] = j;
	}
	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 = -1;
	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(l);
	return (m[a.size()-1] - l * k) / 2;
}

Compilation message (stderr)

aliens.cpp: In function 'int f(lint)':
aliens.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0, j=-1; i<a.size(); i++) {
                      ~^~~~~~~~~

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