#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
const ll INF = 1e18;
using ld = long double;
struct StaticCHT
{
vector<int> 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)
{
if (nbInteret <= 500 and dim <= 1000)
{
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(nbPhotos+1, vector<ll>(SZ(points)+1, INF));
for (int i(0); i <= nbPhotos; ++i)
dp[i][0] = 0;
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]
for (int take(1); take <= SZ(points); ++take)
{
ll a = -2 * vx[take-1];
ll b = sq(vx[take-1]) + dp[photos-1][take-1] - sq(max(0, (take > 1) ? vy[take-2]-vx[take-1] : 0));
if (dp[photos-1][take-1] != INF)
cht.add(a, b);
dp[photos][take] = cht.query(vy[take-1]) + sq(vy[take-1]);
}
}
ll ans(INF);
for (int i(0); i <= nbPhotos; ++i)
ans = min(ans, dp[i][SZ(points)]);
return ans;
}
}
