#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/contests/ioi16d2/debug.h"
#else
#define debug(...) void(37)
#endif
typedef __int128_t int128_t;
struct LineContainer {
using E = array<int64_t, 3>;
deque<E> d;
array<int64_t, 2> pass(E x, E y) {
return {y[1] - x[1], x[0] - y[0]}; //It might be already bigger
}
void add(int64_t m, int64_t c, int info) {
E add;
add[0] = m, add[1] = c, add[2] = info;
while (int(d.size()) > 1) {
array<int64_t, 2> isect0 = pass(add, d.back());
array<int64_t, 2> isect1 = pass(d.back(), d.end()[-2]);
if (int128_t(isect0[0] * isect1[1]) < int128_t(isect1[0] * isect0[1])) {
d.pop_back();
} else {
break;
}
}
d.push_back(add);
debug(add, d);
}
int64_t eval_eq(int64_t m, int64_t c, int64_t x) {
return m * x + c;
}
int64_t eval_element(E e, int64_t x) {
return eval_eq(e[0], e[1], x);
}
pair<int64_t, int> eval(int64_t x) {
assert(!d.empty());
while (int(d.size()) > 1 && eval_element(d[0], x) > eval_element(d[1], x)) {
d.pop_front();
}
debug(x, d);
return {eval_element(d.front(), x), d.front()[2]};
}
};
int64_t S(int x) {
return int64_t(x) * x;
}
long long take_photos(int N, int M, int K, std::vector<int> R_, std::vector<int> C) {
vector<array<int, 2>> ranges;
for (int i = 0; i < N; ++i) {
if (R_[i] - C[i] > 0) {
ranges.push_back({C[i], R_[i] + 1});
} else {
ranges.push_back({R_[i], C[i] + 1});
}
}
sort(ranges.begin(), ranges.end(), [&](auto x, auto y) {
return array<int, 2>{x[0], -x[1]} < array<int, 2>{y[0], -y[1]};
});
vector<int> L, R;
int mx_r = -1;
for (auto[l, r] : ranges) {
if (mx_r < r) {
mx_r = r;
L.push_back(l);
R.push_back(r);
}
}
debug(N, L, R);
N = int(L.size());
K = min(K, N);
//cost = best[i][j] + S(R[n] - L[i]) - (n + 1 < N && R[n] > L[n + 1] ? S(R[n] - L[n + 1]) : 0);
auto Get = [&](int64_t penalty) {
debug(penalty);
LineContainer lc;
vector<pair<int64_t, int>> ans(N);
lc.add(-2 * L[0], S(L[0]), 0);
for (int i = 0; i < N; ++i) {
ans[i] = lc.eval(R[i]);
ans[i].first += + S(R[i]) - (i + 1 < N && R[i] > L[i + 1] ? S(R[i] - L[i + 1]) : 0) + penalty;
ans[i].second++;
debug(ans[i]);
if (i < N - 1) {
lc.add(-2 * L[i + 1], ans[i].first + S(L[i + 1]), ans[i].second);
}
}
debug(ans);
return ans[N - 1];
};
int64_t low = 0, high = int64_t(M) * M;
while (low < high) {
int64_t mid = (low + high) >> 1;
if (Get(mid).second > K) {
low = mid + 1;
} else {
high = mid;
}
}
auto[r, k] = Get(low);
debug(low, r, k);
r -= 1LL * low * K;
return r;
}
