#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
/*
Cells (r, c) and (c, r) are equivalent.
(a, b) = (min(r, c), max(r, c))
A square (p, q) covers point (a, b) if and only if p <= a and b <= q
If (a1, b1) and (a2, b2) are points and a1 <= a2 and b2 <= b1, then (a2, b2) is irrelevant.
So, for any (a1, b1) and (a2, b2) a1 < a2 <=> b1 < b2
When checking for overlapping areas, we only have to consider the last square.
Let points be sorted (a[1], b[1]) < (a[2], b[2]) < .... < (a[x], b[x]).
Let dp[i][k] be the minimum area required to cover the first i points using k squares.
dp[0][k] = 0
dp[i][k] = min{dp[j][k-1] + (b[i] - a[j] + 1)^2 - max(0, b[j] - a[j] + 1)^2 | j=1..i-1}
A point (a, b) requires a square of endpoints (a, a) and (b, b) (side = b-a+1)
dp[j][x-1] + sq(b[i]-a[j+1])
dp[j][x-1] + b[i]^2 + a[j+1]^2 - 2*b[i]*a[j+1]
1*[[dp[j][x-1] + a[j+1]^2]] + (-2*b[i])*[[ a[j+1] ]]
*/
vector<int> R, C;
vector<long long> a(1, -5), b(1, -5);
int N, M, K;
vector<long long> A, B;
long long sq(long long x)
{
return x*x;
}
const long long INF = 5'000'000'000'000; //CHANGE!!!!!!!!!
long long parametric_search(long long X, long long Y)
{
cerr << "search " << X << ' ' << Y << '\n';
long long CT = (X + Y)/2;
// if(X != Y) CT++;
cerr << "ct = " << CT << '\n';
long long dp[N+1]; // minimum area+cost to cover first i points
int photos[N+1];
dp[0] = photos[0] = 0;
dp[1] = sq(B[1] - A[1]) + CT;
photos[1] = 1;
for(int i = 2; i <= N; i++)
{
int J = -1;
long long opt = INF;
for(int j = 0; j < i; j++)
{
long long val;
if(B[j] - A[i] + 1 >= 1)
val = CT + dp[j] + sq(B[i] - A[j+1]) - sq(B[j] - A[i]);
else
val = CT + dp[j] + sq(B[i] - A[j+1]);
if(val < opt)
{
opt = val;
J = j;
}
}
dp[i] = opt;
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';
R = r;
C = c;
N = n;
M = m;
K = k;
int I[n];
for(int i = 0; i < n; i++)
I[i] = i;
sort(I, I+n, [] (int x, int y)
{
if(min(R[x], C[x]) == min(R[y], C[y]))
return max(R[x], C[x]) > max(R[y], C[y]);
return min(R[x], C[x]) < min(R[y], C[y]);
});
int maxb = -1;
for(int i:I)
{
// cerr << i << ' ';
if(maxb < max(r[i], c[i]))
{
maxb = max(r[i], c[i]);
a.push_back(min(r[i], c[i]));
b.push_back(max(r[i], c[i]) + 1);
}
}
n = a.size() - 1;
// for(int i = 1; i <= n; i++) cerr << a[i] << ' ' << b[i] << '\n';
k = min(k, n);
A = a;
B = b;
N = n;
K = k;
cerr << "points: \n";
for(int i = 1; i <= N; i++) cerr << A[i] << ' ' << B[i] << '\n';
cerr << "check\n";
return parametric_search(0LL, INF);
}
