#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
struct Line {
mutable long long k, m, p, c; // slope, y-intercept, last optimal x, photo_count
};
struct LineContainer {
deque<Line> lines;
const long long inf = LLONG_MAX;
long long div(long long a, long long b) { // floored division
if (b < 0) a *= -1, b *= -1;
if (a >= 0) return a / b;
return -((-a + b - 1) / b);
}
long long isect(const Line& x, const Line& y) {
if (x.k == y.k && x.m > y.m)
return inf;
assert(x.k < y.k);
return div(y.m - x.m, x.k - y.k);
}
void add(long long k, long long m, int photo_count) {
assert(lines.empty() || photo_count >= lines.back().c);
if (!lines.empty() && lines.back().k == k && lines.back().m >= m) return;
Line line{k, m, inf, photo_count};
while (lines.size() > 1 && (isect(lines.back(), line) < isect(lines[lines.size()-2], lines.back())))
lines.pop_back();
lines.push_back(line);
if (lines.size() >= 2) {
lines[lines.size()-2].p = isect(lines[lines.size()-2], lines.back());
}
}
pair<long long, int> query(long long x) {
assert(!lines.empty());
while (x > lines[0].p) lines.pop_front();
assert(!lines.empty());
return {lines[0].k * x + lines[0].m, lines[0].c};
}
};
vector<array<int, 2>> extract_relevant_sorted_points(const vector<int>& r, const vector<int>& c);
pair<long long, int> optimal_solution(int n, int m, long long C, const vector<array<int, 2>>& pos);
long long take_photos(int n, int m, int k, vector<int> _r, vector<int> _c) {
vector<array<int, 2>> pos = extract_relevant_sorted_points(_r, _c);
n = pos.size();
k = min(k, n);
long long l = 0, r = static_cast<long long>(m) * m;
while (r - l > 1) {
long long C = (l+r) / 2;
auto [value, photo_count] = optimal_solution(n, m, C, pos);
if (photo_count > k)
l = C;
else
r = C;
}
auto [value, photo_count] = optimal_solution(n, m, r, pos);
return value - k * r;
}
pair<long long, int> optimal_solution(int n, int m, long long C, const vector<array<int, 2>>& pos) {
LineContainer lines;
lines.add(-2 * static_cast<long long>(1 - pos[0][0]), -static_cast<long long>(1 - pos[0][0]) * (1 - pos[0][0]), 0);
for (int i = 1; i <= n; i++) {
auto [line_value, prev_photo_count] = lines.query(pos[i-1][1]);
long long dp_value = C + static_cast<long long>(pos[i-1][1]) * pos[i-1][1] - line_value;
if (i == n) {
return {dp_value, prev_photo_count + 1};
}
long long overlap_side_length = max<long long>(0, pos[i-1][1] - pos[i][0] + 1);
long long overlap_area = overlap_side_length * overlap_side_length;
long long slope = - 2 * static_cast<long long>(1 - pos[i][0]);
long long intercept = - (dp_value - overlap_area + static_cast<long long>(1 - pos[i][0]) * (1 - pos[i][0]));
lines.add(slope, intercept, prev_photo_count + 1);
}
assert(false);
}
vector<array<int, 2>> extract_relevant_sorted_points(const vector<int>& r, const vector<int>& c) {
const int n = r.size();
vector<array<int, 2>> sorted_points;
for (int i = 0; i < n; i++) {
sorted_points.push_back({max(r[i], c[i]), min(r[i], c[i])});
}
sort(sorted_points.begin(), sorted_points.end());
for (int i = 0; i < n; i++) {
sorted_points[i] = { sorted_points[i][1], sorted_points[i][0] };
}
vector<array<int, 2>> stack;
for (const auto [r, c] : sorted_points) {
if (!stack.empty() && stack.back()[1] == c) {
continue; // Our point is smalong longer
}
while (!stack.empty() && stack.back()[0] >= r) stack.pop_back();
stack.push_back({r, c});
}
return stack;
}
