Submission #63367

#	Time	Username	Problem	Language	Result	Execution time	Memory
63367		fallingstar	Aliens (IOI16_aliens)	C++14	4 / 100	5 ms	768 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>

#define long long long

using namespace std;

const int N = 1e5 + 2;
const long INF = 1e18;

struct TPoint { long x, y; };

inline long sqr(long x) { return x * x; }

int n, m, k;
TPoint a[N];

void Reduce()
{
	for (int i = 1; i <= n; ++i)
		if (a[i].x > a[i].y) swap(a[i].x, a[i].y);
	sort(a + 1, a + 1 + n, [](TPoint p, TPoint q) { return p.x < q.x || (p.x == q.x && p.y > q.y); });
	int new_n = 1;
	for (int i = 2; i <= n; ++i)
		if (a[i].y > a[new_n].y) a[++new_n] = a[i];
	n = new_n;
	for (int i = 1; i <= n; ++i) ++a[i].y;				// we add every column by 1
}

inline long Cost(int i, int j)
{
	int pre_h = max(0LL, a[i - 1].y - a[i].x);
	int cur_h = a[j].y - a[i].x;
	return sqr(cur_h) - sqr(pre_h);
}

long f[2][N];

bool Minimize(long &a, long b) { if (a <= b) return false; a = b; return true; }

void DP(int cur, int pre, int sL, int sR, int qL, int qR)
{
	int mid = (sL + sR) / 2;

	int opt = mid; 
	f[cur][mid] = f[pre][mid - 1] + Cost(mid, mid);

	for (int j = qL; j < mid; ++j)
		if (Minimize(f[cur][mid], f[pre][j - 1] + Cost(j, mid))) opt = j;

	if (sL < mid) DP(cur, pre, sL, mid - 1, qL, opt);
	if (mid < sR) DP(cur, pre, mid + 1, sR, opt, qR);
}

struct THull
{
	struct TLine {
		long a, b;
		long Eval(long x) { return a * x + b; }
	};
	double Intersect(TLine p, TLine q) { return (double) (q.b - p.b) / (p.a - q.a); }
	int n = 0, lim = 1;
	TLine st[N];
	void AddLine(TLine p)
	{
		while (n >= 2 && n >= lim && Intersect(st[n - 1], p) <= Intersect(st[n], p)) --n;
		st[++n] = p;
	}
	long Query(long x)
	{
		while (lim < n && x >= Intersect(st[lim], st[lim + 1])) ++lim;
		return st[lim].Eval(x);
	}
	void Clear() { n = 0, lim = 1; }
} hull;

long Solve()
{
	Reduce();
	// for (int i = 1; i <= n; ++i) cerr << Cost(i, i) << ' ';
	// cerr << '\n';

	int cur = 1, pre = 0;
	fill(f[cur] + 1, f[cur] + 1 + n, INF);
	for (int i = 1; i <= k; ++i)
	{
		swap(cur, pre);
		hull.Clear();
		for (int i = 1; i <= n; ++i)
		{
			hull.AddLine({-a[i].x * 2, sqr(a[i].x) - sqr(max(0LL, a[i - 1].y - a[i].x)) + f[pre][i - 1]});
			f[cur][i] = hull.Query(a[i].y) + sqr(a[i].y);
		}
	}
	return f[cur][n];
}

long take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c) {
	n = _n, m = _m, k = _k;
	for (int i = 0; i < _n; ++i) a[i + 1] = {_r[i], _c[i]};				// we add column by 1
    return Solve();
}

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