#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4005;
const long long inf = (1LL << 62);
const long long MAXLAMBDA = 1e13;
int n, m, k;
pair<int, int> points[maxn];
vector<pair<int, int>> v, v2;
pair<long long, int> dp[maxn];
long long rem[maxn];
long long sq(long long x)
{
return x * x;
}
struct Line
{
long long a, b;
int dpSecond;
long long calc(long long x)
{
return a * x + b;
}
};
double intersect(Line l1, Line l2)
{
return (1.0 * (l2.b - l1.b)) / (1.0 * (l1.a - l2.a));
}
struct ConvexHullTrickMin
{
vector<pair<Line, double>> envelope;
void reset()
{
envelope.clear();
}
bool toRemove(Line prv2, Line prv1, Line& newLine)
{
double p1 = intersect(prv2, prv1);
double p2 = intersect(prv2, newLine);
if (p2 > p1) return false;
//newLine.dpSecond = min(newLine.dpSecond, prv1.dpSecond);
if (p2 < p1) return true;
return true;
}
void addLine(Line newLine)
{
int curr = newLine.dpSecond;
while (envelope.size() >= 2 && toRemove(envelope[envelope.size() - 2].first, envelope.back().first, newLine) == true)
{
envelope.pop_back();
}
if (envelope.size() >= 1) envelope.push_back({newLine, intersect(newLine, envelope.back().first)});
else envelope.push_back({newLine, -inf});
}
Line query(double x)
{
int l = 0;
int r = envelope.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (x == envelope[mid].second)
{
if (mid == 0) return envelope[mid].first;
if (envelope[mid].first.dpSecond > envelope[mid - 1].first.dpSecond) return envelope[mid - 1].first;
else return envelope[mid].first;
}
if (envelope[mid].second > x)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
return envelope[r].first;
}
};
ConvexHullTrickMin cht;
pair<long long, int> check(long long lambda)
{
cht.reset();
dp[0] = {0, 0};
for (int i = 1; i <= n; ++i)
{
dp[i] = {inf, 0};
}
for (int i = 1; i <= n; ++i)
{
cht.addLine({-2 * points[i].first + 2, dp[i - 1].first - rem[i] - 2 * points[i].first + points[i].first * points[i].first + 1, dp[i - 1].second});
Line bestLine = cht.query(points[i].second);
dp[i] = {bestLine.calc(points[i].second) + points[i].second * points[i].second + lambda, 1 + bestLine.dpSecond};
}
return dp[n];
}
long long take_photos(int N, int M, int K, std::vector<int> rr, std::vector<int> c)
{
m = M;
k = K;
for (int i = 1; i <= N; ++i)
{
int x = rr[i - 1] + 1;
int y = c[i - 1] + 1;
if (x > y)
{
swap(x, y);
}
v.push_back({x, y});
}
sort(v.begin(), v.end());
n = 0;
for (int i = 0; i < N; ++i)
{
if (i == N - 1 || v[i].first != v[i + 1].first)
{
v2.push_back(v[i]);
}
}
int maxEnd = 0;
for (int i = 0; i < v2.size(); ++i)
{
if (v2[i].second <= maxEnd) continue;
points[++n] = v2[i];
maxEnd = points[n].second;
}
for (int i = 2; i <= n; ++i)
{
if (points[i - 1].second >= points[i].first) rem[i] = sq(points[i - 1].second - points[i].first + 1);
}
long long l = 0;
long long r = MAXLAMBDA;
while (l <= r)
{
long long mid = (l + r) / 2;
pair<long long, int> res = check(mid);
//cout << l << " " << r << " " << mid << " :: " << res.first << " " << res.second << endl;
if (res.second > k)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
pair<long long, int> res = check(l);
return res.first - (1LL * k) * l;
}
