#include "aliens.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n, m, k;
struct Interval
{
int l, r;
inline friend bool operator < (const Interval &a, const Interval &b)
{
return a.l < b.l || (a.l == b.l && a.r < b.r);
}
};
struct CHT
{
struct Line
{
llong x, y;
int cntPenalties;
int to;
std::pair <llong,int> getValue(int at)
{
return {x * at + y, cntPenalties};
}
};
llong intersect(Line a, Line b)
{
if (a.y >= b.y)
{
return INF;
}
return (b.y - a.y) / (a.x - b.x) - ((b.y - a.y) % (a.x - b.x) == 0 && b.cntPenalties < a.cntPenalties);
}
std::deque <Line> dq;
void reset()
{
dq.clear();
}
void push(Line toPush)
{
while (dq.size() && dq.front().getValue(dq.front().to) > toPush.getValue(dq.front().to))
{
dq.pop_front();
}
if (dq.empty())
{
dq.push_front(toPush);
} else
{
llong where = intersect(toPush, dq.front());
if (where <= m) dq.push_front({toPush.x, toPush.y, toPush.cntPenalties, where});
}
}
std::pair <llong,int> find(int at)
{
while (dq.size() >= 2 && dq[dq.size() - 2].to >= at)
{
dq.pop_back();
}
assert(dq.size());
return dq.back().getValue(at);
}
};
CHT cht;
std::vector <Interval> v;
std::pair <llong,int> dp[MAXN];
std::pair <llong,int> check(llong penalty)
{
cht.reset();
cht.push({-2 * v.back().r, 1LL * v.back().r * v.back().r + penalty, 1, m});
for (int idx = v.size() - 1 ; idx >= 0 ; --idx)
{
dp[idx] = cht.find(v[idx].l);
dp[idx].first += 1LL * v[idx].l * v[idx].l;
if (idx != 0)
{
llong toRemove = std::max(0, v[idx - 1].r - v[idx].l); toRemove *= toRemove;
cht.push({-2 * v[idx - 1].r, 1LL * v[idx - 1].r * v[idx - 1].r + dp[idx].first - toRemove + penalty, dp[idx].second + 1, m});
}
}
return dp[0];
}
llong take_photos(int N, int M, int K, std::vector <int> x, std::vector <int> y)
{
n = N; m = M; k = K;
std::vector <Interval> sorted;
for (int i = 0 ; i < n ; ++i)
{
sorted.push_back({std::min(x[i], y[i]), std::max(x[i], y[i]) + 1});
}
std::sort(sorted.begin(), sorted.end());
for (const Interval &curr : sorted)
{
while (v.size() && v.back().l == curr.l && curr.r >= v.back().r)
{
v.pop_back();
}
if (v.empty() || v.back().r < curr.r)
{
v.push_back(curr);
}
}
k = std::min(k, (int)v.size());
llong l = -1, r = 1LL * m * m, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
auto res = check(mid);
if (res.second == k)
{
return res.first - k * mid;
}
if (res.second > k) l = mid;
else r = mid;
}
auto resL = check(l);
auto resR = check(r);
llong fL = resL.first - resL.second * l;
llong fR = resR.first - resR.second * r;
return fL + (fR - fL) * (resL.second - k) / (resL.second - resR.second);
}
