#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> R, C;
int N, K;
vector<long long> A(1, -1), B(1, -1);
long long sq(long long x)
{
return x*x;
}
const long long INF = 5'000'000'000'000;
long long parametric_search(long long X, long long Y)
{
long long CT = (X + Y)/2;
// cerr << "ct = " << CT << '\n';
long long dp[N+1]; // minimum area+cost to cover first i ranges
int photos[N+1];
dp[0] = photos[0] = 0;
for(int i = 1; i <= N; i++)
{
photos[i] = i;
dp[i] = INF;
for(int j = 0; j < i; j++)
{
long long val;
val = CT + dp[j] + sq(B[i] - A[j+1]) - sq(max(0LL, B[j] - A[j+1]));
if(val < dp[i])
{
dp[i] = val;
photos[i] = photos[j] + 1;
}
else if(val == dp[i])
{
photos[i] = min(photos[i], photos[j] + 1);
}
}
}
// for(int i = 1; i <= N; i++) cerr << dp[i] << ' ';
// cerr << '\n';
// for(int i = 1; i <= N; i++) cerr << photos[i] << ' ';
// cerr << '\n';
if(X == Y) return dp[N] - CT * photos[N];
else
{
if(photos[N] <= K)
return parametric_search(X, CT);
else return parametric_search(CT+1, Y);
}
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
// cerr << '\n';
for(int i = 0; i < n; i++)
{
if(r[i] > c[i]) swap(r[i], c[i]);
}
R = r;
C = c;
int I[n];
for(int i = 0; i < n; i++)
I[i] = i;
sort(I, I+n, [] (int x, int y)
{
if(R[x] == R[y])
return C[x] > C[y];
return R[x] < R[y];
});
int maxb = -1;
for(int i:I)
{
// cerr << i << ' ';
if(maxb < c[i])
{
maxb = c[i];
A.push_back(r[i]);
B.push_back(c[i] + 1);
}
}
N = A.size() - 1;
K = min(k, N);
cerr << "points: \n";
for(int i = 1; i <= N; i++) cerr << A[i] << ' ' << B[i] << '\n';
cerr << "check\n";
return parametric_search(0LL, INF);
}
