#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const long long INF = 0x3FFFFFFFFFFFFFFFLL;
long long squared(int x) {
return 1ll * x * x;
}
long long cross_x(pair<long long, long long> X, pair<long long, long long> Y) {
/* Returns the first x >= to when the lines intersect */
long long db = X.first - Y.first;
long long dc = Y.second - X.second;
if (db == 0) {
return db < 0 ? -INF : INF;
}
if (db < 0) {
db = -db;
dc = -dc;
}
if (dc < 0) {
return dc / db;
}
return (dc + db - 1) / db;
}
struct dumb_hull {
bool insert(long long a, long long b) {
lns.push_back(make_pair(a, b));
return true;
}
long long get(long long x) const {
long long res = -INF;
for (auto ln : lns) {
res = max(res, ln.first * x + ln.second);
}
return res;
}
vector<pair<long long, long long> > lns;
};
struct line_hull {
/* Implements a max hull, get the max ax+b for all inserted lines. */
bool insert(long long a, long long b) {
/* Insert line ax+b */
// cout << "INSERT " << a << ", " << b << endl;
auto ln = make_pair(a, b);
auto it = st.lower_bound(ln);
bool is_last = it == st.end();
if (!is_last && ln.first == it->first) {
return false;
}
auto jt = it;
bool is_first = it == st.begin();
if (!is_first) {
--it;
if (it->first == ln.first) {
if (it == st.begin()) {
is_first = true;
} else {
--it;
}
}
}
long long lft_x = is_first ? -INF : cross_x(*it, ln);
long long rht_x = is_last ? INF : cross_x(ln, *jt);
if (rht_x <= lft_x) {
return false;
}
if (!is_first) {
while (it != st.begin()) {
auto kt = it--;
long long prev_lft_x = cross_x(*it, *kt);
if (prev_lft_x < lft_x) {
++it;
break;
}
lft_x = cross_x(*it, ln);
}
++it;
}
if (!is_last) {
while (true) {
auto kt = jt++;
if (jt == st.end()) {
break;
}
long long prev_rht_x = cross_x(*kt, *jt);
if (rht_x < prev_rht_x) {
break;
}
rht_x = prev_rht_x;
}
--jt;
}
crs.erase(
crs.lower_bound(make_pair(lft_x + (is_first ? -1 : 0), make_pair(INF, INF))),
crs.lower_bound(make_pair(rht_x, make_pair(INF, INF)))
);
crs.insert(make_pair(lft_x, ln));
if (!is_last) {
crs.insert(make_pair(rht_x, *jt));
}
st.erase(it, jt);
st.insert(ln);
// cout << st.size() << ", " << crs.size() << endl;
return true;
}
long long get(long long x) const {
auto it = crs.lower_bound(make_pair(x, make_pair(-INF, -INF)));
--it;
return it->second.first * x + it->second.second;
}
set<pair<long long, long long> > st;
set<pair<long long, pair<long long, long long> > > crs;
};
long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
vector<pair<int, int> > A;
for (int i = 0; i < N; i++) {
int ri = R[i];
int ci = C[i];
if (ri > ci) swap(ri, ci);
A.push_back(make_pair(ci, ci - ri));
}
sort(A.begin(), A.end());
int j = 0;
for (auto p : A) {
while (j > 0 && p.second >= A[j - 1].second + p.first - A[j - 1].first) {
--j;
}
A[j++] = p;
}
A.resize(j);
N = j;
vector<long long> ADJ(N + 1, 0);
for (int i = 1; i < N; i++) {
ADJ[i] = squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first));
}
long long INF = squared(M + 1);
vector<long long> DP(N + 1, INF);
vector<long long> DP2(N + 1, INF);
DP[0] = 0;
for (int k = 0; k < K; k++) {
line_hull hl;
//dumb_hull hl;
for (int i = 0; i <= N; i++) {
if (i) {
long long x = A[i - 1].first;
DP[i] = -hl.get(x) + squared(x);
}
/*
for (int j = 0; j < i; j++) {
DP[i] = min(
DP[i],
DP[j] + squared(1 + A[j].second + A[i - 1].first - A[j].first) - ADJ[j]
);
}
*/
// x^2 + bx + c where x = A[i - 1].first
long long sadd = 1 + A[i].second - A[i].first;
long long b = 2 * sadd;
long long c = squared(sadd) + DP[i] - ADJ[i];
hl.insert(-b, -c);
}
DP.swap(DP2);
}
return DP[N];
}
