#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, 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) {
vector<array<int, 2>> cells = get_cells(rows, columns);
ll l = 0, r = 1e12;
while (r - l > 1) {
ll m = (r+l) / 2;
//cout << l << " " << r << " " << m << " " << get_count_val(cells, m)[0] << " " << get_count_val(cells, m)[1] << "\n";
if (get_count_val(cells, m)[1] < static_cast<ll>(k))
r = m;
else
l = m;
}
auto [ lc, ls ] = get_count_val(cells, l);
auto [ rc, rs ] = get_count_val(cells, r);
if (rs == ls)
return lc;
ll res = (rc - lc) * (k - ls) / (rs - ls) + lc;
//cout << steps << "\n";
assert(ls >= k && k >= rs);
return res;
}
