#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
bool cmp(const pair<long long, long long>& a, const pair<long long, long long>& b) {
if (a.first != b.first) {
return a.first < b.first;
}
return a.second > b.second;
}
long long divide_up(long long a, long long b) {
if (b < 0) {
a = -a;
b = -b;
}
if (a >= 0) {
return (a + b - 1) / b;
}
return a / b;
}
long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> points_x, vector<int32_t> points_y) {
vector<pair<long long, long long>> segs(n);
for (long long i = 0; i < n; i++) {
segs[i] = {min(points_x[i], points_y[i]), max(points_x[i], points_y[i])};
}
sort(segs.begin(), segs.end(), cmp);
vector<pair<long long, long long>> new_segs;
new_segs.push_back({-1, -1});
long long largest_r = -2e18;
for (auto [l, r]: segs) {
if (r <= largest_r) {
continue;
}
largest_r = r;
new_segs.push_back({l, r});
}
segs = new_segs;
n = segs.size();
new_segs.clear();
vector<vector<long long>> a(k + 1, vector<long long>(n));
vector<long long> b(n);
for (long long i = 0; i < n - 1; i++) {
b[i] = -2 * segs[i + 1].first;
}
vector<vector<long long>> dp(k + 1, vector<long long>(n, 2e18));
auto count_a = [&](long long j, long long i) {
if (i == n - 1) {
return;
}
a[j][i] = dp[j][i] + (segs[i + 1].first - 1) * (segs[i + 1].first - 1)
- max(0ll, segs[i].second - segs[i + 1].first + 1) *
max(0ll, segs[i].second - segs[i + 1].first + 1);
};
vector<vector<pair<long long, long long>>> ch(k + 1);
vector<long long> last(k + 1);
dp[0][0] = 0;
count_a(0, 0);
ch[0].push_back({-1, 0});
for (long long i = 1; i < n; i++) {
for (long long j = 1; j <= i && j <= k; j++) {
// dp[j][i]
long long x = segs[i].second;
while (last[j - 1] + 1 < ch[j - 1].size() && ch[j - 1][last[j - 1] + 1].first <= x) {
last[j - 1]++;
}
long long from = ch[j - 1][last[j - 1]].second;
dp[j][i] = segs[i].second * segs[i].second + 2 * segs[i].second + a[j - 1][from] + b[from] * x;
//cerr << x << ' ' << from << endl;
//cerr << segs[i].second * segs[i].second - 2 * segs[i].second << ' ' << a[j - 1][from] << ' ' << << endl;
count_a(j, i);
if (i == n - 1) {
continue;
}
if (ch[j].empty()) {
ch[j].push_back({-1, i});
continue;
}
while (true) {
x = ch[j].back().first;
long long ind = ch[j].back().second;
if (a[j][ind] + b[ind] * x < a[j][i] + b[i] * x) {
break;
}
ch[j].pop_back();
}
long long ind = ch[j].back().second;
x = divide_up(a[j][i] - a[j][ind], b[ind] - b[i]);
ch[j].push_back({x, i});
last[j] = min(last[j], (long long)(ch[j].size() - 1));
}
}
long long ans = 2e18;
for (long long j = 1; j <= k; j++) {
ans = min(ans, dp[j][n - 1]);
}
return ans;
}
