#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
#include <complex>
using namespace std;
using ll = long long;
typedef complex<ll> point;
#define x real
#define y imag
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);
}
ll dot(point a, point b) {
return ((conj(a) * b).x());
}
ll cross(point a, point b) {
return ((conj(a) * b).y());
}
vector<point> hull, vec;
vector<ll> countHull;
void addLine(ll m, ll c, ll count) {
point newLine({m, c});
while (!vec.empty() && (dot(vec.back(), newLine - hull.back()) < 0)) {
vec.pop_back();
hull.pop_back();
countHull.pop_back();
}
if (!hull.empty()) vec.push_back(point({0, 1}) * (newLine - hull.back()));
countHull.push_back(count);
hull.push_back(newLine);
}
pair<ll, ll> query(ll ri) {
point toFind({ri, 1});
ll idx = lower_bound(vec.begin(), vec.end(), toFind, [](point a, point b) {return (cross(a, b) > 0);}) - vec.begin();
return {dot(toFind, hull[idx]), countHull[idx]};
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pair<ll, ll>> oriPoints, points;
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();
auto check = [&] (ll cost, ll &res) {
hull.clear(); vec.clear(); countHull.clear();
vector<ll> dp(newN + 1, 0), counts(newN + 1, 0);
for (int i = 1; i <= newN; ++i) {
ll m = 2 * (points[i - 1].first - 1), c = sq(points[i - 1].first - 1) + dp[i - 1] + (i > 1 ? positiveArea(points[i - 1].first, points[i - 2].second) : 0);
addLine(m, c, counts[i - 1]);
auto cur = query(-points[i - 1].second);
dp[i] = cur.first + cost + sq(points[i - 1].second);
counts[i] = cur.second + 1;
}
res = dp[newN];
return (counts[newN] <= k);
};
ll low = 0, high = sq(m), res = LLONG_MAX / 2;
while (low < high) {
ll mid = (low + high) / 2;
if (check(mid, res)) high = mid;
else low = mid + 1;
}
check(low, res);
return (res - k * low);
}
