Submission #341381

#	Time	Username	Problem	Language	Result	Execution time	Memory
341381		peijar	Aliens (IOI16_aliens)	C++17	60 / 100	2079 ms	7012 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
const ll INF = 1e12;
using ld = long double;

struct StaticCHT
{
	vector<ll> a, b;
	int hd, tl;
	StaticCHT(int n) : a(n), b(n) {hd = tl = 0;}

	// decreasing slopes
	void add(ll a0, ll b0)
	{
		while (tl - hd >= 2)
		{
			ll a1 = a[tl-1], b1 = b[tl-1];
			ll a2 = a[tl-2], b2 = b[tl-2];
			if (ld(b0-b2) * (a1 - a0) < ld(b0-b1) * (a2-a0)) break;
			tl--;
		}
		a[tl] = a0, b[tl] = b0;
		tl++;
	}
	// increasing x0
	ll query(ll x0)
	{
		while (tl - hd >= 2)
		{
			if (x0 * a[hd] + b[hd] < x0 * a[hd+1] + b[hd+1]) break;
			hd++;
		}
		assert(hd < SZ(a));
		return x0 * a[hd] + b[hd];
	}
};


ll sq(ll x) {return x * x;}

ll take_photos(int nbInteret, int dim, int nbPhotos, vector<int> vy, vector<int> vx) 
{
	vector<pair<int, int>> points(nbInteret);
	for (int i(0); i < nbInteret; ++i)
		points[i] = make_pair(min(vx[i], vy[i]), max(vx[i], vy[i]));
	sort(points.begin(), points.end(),
			[](pair<int, int> a, pair<int, int> b)
			{
			if (a.first == b.first)
			return a.second > b.second;
			return a.first < b.first;
			});
	vector<pair<int, int>> cur;
	for (auto p : points)
		if (cur.empty() or p.second > cur.back().second)
			cur.push_back(p);
	points = move(cur);
	nbInteret = SZ(points);
	vy.resize(nbInteret);
	vx.resize(nbInteret);
	for (int i(0); i < nbInteret; ++i)
		vy[i] = points[i].second+1, vx[i] = points[i].first;
	vector<vector<ll>> dp(2, vector<ll>(nbInteret+1, INF));
	dp[0][0] = dp[1][0] = 0;
	ll ans(INF);
	for (int photos(1); photos <= nbPhotos; photos++)
	{
		StaticCHT cht(nbInteret);
		// dp[i][j] = min_t<j dp[i-1][t] + (vy[j-1]-vx[t])^2 - max(0, vy[t-1] - vx[t])^2
		// 					= vy[j-1]^2 + min_t<j (-2vx[t]) vy[j-1] + vx[t]^2 - max... + dp[i-1][t]
		int cur(photos&1);
		int prev(!cur);
		for (int take(1); take <= SZ(points); ++take)
		{
			ll a = -2 * vx[take-1];
			ll b = sq(vx[take-1]) + dp[prev][take-1]  - sq(max(0, (take > 1) ? vy[take-2]-vx[take-1] : 0));
			if (dp[prev][take-1] != INF)
				cht.add(a, b);
			dp[cur][take] = cht.query(vy[take-1]) + sq(vy[take-1]);
		}
		ans = min(ans, dp[cur][nbInteret]);
	}
	return ans;
}

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