#include "aliens.h"
//#include "grader.cpp"
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5e4 + 5;
struct Point
{
int r, c;
Point(){}
Point(int r, int c)
{
this->r = r;
this->c = c;
}
};
bool cmpCol(Point A, Point B)
{
if(A.c!=B.c) return A.c<B.c;
return A.r>B.r;
}
int n, m, k;
vector <int> opt[MAXN];
vector <long long> dp[MAXN];
vector <Point> v;
void init()
{
for(int i = 0;i<n;i++)
{
opt[i].assign(k+5, 0);
dp[i].assign(k+5, 69696969969699LL);
}
vector <Point> newV;
for(Point p: v)
{
int d = p.c - p.r + 1;
while(newV.empty()==false && p.c-newV.back().c<d && abs(p.c-newV.back().r)<d) newV.pop_back();
newV.push_back(p);
}
v = newV;
n = v.size();
}
long long squareNum(long long x)
{
if(x<0) return 0;
return x*x;
}
int getSquareSz(int l, int r)
{
return (v[l].c-v[l].r) + (v[r].c-v[l].c) + 1;
}
void evalState(int mid, int lOpt, int rOpt, int j)
{
rOpt = min(rOpt, mid);
for(int p = lOpt;p<=rOpt;p++)
{
long long curr;
if(p!=0) curr = dp[p-1][j-1] + squareNum(getSquareSz(p, mid))
- squareNum(v[p-1].c-(v[mid].c-getSquareSz(p, mid)));
else
curr = squareNum(getSquareSz(p, mid));
if(dp[mid][j]>curr)
{
opt[mid][j] = p;
dp[mid][j] = curr;
}
//cout << p << " -> " << squareNum(v[p-1].c-(v[i].c-squareSz[p][i])) << " " << side << '\n';
}
}
void evalDP(int l, int r, int lOpt, int rOpt, int j)
{
if(l>r) return;
int mid = (l+r)/2;
evalState(mid, lOpt, rOpt, j);
evalDP(l, mid-1, lOpt, opt[mid][j], j);
evalDP(mid+1, r, opt[mid][j], rOpt, j);
}
long long take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c)
{
n = _n;
m = _m;
k = _k;
for(int i = 0;i<n;i++)
{
if(c[i]<r[i]) swap(c[i], r[i]);
}
for(int i = 0;i<n;i++) v.push_back(Point(r[i], c[i]));
sort(v.begin(), v.end(), cmpCol);
init();
for(int i = 0;i<n;i++) dp[i][0] = squareNum(getSquareSz(0, i));
if(k<=105)
{
for(int j = 1;j<k;j++)
{
evalDP(0, n-1, 0, n-1, j);
}
}
else
{
for(int j = 1;j<k;j++)
{
for(int i = n-1;i>=0;i--)
{
int lOpt = ((j==1)?0:opt[i][j-1]);
int rOpt = ((i==n-1)?i:opt[i+1][j]);
evalState(i, lOpt, rOpt, j);
}
}
}
long long answer = 6996969969696996LL;
for(int i = 0;i<k;i++) answer = min(answer, dp[n-1][i]);
return answer;
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
5 10 2
0 3
3 4
4 3
3 3
4 2
*/
