#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define fi first
#define se second
#define mp make_pair
const ld inf = (ld)1e18;
struct line{
ll ai;
ll bi;
int cn;
ld lim;
};
vector<line> hull;
ld inter(line aa, line bb){
return (ld)(aa.bi - bb.bi) / (ld)(bb.ai - aa.ai);
}
void put_line(ll aa, ll bb, int c){
aa=-aa;
bb=-bb; // assume a is increasing
line nw = {aa, bb, c, inf};
line l1, l2;
while(hull.size() >= 2){
l1 = hull[hull.size() - 2];
l2 = hull[hull.size() - 1];
if(inter(l1, l2) >= inter(l2, nw)) {
hull.pop_back();
}
else{
break;
}
}
if(!hull.empty()) hull.back().lim=inter(hull.back(), nw);
hull.push_back(nw);
}
pair<ll, int> query(ll xi){
int l = 0;
int r = (int)hull.size() - 1;
int mid;
while(l < r){
mid = (l + r) / 2;
if(hull[mid].lim < xi){
l=mid + 1;
}
else{
r=mid;
}
}
return mp(-xi * 1ll * hull[l].ai - hull[l].bi, hull[l].cn);
}
const int N = (int)1e5 + 10;
vector<pii> T;
ll dp[N];
int cnt[N];
ll sq(ll x){
return x * 1ll * x;
}
void compute(int n, int k, ll penalty){
dp[0]=cnt[0]=0;
hull.clear();
for(int i = 1; i < n; i ++ ){
dp[i]=inf;
}
ll B;
pair<ll, int> ndp;
for(int i = 1 ; i < n; i ++ ){
B = sq(max(T[i - 1].se - T[i].fi, 0));
put_line(-2ll * T[i].fi, sq(T[i].fi) + dp[i - 1] - B, cnt[i - 1]);
ndp = query(T[i].se);
ndp.fi += sq(T[i].se) + penalty;
ndp.se ++ ;
dp[i] = ndp.fi;
cnt[i] = ndp.se;
}
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pii> segt;
for(int i = 0 ; i < n ; i ++ ){
segt.push_back(mp(min(r[i], c[i]), max(r[i],c[i])));
}
sort(segt.begin(), segt.end(), [&](pii i, pii j){
if(i.fi == j.fi){
return i.se > j.se;
}
else{
return i.fi < j.fi;
}
});
T.push_back(mp(-1,-1));
for(auto x : segt){
if(x.se > T.back().se){
T.push_back(x);
}
}
n=T.size();
for(int i = 1; i < n; i ++ ) T[i].fi -- ;
k=min(k,n-1);
ll lf = 0ll, rf = m * 1ll * m + 100;
ll mid;
while(lf < rf){
mid = (lf + rf) / 2;
compute(n, k, mid);
if(cnt[n - 1] <= k){
rf=mid;
}
else{
lf=mid+1;
}
}
compute(n, k, lf);
return dp[n-1] - k * 1ll * lf;
}
