#include "aliens.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100010;
pll a[N], dp[N];
int n;
vector<pair<pll,int>> con;
bool should_remove(pll a, pll b, pll c)
{
return (b.second - a.second) * (a.first - c.first)
<= (c.second - a.second) * (a.first - b.first);
}
void insert_con(pll p, int id)
{
while (con.size() >= 2 && should_remove(p, (con.end()-1)->first,
(con.end()-2)->first))
con.pop_back();
con.push_back({p, id});
}
ll eval(pll p, ll x)
{
return p.first * x + p.second;
}
ll area(ll i, ll j)
{
return i > j? 0: (j-i)*(j-i);
}
pll calc(ll lambda)
{
dp[0] = {0, 0};
con.clear();
insert_con({2*a[0].first, -a[0].first*a[0].first}, 0);
int p = 0;
Loop (i,0,n) {
ll x = a[i].second;
p = min(p, (int)con.size() - 1);
while (p+1 < con.size() && eval(con[p ].first, x)
< eval(con[p+1].first, x))
++p;
int k = con[p].second;
ll val = area(a[k].first, a[i].second)
- (k? area(a[k].first, a[k-1].second): 0)
+ lambda + dp[k].first;
dp[i+1] = {val, dp[k].second+1};
if (i+1 == n)
return dp[n];
insert_con({2*a[i+1].first, - a[i+1].first*a[i+1].first
+ area(a[i+1].first, a[i].second)
- dp[i+1].first},
i+1);
}
return {-1, -1};
}
long long take_photos(int n, int m, int k, std::vector<int> r,
std::vector<int> c)
{
Loop (i,0,n) {
a[i] = {r[i], c[i]};
if (a[i].first > a[i].second)
swap(a[i].first, a[i].second);
a[i].second += 1;
}
sort(a, a+n, [](pll x, pll y){return x.first < y.first
|| (x.first == y.first
&& x.second > y.second);});
for (int i = 0, j = 0; i < n; ++i) {
if (!j || a[j-1].second < a[i].second) {
a[j] = a[i];
++::n;
++j;
}
}
ll bl = 0, br = (ll)m * m;
while (bl < br) {
ll mid = (bl + br)/2;
int cnt = calc(mid).second;
if (cnt > k)
bl = mid+1;
else
br = mid;
}
return calc(bl).first - k*bl;
}
