#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int , long long> pil;
typedef pair<ll , ll> pll;
#define BB dq[dq.size() - 2]
struct Line {
ll cf , b , z;
Line(ll cf_ ,ll b_,ll z_) {
cf = cf_;
b = b_;
z = z_;
}
};
inline pll inter(Line a , Line b) {
return pll(a.b - b.b , b.cf - a.cf);
}
inline bool cmp(pll a , pll b) {
if(a.second < 0) {
a.second *= -1;
a.first *= -1;
}
if(b.second < 0) {
b.second *= -1;
b.first *= -1;
}
return a.first * b.second < a.second * b.first;
}
inline bool cmp(pll a , ll b) {
return cmp(a , pll(b , 1));
}
inline bool equ(pll a , ll b) {
return !cmp(a , pll(b , 1)) && !cmp(pll(b , 1) , a);
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vi ind;
int N = 0;
{
rep(i , 0 , n) {
if (r[i] > c[i]) swap(r[i] , c[i]);
c[i]++;
}
vi local(n);
iota(all(local) , 0);
sort(all(local) , [&](int a , int b) {
if (r[a] != r[b]) return r[a] < r[b];
return c[a] > c[b];
});
int mx = -1;
rep(i , 0 , n)
if (c[local[i]] > mx) {
ind.pb(local[i]);
mx = c[local[i]];
}
N = ind.size();
ind.pb(n);
r[n] = 1e9;
if (k == 1) {
ll dist = c[ind[N - 1]] - r[ind[0]];
return dist * dist;
}
}
auto solve = [&](ll Cost) -> pil {
vector<pil> dp(N + 1);
deque<Line> dq;
dp[N] = pil(0 , 0);
auto push = [&](int id) {
int pos = ind[id];
int pre = ind[id - 1];
ll Rj1 = c[pre];
ll Li = r[pos];
Line ln(Rj1 , dp[id].second + Rj1 * Rj1 - (Li < Rj1 ? (Rj1 - Li) * (Rj1 - Li) : 0) , dp[id].first);
while (dq.size() > 1 && cmp(inter(BB , ln) , inter(BB , dq.back())))
dq.pop_back();
dq.pb(ln);
return;
};
auto relax = [&](int id) {
ll pn = -2ll * r[ind[id]];
while (dq.size() > 1) {
if (cmp(inter(dq[0] , dq[1]) , pn)) {
dq.pop_front();
}
else if (equ(inter(dq[0] , dq[1]) , pn)) {
if (dq[0].z < dq[1].z) swap(dq[0] , dq[1]);
dq.pop_front();
}
else
break;
}
return;
};
for(int i = N - 1 ; ~i; i--) {
push(i + 1);
relax(i);
int me = ind[i];
dp[i] = pil(dq[0].z + 1, (1ll * r[me] * r[me]) - 2ll * r[me] * dq[0].cf + dq[0].b + Cost);
// cout << i << ' ' << dp[i].first << ' '<< dp[i].second << endl;
}
return dp[0];
};
ll lo = 1ll * m * m + 10, hi = -1;
while (lo - 1 != hi) {
ll mid = lo + hi >> 1;
if (k < solve(mid).first)
hi = mid;
else
lo = mid;
}
auto result = solve(lo);
return result.second - k * lo;
}
