#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);
}
set<pair<ll, ll>> hull;
vector<pair<ll, ll>> points;
vector<ll> dp_prev, dp_cur;
ll valOnLine(pair<ll, ll> line, ll x) {
return (line.second - x * line.first);
}
ll query(ll x) {
while (hull.size() > 1) {
auto first = hull.begin(), second = next(first);
if (valOnLine(*first, x) > valOnLine(*second, x)) hull.erase(first);
else break;
}
return valOnLine(*hull.begin(), x);
}
void addLine(ll m, ll c) {
while (hull.size() > 1) {
auto last = prev(hull.end());
ll m1 = -last->first, c1 = last->second;
ll m2 = -prev(last)->first, c2 = prev(last)->second;
if ((c - c1) * (m2 - m1) <= (c1 - c2) * (m1 - m)) hull.erase(last);
else break;
}
hull.emplace(-m, c);
}
ll getA(ll j) {
return (-2 * points[j].first + 2);
}
ll getB(ll j) {
return (sq(points[j].first - 1) + (j ? dp_prev[j - 1] - positiveArea(points[j].first, points[j - 1].second) : 0));
}
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);
int newN = points.size();
dp_prev.assign(newN, LLONG_MAX / 2);
dp_cur.assign(newN, 0);
// cout << newN << '\n';
for (int i = 1; i <= k; ++i) {
hull.clear();
addLine(getA(0), getB(0));
// for (auto &i : hull) cout << i.first << ' ' << i.second << " ";
// cout << '\n';
for (int j = 1; j <= newN; ++j) {
ll ri = points[j - 1].second;
dp_cur[j - 1] = sq(ri) + query(ri);
// cout << j << ' ' << ri;
if (j < newN) addLine(getA(j), getB(j));
// cout << '\n';
}
dp_prev = dp_cur;
// for (auto &i : dp_prev) cout << i << ' ';
// cout << '\n';
}
// for (auto &i : hull) cout << i.first << ' ' << i.second << " ";
// cout << '\n';
return dp_prev[newN - 1];
}
