#include <bits/stdc++.h>
#include "aliens.h"
#define ll long long
using namespace std;
constexpr static ll INF = 1e15;
vector<array<int, 2>> get_cells(const vector<int>& r, const vector<int>& c) {
const int n = r.size();
vector<array<int, 2>> cells;
for (int i = 0; i < n; i++) {
cells.push_back({min(r[i], c[i]), -max(r[i], c[i])});
}
sort(cells.begin(), cells.end());
vector<array<int, 2>> final_cells;
int lastc = -1;
for (auto [r, c] : cells) {
if (-c <= lastc)
continue;
lastc = -c;
final_cells.push_back({r, -c});
}
return final_cells;
}
ll calculate_cost(array<ll, 2> line, ll c) {
return line[0] + line[1] * c + c * c;
}
ll calculate_cost(array<ll, 3> line, ll c, ll lambda) {
return line[0] + line[1] * c + c * c + lambda;
}
bool beating_intercept(const deque<array<ll, 3>>& d, ll y2, ll s2) {
if (d.size() == 0) return false;
if (y2 < d[0][0]) return true;
if (d.size() == 1) return false;
auto [ y1, s1, _ ] = d.back();
auto [ y0, s0, __ ] = d[d.size()-2];
assert(y0 <= y1 && y1 <= y2);
assert(s2 <= s1 && s1 <= s0);
return (y1 - y2) * (s1 - s0) <= (y0 - y1) * (s2 - s1);
}
array<ll, 2> get_count_val(const std::vector<array<int, 2>>& cells, ll lambda) {
const int n = cells.size();
deque<array<ll, 3>> dp; // (Initial point, slope, number of attempts)
ll initial_y_intercept = static_cast<ll>(cells[0][0] - 1) * (cells[0][0] - 1);
ll initial_slope = - 2 * (cells[0][0] - 1);
dp.push_back({initial_y_intercept, initial_slope, 0});
for (int i = 1; i <= n; i++) {
int c = cells[i-1][1];
while (dp.size() > 1 && calculate_cost(dp[0], c, lambda) > calculate_cost(dp[1], c, lambda)) dp.pop_front();
ll cost = calculate_cost(dp[0], c, lambda);
int steps = dp[0][2] + 1;
if (i < n) {
ll y_intercept = cost + static_cast<ll>(cells[i][0] - 1) * (cells[i][0] - 1) - max<ll>(0, c - cells[i][0] + 1) * max<ll>(0, c - cells[i][0] + 1);
ll slope = -2 * (cells[i][0] - 1);
while (beating_intercept(dp, y_intercept, slope)) dp.pop_back();
dp.push_back({y_intercept, slope, steps});
}
else {
return { cost - lambda * steps, steps };
}
}
assert(false);
}
long long take_photos(int n, int m, int k, std::vector<int> rows, std::vector<int> columns) {
assert(n*k <= 1e8);
vector<array<int, 2>> cells = get_cells(rows, columns);
ll l = -1, r = static_cast<ll>(m) * m;
while (r - l > 1) {
int m = (r+l) / 2;
if (get_count_val(cells, m)[1] < k)
r = m;
else
l = m;
}
return get_count_val(cells, l)[0];
}
