#pragma GCC optimize ("Ofast,__attribute__((always_inline))")
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define fi first
#define se second
// Create a struct for linear functions
// First argument: slope, second argument: y-intercept
struct Line {
int m;
ll b;
int b2;
inline pair<ll, int> evaluate(ll x) const {
return {m * x + b, b2};
}
};
/*
Maintain the minimum line in the li chao tree
*/
class Tree {
public:
Tree *lt, *rt;
int l, r;
Line v;
Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v({0, INF(ll), INF(int)}) {}
void build() {
if(l == r || (lt != nullptr)) {
return;
}
int m = (l + r) >> 1;
lt = new Tree(l, m);
rt = new Tree(m + 1, r);
}
void insert_line(Line nl) {
build();
int m = (l + r) >> 1;
bool less_l = nl.evaluate(l) < v.evaluate(l);
bool less_m = nl.evaluate(m + 1) < v.evaluate(m + 1);
/*
! TODO why does swap work
! and v = nl does not???
well, if we do v = nl,
we simply erase v from existence
we don't want that---we want to consider both
so nl is considered now
therefore we instead propagate v downward
*/
if(less_m) swap(v, nl);
if(l != r) {
(less_l == less_m ? rt: lt)->insert_line(nl);
}
}
pair<ll, int> evaluate(int x) {
build();
if(l == r) {
return v.evaluate(x);
}
return min((x <= ((l + r) >> 1) ? lt : rt)->evaluate(x), v.evaluate(x));
}
~Tree() {
if(lt != nullptr) {
delete lt;
delete rt;
}
}
};
/*
Suppose the penalty for using another picture is +y
*/
pll solve_lambda_brute(const vpll& pts, ll m, ll y) {
ll np = pts.size();
// note: stores NEGATIVE area, num pictures
// then, the DP just gets the maximum state
vector<pair<ll, int>> dp(np, {0ll, 0});
Tree * tr = new Tree(0ll, m - 1ll);
tr->build();
for(ll i = 0ll; i < np; i++) {
ll cl = pts[i].fi, cr = pts[i].se;
if(i == 0ll) {
tr->insert_line({- ((int)(pts[i].fi) << 1), y + pts[i].fi * pts[i].fi, -1});
} else {
ll overlap = max(pts[i - 1ll].se - pts[i].fi + 1ll, 0ll);
tr->insert_line({- ((int)(pts[i].fi) << 1), dp[i - 1ll].fi - overlap * overlap + y + pts[i].fi * pts[i].fi, dp[i - 1ll].se - 1});
}
pair<ll, int> opt = tr->evaluate(cr + 1ll);
dp[i] = {opt.fi + (cr + 1ll) * (cr + 1ll), opt.se};
// cerr << y << " " << i << " " << dp[i].fi << " " << -dp[i].se << endl;
}
delete tr;
return dp[np - 1ll];
}
ll take_photos(int i_n, int i_m, int i_k, vi r, vi c) {
ll n = i_n, m = i_m, k = i_k;
// first, we preprocess. remove all redundant points
vpll pts;
for(ll i = 0ll; i < n; i++) {
if(r[i] > c[i]) swap(r[i], c[i]);
pts.push_back({r[i], c[i]});
}
sort(pts.begin(), pts.end(), [](pll p1, pll p2){return p1.fi < p2.fi || (p1.fi == p2.fi && p1.se > p2.se);});
ll max_r = -1ll;
vpll filt_pts;
for(ll i = 0ll; i < n; i++) {
ll cl = pts[i].fi, cr = pts[i].se;
if(cr > max_r) {
filt_pts.push_back(pts[i]);
// cerr << cl << " " << cr << endl;
max_r = cr;
}
}
// Performing lagrangian relaxation
ll lo = 0ll, hi = 1e11;
while(hi - lo > 1ll) {
ll mid = (lo + hi) >> 1ll;
pll cpair = solve_lambda_brute(filt_pts, m, mid);
ll c_k = -cpair.se;
if(c_k >= k) lo = mid;
else hi = mid;
}
return solve_lambda_brute(filt_pts, m, lo).fi - k * lo;
}
