#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
struct parabola {
ll b, c;
ll k;
parabola(ll origin, ll b, ll c, ll k) {
this->b = 2 * (-origin) + b;
this->c = origin * origin + b * (-origin) + c;
this->k = k;
}
ll eval(ll x) {
return x * x + b * x + c;
}
static ll intersect(parabola &s, parabola &t) {
// Line root x2
ll a = s.b - t.b;
ll b = s.c - t.c;
return a == 0 ? -1 : (-b) / a;
}
};
ll n, m;
vector<pair<ll, ll>> p;
deque<pair<ll, parabola>> deq; // obsolete from x, parab
pair<ll, ll> solve(ll pen) {
deq.clear();
vector<ll> dp(n);
vector<ll> dpK(n);
dp[0] = (p[0].first + p[0].second + 2 - m) *
(p[0].first + p[0].second + 2 - m) + pen;
dpK[0] = 1;
deq.push_back({m, parabola(p[0].first, 2*abs(p[0].first+p[0].second+2-m), dp[0], dpK[0])});
for (int i = 1; i < n; i++) {
while (deq.front().first <= p[i].first) deq.pop_front();
ll val = deq.front().second.eval(p[i].first);
ll k = deq.front().second.k;
ll nwVal = (p[i].first + p[i].second + 2 - m) *
(p[i].first + p[i].second + 2 - m) + dp[i-1] + pen;
ll subSide = (p[i-1].first + p[i].second + 2 - m);
ll nwK = dp[i-1] + 1;
if (subSide > 0) nwVal -= subSide * subSide;
if (nwVal < val || (nwVal <= val && nwK <= k)) {
val = nwVal;
k = nwK;
deq.clear();
}
dp[i] = val;
dpK[i] = k;
parabola parab(p[i].first, 2*abs(p[i].first+p[i].second+2-m), nwVal, nwK);
if (deq.empty()) {
deq.push_back({m, parab});
continue;
}
if (parab.eval(m) >= deq.back().second.eval(m)) continue;
ll validFrom = 2 * (deq.size() < 2 ? 0 : deq[deq.size()-2].first);
ll eval = parab.eval(validFrom);
ll evalPrev = deq.back().second.eval(validFrom);
bool disc = eval < evalPrev || (eval <= evalPrev && nwK <= deq.back().second.k);
while (disc) {
deq.pop_back();
if (deq.empty()) break;
validFrom = 2 * (deq.size() < 2 ? 0 : deq[deq.size()-2].first);
eval = parab.eval(validFrom);
evalPrev = deq.back().second.eval(validFrom);
disc = eval < evalPrev || (eval <= evalPrev && nwK <= deq.back().second.k);
}
if (!deq.empty()) {
ll x = parabola::intersect(parab, deq.back().second);
eval = parab.eval(x);
evalPrev = deq.back().second.eval(x);
if (eval < evalPrev || (eval <= evalPrev && nwK <= deq.back().second.k)) {
if (x >= m) continue;
deq.back().first = x;
}
else {
if (x+1 >= m) continue;
deq.back().first = x+1;
}
}
deq.push_back({m, parab});
}
return {dpK[n-1], dp[n-1]};
}
ll take_photos(int n1, int m1, int k, vector<int> r, vector<int> c) {
// Sort and filter
n = n1; m = m1;
vector<pair<ll, ll>> prs(n);
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) prs[i] = {r[i], m-1-c[i]};
else prs[i] = {c[i], m-1-r[i]};
}
sort(prs.begin(), prs.end());
p.clear();
for (auto &e : prs) {
while (!p.empty() && p.back().second <= e.second) p.pop_back();
p.push_back(e);
}
n = p.size();
// Solve
ll left = 0, right = 2 * ((m+1)/2) * ((m+1)/2);
while (left < right) {
ll mid = (left + right) / 2;
pair<ll, ll> val = solve(mid);
if (val.first > k) {
left = mid + 1;
}
else {
right = mid;
}
}
pair<ll, ll> res = solve(left);
return res.second - k*left;
}
