/**
* 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).
* Well, i really shouldn't have written "Too trivial" in [S1]. The following
* observation is: if two segments (a1,b1) (a2,b2) satisfy a1 <= a2 and
* b1 >= b2, the former's square completely contains the latter, so we shall
* remove the latter. This means when we sort the points based on their b
* values, a values are strictly increasing, ENSURING that intersection of area
* is calculated correctly. So in fact, [S3] = [S1] + [S2]!
*
* Time Complexity: O(n^2 * k)
* Implementation 1.5 (first 3 tasks)
*/
#include <bits/stdc++.h>
#include "aliens.h"
typedef long long ll;
const int N_MAX = 500;
const int INF = 0x3f3f3f3f;
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.j == p2.j; }
ll take_photos(int n, int m, int max_sqr, std::vector<int> row, std::vector<int> col) {
std::vector<point_t> values(n);
for (int k = 0; k < n; k++)
values[k].i = std::min(row[k], col[k]), values[k].j = std::max(row[k], col[k]);
std::sort(values.begin(), values.end(),
[](const point_t& p1, const point_t& p2) {
return p1.j < p2.j || (p1.j == p2.j && p1.i > p2.i);
});
// The most important part I missed in the first few submissions:
std::vector<bool> skipped(n, false);
for (int k = n - 1, suffix_min = INF; k >= 0; k--) {
if (values[k].i >= suffix_min)
skipped[k] = true;
suffix_min = std::min(suffix_min, values[k].i);
}
int front = 0; // an algo. working like std::unique()
for (int k = 0; k < n; k++) {
if (skipped[k])
continue;
values[front++] = values[k];
}
n = front;
// std::cerr << "debug: " << n << std::endl;
// for (int i = 0; i < n; i++)
// std::cerr << values[i].i << ' ' << values[i].j << std::endl;
for (int k = 0; k <= n; k++) {
for (int s = 0; s <= max_sqr; s++)
cover[k][s] = INF;
}
cover[0][0] = 0;
for (int k = 0; k < n; k++) {
for (int s = 1; s <= max_sqr; s++) {
for (int m = k, left = INF; m >= 0; m--) { // [m,k]
int prev = (m > 0 ? values[m - 1].j : -1);
left = std::min(left, values[m].i);
cover[k + 1][s] = std::min(
cover[k + 1][s],
cover[m][s - 1] + sqr(values[k].j - left + 1)
- sqr(std::max(prev - left + 1, 0))
);
}
}
}
ll area = INF;
for (int s = 1; s <= max_sqr; s++)
area = std::min(area, cover[n][s]);
return area;
}
