#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll INF = 1e18;
struct Line{
ll m = 0;
ll c = INF;
Line(ll _m, ll _c){
m=_m;
c=_c;
}
ll f(ll x){
return m*x + c;
}
ld intersectX(Line &a){
return (1.0*(a.c-c))/(m-a.m);
}
};
struct ConvexHull{
deque<Line> dq;
void insert(Line l){
// wlog gradients decreasing
if (dq.size()==0){
dq.push_back(l);
return;
}
if (dq.back().m == l.m){
if (l.c < dq.back().c){
dq.pop_back();
dq.push_back(l);
}
return;
}
int s = dq.size();
while (s>=2 && l.intersectX(dq[s-1])<l.intersectX(dq[s-2])){
dq.pop_back();
s--;
}
dq.push_back(l);
}
ll query(ll x){
while (dq.size()>=2 && dq[0].f(x)>dq[1].f(x)){
dq.pop_front();
}
return dq[0].f(x);
}
};
long long take_photos(int n, int m, int k, std::vector<int> rv, std::vector<int> cv) {
vector<pair<ll,ll>> ptmp(n);
for (int i = 0; i<n; i++){
if (cv[i]>rv[i]){
ptmp[i]={rv[i],-cv[i]};
} else {
ptmp[i]={cv[i],-rv[i]};
}
}
sort(ptmp.begin(),ptmp.end());
vector<ll> r;
vector<ll> c;
c.push_back(ptmp[0].first);
r.push_back(-ptmp[0].second);
for (int i = 1; i<n; i++){
if (c.back()<ptmp[i].first&&-r.back()>ptmp[i].second){
c.push_back(ptmp[i].first);
r.push_back(-ptmp[i].second);
}
}
/*cout<<"points (monotonically decreasing):\n";
for (int i = 0; i<c.size(); i++){
cout<<c[i]<<' '<<r[i]<<'\n';
}*/
n = c.size();
vector<ll> intersect(n-1);
for (int i = 0; i<n-1; i++){
ll b = r[i];
ll a = c[i+1];
if (b<a){
continue;
}
//cout<<"intersect "<<a<<' '<<b<<'\n';
intersect[i] = (b-a+1) * (b-a+1);
}
/*cout<<"intersect values:\n";
for (int i : intersect){
cout<<i<<' ';
}cout<<'\n';*/
vector<vector<ll>> dp(k+1,vector<ll>(n,INF));
ll minans = INF;
for (int num = 1; num<=k; num++){
ConvexHull hull;
hull.insert({2-2*c[0],(c[0]-1)*(c[0]-1)});
for (int x = 0; x<n; x++){
dp[num][x] = r[x]*r[x] + hull.query(r[x]);
if (x!=n-1){
hull.insert({2-2*c[x+1], dp[num-1][x]-intersect[x]+(c[x+1]-1)*(c[x+1]-1)});
} else {
minans=min(minans,dp[num][x]);
}
}
}
/*for (int num = 1; num<=k; num++){
for (int x = 0; x<n; x++){
cout<<dp[num][x]<<' ';
}cout<<'\n';
}*/
return minans;
}
