#include "aliens.h"
#include <bits/stdc++.h>
#define NO_DEBUG
using namespace std;
using lint = long long;
const lint INF = 1e15;
struct Segment {
lint left, right;
Segment(lint l = 0, lint r = 0): left(l), right(r) {}
bool operator < (const Segment &o) const {
return left < o.left || (left == o.left && right > o.right);
}
bool operator == (const Segment &o) const {
return left == o.left && right == o.right;
}
};
struct ConvexHull { // Convex Hull Trick
struct Line {
lint m, c;
int id;
Line(lint M = 0, lint C = INF, int id_ = -1): m(M), c(C), id(id_) {}
lint get(lint x) {
return m * x + c;
}
};
vector<Line> hull = {Line(0, INF)};
int ptr = 0;
void insert(lint m, lint c) {
hull.emplace_back(Line(m, c));
int sz = hull.size() - 1;
/* y = m1x + c1 = m2x + c2
(m1 - m2)x = (c2 - c1)
x = (c2 - c1) / (m1 - m2)
(c2 - c1) / (m1 - m2) < (c3 - c2) / (m2 - m3)
*/
while (ptr <= sz - 2 && (hull[sz - 1].c - hull[sz].c) * (hull[sz - 1].m - hull[sz - 2].m) <
(hull[sz - 2].c - hull[sz - 1].c) * (hull[sz].m - hull[sz - 1].m))
hull[sz - 1] = hull[sz], sz--, hull.pop_back();
}
lint query(lint x) {
while (ptr + 1 < hull.size() && hull[ptr].get(x) > hull[ptr + 1].get(x))
ptr++;
return hull[ptr].get(x) + x * x;
}
};
int N, K;
vector<Segment> segment;
vector<vector<lint>> DP;
vector<ConvexHull> hull;
void preprocess(int n, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; i++)
segment.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
sort(segment.begin(), segment.end());
vector<Segment> tmp;
tmp.emplace_back(-1, -1);
for (auto s : segment) {
Segment overlap = Segment(min(tmp.back().left, s.left), max(tmp.back().right, s.right));
if (overlap == s) swap(s, tmp.back());
if (overlap == tmp.back()) continue;
tmp.emplace_back(s);
}
segment = tmp, N = segment.size() - 1, K = k;
DP.assign(N + 1, vector<lint>(K + 1, INF));
hull.resize(K + 1);
}
lint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
preprocess(n, k, r, c);
for (int k = 0; k <= K; k++)
DP[0][k] = 0;
for (int k = 1; k <= K; k++) {
for (int n = 1; n <= N; n++) {
lint m = - 2 * segment[n].left;
lint c = + segment[n].left * segment[n].left
- max(0ll, segment[n - 1].right - segment[n].left + 1) *
max(0ll, segment[n - 1].right - segment[n].left + 1)
+ DP[n - 1][k - 1];
hull[k].insert(m, c);
DP[n][k] = min(DP[n][k], hull[k].query(segment[n].right + 1));
}
}
#ifndef NO_DEBUG
for (int i = 0; i <= K; i++) {
cout << "K = " << i << ": ";
for (int j = 0; j <= N; j++) {
cout << DP[j][i] << " ";
}
cout << "\n";
}
#endif
return DP[N][K];
}
