#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
#include <set>
using namespace std;
using ll = long long;
ll sq(ll a) {
return a * a;
}
ll sq(int a) {
return (ll)(a) * a;
}
ll getArea(pair<ll, ll> a) {
return sq(a.second - a.first + 1);
}
ll getArea(ll a, ll b) {
return sq(b - a + 1);
}
ll positiveArea(ll a, ll b) {
ll sideLength = b - a + 1;
return (sideLength > 0 ? sq(sideLength) : 0);
}
vector<ll> dp_prev, dp_cur;
vector<pair<ll, ll>> points;
void compute(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) / 2;
pair<ll, int> best = {LLONG_MAX / 2, -1};
for (int i = optl; i <= min(mid, optr); ++i) {
best = min(best, {(i ? dp_prev[i - 1] : 0) + getArea(points[i].first, points[mid].second) - (i ? positiveArea(points[i].first, points[i - 1].second) : 0), i});
}
dp_cur[mid] = best.first;
compute(l, mid - 1, optl, best.second);
compute(mid + 1, r, best.second, optr);
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pair<ll, ll>> oriPoints;
for (ll i = 0; i < n; ++i) {
if (r[i] > c[i]) swap(r[i], c[i]);
oriPoints.emplace_back(r[i], c[i]);
}
sort(oriPoints.begin(), oriPoints.end());
pair<ll, ll> cur = oriPoints[0];
for (ll i = 1; i < n; ++i) {
if (oriPoints[i].first == cur.first) cur.second = max(oriPoints[i].second, cur.second);
else if (cur.second < oriPoints[i].second) {
if (cur.first != -1) points.emplace_back(cur);
cur = oriPoints[i];
}
}
points.emplace_back(cur);
// for (auto &i : points) cout << i.first << ' ' << i.second << " ";
// cout << '\n';
int newN = points.size();
dp_prev.assign(newN, LLONG_MAX / 2);
dp_cur.assign(newN, 0);
for (int i = 0; i < k; ++i) {
compute(0, newN - 1, 0, newN - 1);
dp_prev = dp_cur;
// for (int i : dp_prev) cout << i << ' ';
// cout << '\n';
}
return dp_prev[newN - 1];
}
