#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1e6 + 123;
const ll INF = 1e18;
ll x[N], y[N];
ll sq (ll x) { return x * x; }
struct line {
ll k, b;
ll f (ll x) {
return k * x + b;
}
};
ld inter (line a, line b) {
return ld(b.b - a.b) / ld(a.k - b.k);
}
struct cht {
vector<line> v;
void add (line a) {
while (v.size() > 1 && inter (v.back(), v[v.size() - 2]) > inter (v[v.size() - 2], a)) {
v.pop_back();
}
v.push_back (a);
}
ll get (ll x) {
if (0) {
ll ans = -INF;
for (auto l : v) ans = max (ans, l.f(x));
return ans;
assert (0);
}
if (v.empty()) return -INF;
int l = 0, r = int(v.size()) - 2;
ll ans = v.back().f(x);
while (l <= r) {
int m = (l + r) >> 1;
ans = max (ans, v[m].f(x));
if (inter (v[m], v[m + 1]) < x) {
l = m + 1;
} else {
r = m - 1;
}
}
if (l < (int)v.size())
ans = max (ans, v[l].f(x));
if (r >= 0)
ans = max (ans, v[r].f(x));
return ans;
}
};
ll calc (int n, int m, int k) {
k = min (n, k);
vector<ll> dp(n + 1, INF), new_dp;
for (int i = 1 ; i <= n ; ++ i) {
dp[i] = sq(y[i] - x[1] + 1);
// cout << dp[i] << " ";
}
// cout << "\n";
for (int _ = 2 ; _ <= k ; ++ _) {
new_dp = vector<ll>(n + 1, INF);
cht ok;
for (int i = 1 ; i <= n ; ++ i) {
if (i >= _)
ok.add ({2 * x[i], -dp[i - 1] - sq(x[i]) + 2 * x[i] - 1 + sq(max(0ll,y[i-1]-x[i]+1))});
if (i >= _)
new_dp[i] = sq(y[i]) + 2 * y[i] - ok.get (y[i]);
// cout << new_dp[i] << " ";
}
// cout << "\n";
swap (dp, new_dp);
}
return dp[n];
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int,int>> a(n);
for (int i = 0 ; i < n ; ++ i) {
if (r[i] > c[i]) swap (r[i], c[i]);
a[i] = {r[i], c[i]};
}
sort (a.begin(), a.end());
int n_ = 0;
for (int i = 0, ymx = -1 ; i < n ; ++ i) {
bool rm = false;
//cout << a[i].first << " " << a[i].second << " a[i]\n";
if (i + 1 < n && a[i].first == a[i + 1].first) {
rm = true;
}
if (a[i].second <= ymx) {
rm = true;
}
if (!rm) {
++n_;
x[n_] = a[i].first;
y[n_] = a[i].second;
//cout << x[n_] << " " << y[n_] << " {x,y}\n";
}
if (i + 1 > n || a[i].first != a[i + 1].first)
ymx = max (ymx, a[i].second);
}
n = n_;
return calc (n, m, k);
}
