#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll INF = 1e18;
int n, m, k;
vl r, c, L, R;
inline ll isq(ll x) {return x*x;}
void preprocess(int N, int M, int K, vi Row, vi Col) {
vector<int> sorted_points(N); iota(sorted_points.begin(), sorted_points.end(), 0);
sort(sorted_points.begin(), sorted_points.end(), [&](int a, int b) {
ll La = min(Row[a], Col[a]), Ra = max(Row[a], Col[a]), Lb = min(Row[b], Col[b]), Rb = max(Row[b], Col[b]);
return La == Lb ? Ra > Rb : La < Lb;
});
vector<int> points; int lastR = -1;
for (int i = 0; i < N; i++) {
int cur = sorted_points[i];
int rcur = max(Row[cur], Col[cur]);
if (rcur > lastR) {
points.push_back(cur);
lastR = rcur;
}
}
n = points.size(); m = M; k = K;
r.resize(n); c.resize(n); L.resize(n); R.resize(n);
for (int i = 0; i < n; i++) {
r[i] = Row[points[i]]; c[i] = Col[points[i]];
L[i] = min(r[i], c[i]);
R[i] = max(r[i], c[i]);
}
}
// n <= 50, m <= 100
ll sub1() {
vvi used(m, vi(m, 0));
for (int i = 0; i < n; i++) {
for (int x = L[i]; x <= R[i]; x++) {
for (int y = L[i]; y <= R[i]; y++) {
used[x][y]++;
}
}
}
ll ans = 0;
for (int x = 0; x < m; x++) {
for (int y = 0; y < m; y++) {
if (used[x][y]) ans++;
}
}
return ans;
}
// n <= 500, m <= 1000, r[i] = c[i]
// essentially DP[i][k] = min cost to cover first i using k
// DP[i][k] = min(DP[j[k-1] + (r[i] - r[j+1] + 1)^2)
ll sub2() {
vvl DP(n, vl(k+1, INF));
ll ans = INF;
for (int kv = 1; kv <= k; kv++) {
DP[0][kv] = 1;
for (int i = 1; i < n; i++) {
DP[i][kv] = DP[i-1][kv-1] + 1;
for (int j = 0; j < i; j++) {
ll prev = j == 0 ? 0 : DP[j-1][kv-1];
ll delta = (c[i] - c[j] + 1);
delta *= delta;
DP[i][kv] = min(DP[i][kv], prev + delta);
}
}
ans = min(ans, DP[n-1][kv]);
}
return ans;
}
// n <= 500, m <= 1000
// same dp but we need to account for the squares, as well as overlap between them
ll cost(int i, int j) {
ll overlap = 0;
if (i > 0 && R[i-1] >= L[i]) {
overlap = isq(R[i-1] - L[i] + 1);
}
ll area = isq(R[j] - L[i] + 1);
return area - overlap;
}
// DP[k-1][i-1] + cost(i, j)
ll get_dp(int i, int j, int k, vvl &DP) {
ll prev_value = i == 0 ? 0 : DP[i-1][k-1];
return prev_value + cost(i, j);
}
ll sub3() {
vvl DP(n, vl(k+1, INF));
ll ans = INF;
for (int kv = 1; kv <= k; kv++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
ll prev = j == 0 ? 0 : DP[j-1][kv-1];
if (prev + cost(j, i) < DP[i][kv]) {
DP[i][kv] = prev + cost(j, i);
}
}
}
ans = min(ans, DP[n-1][kv]);
}
return ans;
}
// find the optimal previous index to minimise DP[k][i], searching only between [lo, hi]
int opt(int k, int i, vvl &DP, int lo, int hi) {
int best = -1; ll best_val = INF;
for (int j = lo; j <= i && j <= hi; j++) {
if (get_dp(j, i, k, DP) < best_val) {
best = j;
best_val = get_dp(j, i, k, DP);
}
}
return best;
}
// solve subtask 4&5 with divide and conquer rather than convex hull trick
ll divide_and_conquer() {
vvl DP(n, vl(k+1, INF));
ll ans = INF;
for (int kv = 1; kv <= k; kv++) {
int mid = n / 2;
int opt_mid = opt(kv, mid, DP, 0, mid);
for (int i = 0; i < n; i++) {
int lo = 0, hi = opt_mid;
if (i > mid) lo = opt_mid, hi = n - 1;
DP[i][kv] = get_dp(opt(kv, i, DP, lo, hi), i, kv, DP);
}
ans = min(ans, DP[n-1][kv]);
}
return ans;
}
// n <= 4000, m <= 1m
/*
let P = prev
let O = max(0, R[j-1] - L[j] + 1)^2
let L = L[j]-1
let R = R[i]
f(x) = (R-L)^2 + P + O
= R^2 - 2LR + L^2 + P + O
let C = L^2 + P + O
∴ f(x) = R^2 - 2LR + C
so we can do a cht/li chao tree
*/
// functions of the form f(x) = x^2 + bx + c
struct Function {
ll b, c;
ll seg;
Function(ll B = 0, ll C = INF, ll s = 0) : b(B), c(C), seg(s) {};
ll evaluate(ll x) {
return x*x + b*x + c;
}
};
bool better(Function& f1, Function& f2, ll x) {
ll v1 = f1.evaluate(x), v2 = f2.evaluate(x);
if (v1 != v2) return v1 < v2;
return f1.seg < f2.seg;
}
struct Node {
Function best;
Node *left, *right;
Node() : best(Function()), left(nullptr), right(nullptr) {};
Node(Function Best) : best(Best), left(nullptr), right(nullptr) {};
};
// implicit segtree storing minimum function at x for x in [0, 1m]
struct LiChaoTree {
int lower, upper;
Node* root;
LiChaoTree() {};
LiChaoTree(int L, int U) {
lower = L;
upper = U;
root = new Node();
}
Node* update(Node* cur, int l, int r, Function fnew) {
if (!cur) cur = new Node();
int m = l + (r - l) / 2;
if (better(fnew, cur->best, m)) swap(cur->best, fnew);
if (better(fnew, cur->best, l)) cur->left = update(cur->left, l, m, fnew);
else if (better(fnew, cur->best, r)) cur->right = update(cur->right, m, r, fnew);
return cur;
}
pair<ll, ll> query(Node* cur, int l, int r, ll x) {
if (!cur) return {INF, 0};
pair<ll, ll> our_val = {cur->best.evaluate(x), cur->best.seg};
if (l + 1 == r) return our_val;
int m = l + (r - l) / 2;
if (x < m) return min(our_val, query(cur->left, l, m, x));
else return min(our_val, query(cur->right, m, r, x));
}
void update(Function fnew) {
update(root, lower, upper+1, fnew);
}
pair<ll, ll> query(ll x) {
return query(root, lower, upper+1, x);
}
};
/*
ll sub45() { // solves 4 & 5 using cht
vl overlap(n, 0);
for (int i = 1; i < n; i++) {
ll over = max(0LL, R[i-1] - L[i] + 1);
over *= over;
overlap[i] = over;
}
vl prev_dp(n, INF), cur_dp(n, INF);
for (int i = 0; i < n; i++) {
prev_dp[i] = (R[i] - L[0] + 1) * (R[i] - L[0] + 1);
}
for (int kv = 2; kv <= k; ++kv) {
cur_dp.assign(n, INF);
LiChaoTree lct(0, m);
ll L0 = L[0] - 1;
lct.update(Function(-2*L0, L0*L0));
cur_dp[0] = (R[0] - L[0] + 1) * 1LL * (R[0] - L[0] + 1);
for (int i = 1; i < n; ++i) {
ll Lj = L[i] - 1;
ll B = -2 * Lj;
ll C = prev_dp[i-1] + Lj*Lj - overlap[i];
lct.update(Function(B, C));
cur_dp[i] = lct.query(R[i]);
}
prev_dp.swap(cur_dp);
}
return prev_dp.back();
}
*/
void compute_dp(ll lambda, vl& dp, vl &cnt, const vl &overlap) {
dp.assign(n, INF);
cnt.assign(n, 0);
LiChaoTree lct(0, m+1);
ll L0 = L[0] - 1;
lct.update(Function(-2*L0, L0*L0 + lambda, 1));
auto r0 = lct.query(R[0]);
dp[0] = r0.first;
cnt[0] = r0.second;
for (int i = 1; i < n; ++i) {
ll Lj = L[i] - 1;
ll B = -2 * Lj;
ll C = dp[i-1] + Lj*Lj + lambda - overlap[i];
int nseg = cnt[i-1] + 1;
lct.update(Function(B, C, nseg));
auto res = lct.query(R[i]);
dp[i] = res.first;
cnt[i] = res.second;
}
}
ll sub6() {
vl overlap(n, 0);
for (int i = 1; i < n; i++) {
ll over = max(0LL, R[i-1] - L[i] + 1);
over *= over;
overlap[i] = over;
}
ll lo = 0, hi = 1e13;
vector<ll> dp, cnt;
while (lo < hi) {
ll mid = (lo + hi) >> 1;
compute_dp(mid, dp, cnt, overlap);
if (cnt.back() > k) lo = mid + 1;
else hi = mid;
}
compute_dp(lo, dp, cnt, overlap);
return dp.back() - 1LL * lo * k;
}
ll take_photos(int N, int M, int K, vi Row, vi Col) {
preprocess(N, M, K, Row, Col);
// return sub1();
// return sub2();
// return sub3();
return divide_and_conquer();
// return sub45();
// return sub6();
}
