/**
* I don't feel like fully solving this, so maybe i'll just score some partials.
*
* [S1] Too trivial
* [S2] Each point lies on the main diagonal. Clearly, no two squares should have
* common squares, which means the points are partitioned into contiguous
* segments. O(n^2 * k) dp kills it.
* [S3] Maybe we can somehow sort the points based on their columns, then apply [S2]?
* Yep, pretty much analagous to [S2]. The key here is that if (2,5), (3,5),
* the square that covers (2,5) must cover (3,5).
*
* Time Complexity: O(n^2 * k)
* Implementation 1 ([S3] hold, only solves the first two)
*/
#include <bits/stdc++.h>
#include "aliens.h"
typedef long long ll;
const int N_MAX = 500;
const ll INF = 0x3f3f3f3f3f3f;
inline ll sqr(int k) { return ll(k) * ll(k); }
ll cover[N_MAX + 1][N_MAX + 1];
struct point_t {
int i, j;
};
inline bool operator<(const point_t& p1, const point_t& p2) { return p1.i < p2.i || (p1.i == p2.i && p1.j < p2.j); }
inline bool operator==(const point_t& p1, const point_t& p2) { return p1.i == p2.i && p1.j == p2.j; }
ll take_photos(int n, int m, int max_sqr, std::vector<int> row, std::vector<int> col) {
if (max_sqr == n) {
std::vector<point_t> values(n);
for (int i = 0; i < n; i++)
values[i].i = row[i], values[i].j = col[i];
std::sort(values.begin(), values.end());
return std::unique(values.begin(), values.end()) - values.begin();
}
std::sort(row.begin(), row.end());
n = std::unique(row.begin(), row.end()) - row.begin();
cover[0][0] = 0;
for (int s = 1; s <= max_sqr; s++)
cover[0][s] = INF;
for (int k = 0; k < n; k++) {
cover[k + 1][0] = INF;
for (int s = 1; s <= max_sqr; s++) {
cover[k + 1][s] = INF;
for (int m = 0; m <= k; m++) { // [m,k]
cover[k + 1][s] = std::min(
cover[k + 1][s],
cover[m][s - 1] + sqr(row[k] - row[m] + 1)
);
}
}
}
ll ans = INF;
for (int s = 1; s <= max_sqr; s++)
ans = std::min(ans, cover[n][s]);
return ans;
}
