#include "aliens.h"
#include <bits/stdc++.h>
using namespace std ;
#define ff first
#define ss second
typedef long double ll ;
typedef pair<ll,ll> pll ;
const int M = 1e6+2 ;
const int N = 1e5+2 ;
int mxCoor[ M ] ;
vector <pll> points ;
int sz ;
pll dp [N];
ll Lowpend, Hgpend, Midpend ;
ll last ;
struct info {
ll m, b, ind ;
info ( ll m1, ll b1, ll ind1 ) {
m = m1 ;
b = b1 ;
ind = ind1 ;
}
};
vector <info> convex ;
ll comm ( info A, info B ) {
return (1.0*B.b - A.b) / (A.m - B.m) ;
}
void add ( info cur ) {
while ( 1 ) {
if ( convex.size() < 2 ) {
convex.push_back ( cur ) ;
break ;
}
info tp = convex.back() ;
convex.pop_back() ;
info scn = convex.back() ;
if ( comm ( cur, scn ) > comm ( scn, tp ) ) {
convex.push_back ( tp ) ;
convex.push_back ( cur ) ;
break ;
}
}
}
info query ( int p ) {
int lw = 0, hg = convex.size() ;
--hg ;
while ( lw < hg ) {
int mid = (lw+hg)/2 ;
long double inter = comm(convex[mid], convex[mid+1]) ;
// cout << mid << ' ' << inter << ' '<< p << '\n' ;
if ( inter == p ) return convex[mid] ;
if ( inter < p ) lw = mid+1 ;
else hg = mid ;
}
return convex[lw] ;
}
ll intersect ( int k ) {
ll inters = points[k].ss - points[k+1].ff + 1;
if ( inters < 0 ) inters = 0 ;
inters *= inters ;
return inters ;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
memset ( mxCoor, -1, sizeof mxCoor ) ;
for ( int i = 0 ; i < n ; ++i ) {
if ( c[i] >= r[i] ) mxCoor [r[i]] = max ( mxCoor [r[i]], c[i] ) ;
else mxCoor [c[i]] = max ( mxCoor [c[i]], r[i] ) ;
}
int mx = -1 ;
for ( int i = 0 ; i < m ; ++i ) {
if ( mxCoor[i] <= mx ) continue ;
mx = mxCoor[i] ;
points.push_back({i,mx}) ;
}
sz = points.size() ;
last = mx+1 ;
Lowpend = 0, Hgpend = 1ll*last*last ;
ll ans = 0 ;
k = min(k,sz) ;
while ( fabs(Lowpend-Hgpend) > 1e-6 ) {
convex.clear() ;
Midpend = (Lowpend+Hgpend)/2 ;
dp[sz] = {0,0} ;
info *x = new info( 1ll*points[sz-1].ss, points[sz-1].ss * points[sz-1].ss, 1ll*sz ) ;
add(*x) ;
for ( int i = sz-1 ; i >= 0 ; --i ) {
info opt = query(-2*(points[i].ff-1)) ;
dp[i].ff = (points[i].ff-1)*(points[i].ff-1) - 2*(points[i].ff-1)*(opt.m) + opt.b + Midpend;
dp[i].ss = dp[(int)opt.ind].ss + 1 ;
if ( i ) {
info *x = new info( 1ll*points[i-1].ss, 1ll*dp[i].ff - intersect (i-1) + points[i-1].ss * points[i-1].ss, 1ll*i ) ;
add(*x) ;
}
}
// cout << dp[0].ff << ' ' << dp[0].ss << ' ' << Midpend << '\n' ;
if ( dp[0].ss >= k ) Lowpend = Midpend, ans = dp[0].ff - (long long)(k * Midpend) ;
else Hgpend = Midpend ;
}
// cout << Hgpend << '\n' ;
return (long long)ans;
}
/*
10 100 3
0 0
1 1
2 2
3 3
4 4
5 5
6 6
50 50
81 81
99 99
*/
