#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, M, K;
const ll INF = 1ll << 60ll;
ll take_photos(int N_, int M_, int K_, vector<int> X, vector<int> Y)
{
N = N_; M = M_; K = K_;
vector<int> dist(M), h(M);
for (int i = 0; i < N; i++)
{
if (X[i] > Y[i])
swap(X[i], Y[i]);
dist[X[i]] = max(dist[X[i]], Y[i] - X[i] + 1);
h[X[i]] = max(h[X[i]], Y[i] + 1);
}
int mx = 0;
vector<pair<ll, ll>> nodes;
for (int i = 0; i < M; i++)
{
if (h[i] <= mx)
{
dist[i] = h[i] = 0;
continue;
}
mx = h[i];
nodes.push_back({i, mx});
}
const int node_cnt = nodes.size();
nodes.push_back({M+1, M+1});
vector<vector<ll>> dp(node_cnt + 1, vector<ll>(K+1, INF));
dp[0][0] = 0;
for (int i = 0; i < node_cnt; i++)
{
for (int k = 0; k < K; k++)
{
for (int j = i; j < node_cnt; j++)
{
ll sz = nodes[j].second - nodes[i].first;
ll overlap = max(0ll, nodes[i].first + sz - nodes[j+1].first);
dp[j+1][k+1] = min(dp[j+1][k+1], dp[j][k] + sz * sz - overlap * overlap);
}
}
}
while (dp.back().back() == INF)
dp.back().pop_back();
ll res = dp.back().back();
// DP[i][k] = min number of cells up to i with k photos
// (Provided that you still need to take a photo there)
// Remember to subtract overlapping area
return res;
}
