#include <bits/stdc++.h>
#include "aliens.h"
using ll = long long;
using namespace std;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
// Sub1
if (n <= k && n <= 50 && m <= 100)
{
vector<vector<int>> arr(m + 3, vector<int>(m + 3));
for (int i = 0; i < n; i++)
{
int xx = r[i], yy = c[i];
for (int x = min(xx, yy); x <= max(xx, yy); x++)
for (int y = min(xx, yy); y <= max(xx, yy); y++)
{
arr[x][y]++;
}
}
int cnt = 0;
for (int x = 0; x <= m; x++)
for (int y = 0; y <= m; y++)
cnt += (arr[x][y] != 0);
return cnt;
}
bool check_s2 = 1;
for (int i = 0; i < n; i++)
check_s2 &= (r[i] == c[i]);
if (check_s2)
{
// Observation : cover (l, l), (r, r) -> cover all [(l, l), (l + 1, l + 1), ..., (r, r)]
// For each optimal square that contain some point, the (l, l) must match one of the (r_i, r_i);
// Sort by r_i + remove all duplicate -> Segment cover on diagonal such that sum of (r - l + 1)^2 for all ranges is minimal
// dp[i][k] -> Cover first i points using k segment
// dp[i][k] = min(all(dp[i'][k-1]) + (r[i-1] - l[i'] + 1) ^ 2;
vector<pair<int, int>> pos;
for (int i = 0; i < n; i++)
{
pos.push_back(make_pair(r[i], c[i]));
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
vector<vector<int>> dp(int(pos.size() + 3), vector<int>(k + 3, 0));
n = pos.size();
for (int i = 0; i < n; i++)
{
for (int dk = 1; dk <= k; dk++)
{
int mindp = 1e9, minindex = -1;
for (int ii = 0; ii < i; ii++)
if (dp[ii][dk - 1] < mindp)
{
minindex = ii;
mindp = dp[ii][dk - 1];
}
long long dd = max(0, (pos[i - 1].first - pos[minindex].second + 1) *
(pos[i - 1].first - pos[minindex].second + 1));
dp[i][dk] = mindp + dd * dd;
}
}
return dp[n - 1][k];
}
}
