#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);
void calculate_dp_range(int j, int li, int ri, int lt, int rt, vector<vector<long long>>& dp, const vector<array<int, 2>>& pos);
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<vector<long long>> dp(n+1, vector<long long>(k+1, 1e13));
for (int j = 0; j <= k; j++) {
dp[0][j] = 0;
}
for (int j = 1; j <= k; j++) {
calculate_dp_range(j, 1, n+1, 0, n-1, dp, pos);
}
return dp[n][k];
}
void calculate_dp_range(int j, int li, int ri, int lt, int rt, vector<vector<long long>>& dp, const vector<array<int, 2>>& pos) {
if (li == ri)
return;
int opt = lt;
int i = (li + ri) / 2;
for (int t = lt; t <= min(rt, i - 1); 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 = t;
dp[i][j] = current_value;
}
}
if (ri - li > 1) {
calculate_dp_range(j, li, i, lt, opt, dp, pos);
calculate_dp_range(j, i, ri, opt, rt, dp, pos);
}
}
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;
}
