#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
struct Line {
mutable long long k, m, p; // slope, y-intercept, last optimal x
};
struct LineContainer {
deque<Line> lines;
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);
}
long long isect(const Line& x, const Line& y) {
if (x.k == y.k && x.m > y.m)
return inf;
assert(x.k < y.k);
return div(y.m - x.m, x.k - y.k);
}
void add(long long k, long long m) {
if (!lines.empty() && lines.back().k == k && lines.back().m >= m) return;
Line line{k, m, inf};
while (lines.size() > 1 && isect(lines.back(), line) <= isect(lines[lines.size()-2], lines.back()))
lines.pop_back();
lines.push_back(line);
if (lines.size() >= 2) {
lines[lines.size()-2].p = isect(lines[lines.size()-2], lines.back());
}
}
long long query(long long x) {
assert(!lines.empty());
while (x > lines[0].p) lines.pop_front();
assert(!lines.empty());
return lines[0].k * x + lines[0].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 * static_cast<long long>(1 - pos[0][0]), -static_cast<long long>(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 = static_cast<long long>(pos[i-1][1]) * pos[i-1][1] - dp[j-1].query(pos[i-1][1]);
if (i == n && j == k) {
return dp_value;
}
if (i == n || j == k) {
continue;
}
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 * static_cast<long long>(1 - pos[i][0]);
long long intercept = - (dp_value - overlap_area + static_cast<long long>(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;
}
