#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
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) {
assert(1 <= n && n <= 4000);
assert(1 <= m && m <= 1000000);
vector<array<int, 2>> pos = extract_relevant_sorted_points(r, c);
n = pos.size();
vector<vector<long long>> dp(n+1, vector<long long>(k+1, 1e13));
vector<vector<int>> opt(n+1, vector<int>(k+1));
for (int j = 0; j <= k; j++) {
dp[0][j] = 0;
}
for (int j = 1; j <= k; j++) {
for (int i = n; i >= 1; i--) {
int left_end = j == 1 ? 0 : opt[i][j-1];
int right_end = min(i == n ? n : opt[i+1][j], i-1);
for (int t = left_end; t <= right_end; t++) {
long long side_length = pos[i-1][1] - pos[t][0] + 1;
long long area = side_length * side_length;
long long overlap_side_length = t == 0 ? 0 : max(pos[t-1][1] - pos[t][0] + 1, 0);
long long overlap_area = overlap_side_length * overlap_side_length;
long long current_value = dp[t][j-1] + area - overlap_area;
if (current_value < dp[i][j]) {
opt[i][j] = t;
dp[i][j] = current_value;
}
}
}
}
return dp[n][k];
}
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 smaller
}
while (!stack.empty() && stack.back()[0] >= r) stack.pop_back();
stack.push_back({r, c});
}
return stack;
}
