/**
* @file uoj240-1.cpp
* @author n685
* @brief
* @date 2023-10-07
*
*
*/
#include <bits/stdc++.h>
#include "aliens.h"
#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr \
if (false) \
std::cerr
#endif
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif
using db = long double; // change it to double as needed
const db PI = std::acos(static_cast<db>(-1.0));
// constexpr db PI = std::numbers::pi_v<db>;
constexpr db EPS = 1e-9;
template <class T, class U> constexpr bool eq(const T &a, const U &b) {
if constexpr (std::is_floating_point<
typename std::common_type<T, U>::type>::value) {
return (std::abs(a - b) < EPS);
} else {
return (a == b);
}
}
struct I {
int64_t l = 0, r = 0;
bool operator<(const I &i) const {
return (l == i.l) ? (r > i.r) : (l < i.l);
}
bool contains(const I &i) const { return l <= i.l && i.r <= r; }
};
struct L {
db m, b;
int ind;
auto eval(db x) const { return m * x + b; }
db isect(const L &l) const { return (b - l.b) / (l.m - m); }
};
long long take_photos(int n, int m, int k, std::vector<int> r,
std::vector<int> c) {
std::vector<I> vv(n);
for (int i = 0; i < n; ++i) {
vv[i] = {std::min(r[i], c[i]), std::max(r[i], c[i])};
}
std::sort(vv.begin(), vv.end());
std::vector<I> v;
v.push_back(vv[0]);
for (int i = 1; i < n; ++i) {
if (!v.back().contains(vv[i])) {
v.push_back(vv[i]);
}
}
n = (int)v.size();
std::vector<db> dp;
std::vector<int> cnt, ind;
auto good = [&](db cc) -> bool {
dp.assign(n + 1, 0);
cnt.assign(n + 1, 0);
ind.assign(n + 1, 0);
std::deque<L> dq = {
L{(db)-2 * (v[0].l - 1), dp[0] + (v[0].l - 1) * (v[0].l - 1) + cc, 0}};
auto ins = [&](const L &l) {
while ((int)dq.size() >= 2) {
if (eq(l.m, dq.back().m)) {
if (l.b < dq.back().b) {
dq.pop_back();
} else if (eq(l.b, dq.back().b) && cnt[l.ind] < cnt[dq.back().ind]) {
dq.pop_back();
} else {
return;
}
} else {
// std::pair<int64_t, int64_t> ins1 = dq.end()[-2].isect(dq.back()),
// ins2 = dq.back().isect(l);
// if (ins1.first * ins2.second >= ins2.first * ins1.second) {
if (dq.end()[-2].isect(dq.back()) >= dq.back().isect(l)) {
dq.pop_back();
} else {
break;
}
}
}
dq.push_back(l);
};
auto insFront = [&](const L &l) {
while ((int)dq.size() >= 2) {
if (eq(l.m, dq[0].m)) {
if (l.b < dq[0].b) {
dq.pop_front();
} else if (eq(l.b, dq[0].b) && cnt[l.ind] < cnt[dq[0].ind]) {
dq.pop_front();
} else {
return;
}
} else {
// std::pair<int64_t, int64_t> ins1 = dq.end()[-2].isect(dq.back()),
// ins2 = dq.back().isect(l);
// if (ins1.first * ins2.second >= ins2.first * ins1.second) {
if (dq[1].isect(dq[0]) <= dq[0].isect(l)) {
dq.pop_front();
} else {
break;
}
}
}
dq.push_front(l);
};
auto query = [&](auto x) {
while ((int)dq.size() > 1) {
if (dq[0].eval(x) >= dq[1].eval(x)) {
dq.pop_front();
} else {
break;
}
}
};
for (int i = 1; i <= n; ++i) {
query(v[i - 1].r);
dp[i] = dq[0].eval(v[i - 1].r) + v[i - 1].r * v[i - 1].r;
cnt[i] = cnt[dq[0].ind] + 1;
ind[i] = dq[0].ind;
if (dp[i] < 0) {
// continue;
}
if (i < n) {
ins(L{(db)-2 * (v[i].l - 1),
dp[i] + (v[i].l - 1) * (v[i].l - 1) -
std::max<db>(0, v[i - 1].r - v[i].l + 1) *
std::max<db>(0, v[i - 1].r - v[i].l + 1) +
cc,
i});
}
}
return (cnt[n] <= k);
};
db ll = 0, rr = (db)m * m;
while (std::abs(rr - ll) >= 1e-15) {
db mid = (ll + rr) / 2;
if (good(mid)) {
rr = mid;
} else {
ll = mid;
}
}
// cerr << std::fixed << std::setprecision(20);
// dbg(rr);
// dbg(dp[n] - rr * cnt[n]);
good(rr);
assert(cnt[n] <= k);
return (long long)std::round(dp[n] - rr * cnt[n]);
}
