#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
bool Q;
struct Line {
mutable long long k, m, p; // slope, y-intercept, last optimal x
bool operator<(const Line& o) const {
return Q ? p < o.p : k < o.k;
}
};
struct LineContainer : multiset<Line> {
const long long inf = LLONG_MAX;
long long div(long long a, long long b) { // floored division
if (b < 0) a *= -1, b *= -1;
if (a >= 0) return a / b;
return -((-a + b - 1) / b);
}
// updates x->p, determines if y is unneeded
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return 0; }
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(long long k, long long m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
long long query(long long x) const { // gives max value
assert(!empty());
Q = 1; auto l = *lower_bound({0, 0, x}); Q = 0;
return l.k * x + l.m;
}
};
vector<array<int, 2>> extract_relevant_sorted_points(const vector<int>& r, const vector<int>& c);
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<array<int, 2>> pos = extract_relevant_sorted_points(r, c);
n = pos.size();
vector<LineContainer> dp(k+1);
for (int j = 0; j <= k; j++) {
dp[j].add(-2 * (1 - pos[0][0]), -(1 - pos[0][0]) * (1 - pos[0][0]));
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
long long dp_value = pos[i-1][1] * pos[i-1][1] - dp[j-1].query(pos[i-1][1]);
if (i == n && j == k) {
return dp_value;
}
long long overlap_side_length = max<long long>(0, pos[i-1][1] - pos[i][0] + 1);
long long overlap_area = overlap_side_length * overlap_side_length;
long long slope = - 2 * (1 - pos[i][0]);
long long intercept = - (dp_value + overlap_area + (1 - pos[i][0]) * (1 - pos[i][0]));
dp[j].add(slope, intercept);
}
}
assert(false);
}
vector<array<int, 2>> extract_relevant_sorted_points(const vector<int>& r, const vector<int>& c) {
const int n = r.size();
vector<array<int, 2>> sorted_points;
for (int i = 0; i < n; i++) {
sorted_points.push_back({max(r[i], c[i]), min(r[i], c[i])});
}
sort(sorted_points.begin(), sorted_points.end());
for (int i = 0; i < n; i++) {
sorted_points[i] = { sorted_points[i][1], sorted_points[i][0] };
}
vector<array<int, 2>> stack;
for (const auto [r, c] : sorted_points) {
if (!stack.empty() && stack.back()[1] == c) {
continue; // Our point is smalong longer
}
while (!stack.empty() && stack.back()[0] >= r) stack.pop_back();
stack.push_back({r, c});
}
return stack;
}
