#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define double long double
#define F first
#define S second
#define ll long long
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
const ll inf=1e15;
const int MAXN=505;
typedef pair<ll,ll> pii;
double sq(double x){
return x*x;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pii> ord;
fall(i,0,n-1){
if(c[i]<r[i]) swap(r[i],c[i]);
ord.pb({r[i],-c[i]});
}
sort(all(ord));
vector<pii> v;
int mx=-1;
for(auto [u,j]:ord){
j=-j;
if(mx>=j) continue;
mx=j;
v.pb({u,j});
}
n=sz(v);
deque<tuple<double,double,int>> cht;
auto inter=[&](double a,double b,double c,double d){
double ret=(1.00*b-1.00*d)/(1.00*c-1.00*a);
return ret;
};
auto insert=[&](double a,double b,int lx){
while(sz(cht)>1){
auto [c,d,lx1]=cht.back(); cht.pop_back();
auto [e,f,lx2]=cht.back();
if(inter(a,b,c,d)>inter(c,d,e,f)){
cht.pb({c,d,lx1});
break;
}
}
cht.pb({a,b,lx});
return;
};
vector<double> dp(n+1);
vector<int> us(n+1);
auto aliens=[&](double val){
fall(i,0,n) dp[i]=inf;
dp[0]=0;
cht.clear();
cht.pb({-2*v[0].F,sq(v[0].F)+val,0}); //a frente tem os maiores coeficientes a's
fall(i,1,n){
while(sz(cht)>1){
auto [a,b,lx]=cht.front(); cht.pop_front();
auto [c,d,lx1]=cht.front();
if(a*(1+v[i-1].S)+b<c*(1+v[i-1].S)+d){
cht.push_front({a,b,lx});
break;
}
}
auto [a,b,lx]=cht.front();
dp[i]=a*(1+v[i-1].S)+b+sq(v[i-1].S+1);
us[i]=lx+1;
if(i!=n) insert(-2*v[i].F,dp[i]+sq(v[i].F)-sq(max(0ll,v[i-1].S-v[i].F+1))+val,us[i]);
}
return pair<double,int>{dp[n],us[n]};
};
double ini=0,fim=m*m,ans=0;
k=min(k,n);
while(fim-ini>=1e-8){
double mei=(ini+fim)/2.00;
auto [val,use]=aliens(mei);
if(use<=k) ans=val-k*mei,fim=mei;
else ini=mei;
}
int re=ceil(ans);
if(ans-floor(ans)<ceil(ans)-ans) re=floor(ans);
return re;
}
