#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#pragma once
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
map<pair<ll,ll>,int > M;
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto it = lower_bound(x);
auto it2 = next(it);
if((it2!=this->end()) && ((*it).k * x + (*it).m) == ((*it2).k * x + (*it2).m)
&& M[make_pair((*it).k,(*it).m)]<M[make_pair((*it2).k,(*it2).m)])
it = it2;
auto l = *it;
return l.k * x + l.m;
}
Line getLine(ll x)
{
assert(!empty());
auto it = lower_bound(x);
auto it2 = next(it);
if((it2!=this->end()) && ((*it).k * x + (*it).m) == ((*it2).k * x + (*it2).m)
&& M[make_pair((*it).k,(*it).m)]<M[make_pair((*it2).k,(*it2).m)])
it = it2;
auto l = *it;
return l;
}
};
bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
if(a.first==b.first)
return a.second>b.second;
return a.first<b.first;
}
bool inters(pair<int,int> a,pair<int,int> b)
{
if(a.first<=b.first && a.second>=b.second)
return true;
return false;
}
pair<ll,ll> pics(long long penalty,int n,int m,vector<int>& r,vector<int>& c)
{
vector<pair<long long,long long> > obj;
vector<pair<long long,long long> > aux;
M.clear();
for(int i = 0;i<n;i++)
aux.emplace_back(1LL*min(r[i],c[i]),1LL*max(r[i],c[i]));
sort(aux.begin(),aux.end(),cmp);
obj.emplace_back(-1,-1);
for(auto it:aux)
{
if(!inters(obj.back(),it))
obj.push_back(it);
}
n = obj.size();
vector<long long> dp;
vector<int> pics;
dp.resize(n+1);
pics.resize(n+1);
LineContainer lc;
lc.add(2*obj[1].first,-obj[1].first*obj[1].first);
M[make_pair(2*obj[1].first,-obj[1].first*obj[1].first)] = 0;
for(int i=1;i<n;i++)
{
long long zi = obj[i].second+1;
Line best = lc.getLine(zi);
long long res = -lc.query(zi);
dp[i] = res + zi * zi + penalty;
pics[i] = 1 + M[make_pair(best.k,best.m)];
long long intersection = max(0LL,obj[i].second-obj[i+1].first+1LL)*max(0LL,obj[i].second-obj[i+1].first+1LL);
long long a = 2 * obj[i + 1].first;
long long b = -dp[i] - obj[i + 1].first * obj[i + 1].first + intersection;
lc.add(a,b);
if(M.find(make_pair(a,b))==M.end())
M[make_pair(a,b)] = pics[i];
else
M[make_pair(a,b)] = max(M[make_pair(a,b)],pics[i]);
}
return make_pair(dp[n-1],pics[n-1]);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
long long st = 0;
long long dr = m*m;
long long sol;
pair<ll,ll> best;
while(st<=dr)
{
long long mid = (st+dr)>>1;
if(pics(mid,n,m,r,c).second<=k)
{
sol=mid;
best = pics(mid,n,m,r,c);
dr = mid-1;
}
else st = mid+1;
}
return best.first - sol * best.second;
}
