#include "aliens.h"
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
class LinearFunction {
private:
ll slope, intercept;
public:
LinearFunction(ll m, ll c) : slope(m), intercept(c) {}
ll evaluate(ll x) const {
return slope * x + intercept;
}
ll getSlope() const { return slope; }
ll getIntercept() const { return intercept; }
};
class ConvexHullTrick {
private:
deque<LinearFunction> hull;
bool isRedundant(const LinearFunction& left, const LinearFunction& mid, const LinearFunction& right) {
__int128 lhs = (__int128)(left.getSlope() - right.getSlope()) *
(__int128)(mid.getIntercept() - left.getIntercept());
__int128 rhs = (__int128)(left.getSlope() - mid.getSlope()) *
(__int128)(right.getIntercept() - left.getIntercept());
return lhs <= rhs;
}
public:
void insert(LinearFunction func) {
if (!hull.empty() && hull.front().getSlope() == func.getSlope()) {
if (hull.front().getIntercept() <= func.getIntercept()) {
return;
}
hull.pop_front();
}
while (hull.size() >= 2) {
if (isRedundant(func, hull[0], hull[1])) {
hull.pop_front();
} else {
break;
}
}
hull.push_front(func);
}
ll queryMin(ll x) {
while (hull.size() >= 2) {
int lastIdx = hull.size() - 1;
if (hull[lastIdx].evaluate(x) >= hull[lastIdx - 1].evaluate(x)) {
hull.pop_back();
} else {
break;
}
}
return hull.back().evaluate(x);
}
};
struct Segment {
int start, end;
Segment(int s, int e) : start(s), end(e) {}
bool operator<(const Segment& other) const {
if (start != other.start) return start < other.start;
return end > other.end;
}
ll coverage() const {
return (ll)(end - start + 1) * (end - start + 1);
}
};
vector<Segment> preprocessSegments(int n, vector<int>& r, vector<int>& c) {
vector<Segment> segments;
segments.reserve(n);
for (int i = 0; i < n; i++) {
int startPos = min(r[i], c[i]);
int endPos = max(r[i], c[i]);
segments.emplace_back(startPos, endPos);
}
sort(segments.begin(), segments.end());
vector<Segment> filtered;
int maxEnd = -1;
for (const auto& seg : segments) {
if (seg.end > maxEnd) {
filtered.push_back(seg);
maxEnd = seg.end;
}
}
return filtered;
}
ll calculateOverlap(const Segment& prev, const Segment& curr) {
if (curr.start > prev.end) return 0;
ll overlap = prev.end - curr.start + 1;
return overlap * overlap;
}
pair<ll, int> solveWithPenalty(const vector<Segment>& segments, ll penalty) {
int n = segments.size();
vector<ll> dp(n + 1, 1e18);
vector<int> count(n + 1, 0);
dp[0] = 0;
ConvexHullTrick cht;
for (int i = 0; i <= n; i++) {
if (i > 0) {
ll x = segments[i - 1].end;
ll minCost = cht.queryMin(x);
dp[i] = minCost + x * x + penalty;
}
if (i < n) {
ll slope = -2 * segments[i].start + 2;
ll overlap = (i > 0) ? calculateOverlap(segments[i - 1], segments[i]) : 0;
ll base = segments[i].start - 1;
ll intercept = dp[i] + base * base - overlap;
cht.insert(LinearFunction(slope, intercept));
}
}
// calculate number of segments used
count[n] = 0;
vector<ll> tempDp = dp;
for (int i = n - 1; i >= 0; i--) {
ll x = segments[i].end;
ll costWithSegment = segments[i].coverage();
if (i > 0) {
costWithSegment -= calculateOverlap(segments[i - 1], segments[i]);
}
for (int j = i + 1; j <= n; j++) {
if (dp[j] - dp[i] - penalty <= costWithSegment + 1e-9) {
count[i] = count[j] + 1;
break;
}
}
}
return {dp[n], count[0]};
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
auto segments = preprocessSegments(n, r, c);
n = segments.size();
if (n <= k) {
// can use one segment per point
ll total = 0;
for (int i = 0; i < n; i++) {
total += segments[i].coverage();
if (i > 0) {
total -= calculateOverlap(segments[i - 1], segments[i]);
}
}
return total;
}
ll left = 0, right = (ll)m * m;
while (right - left > 2) {
ll mid1 = left + (right - left) / 3;
ll mid2 = right - (right - left) / 3;
ll cost1 = solveWithPenalty(segments, mid1).first;
ll cost2 = solveWithPenalty(segments, mid2).first;
if (cost1 > cost2) {
left = mid1;
} else {
right = mid2;
}
}
ll result = 1e18;
for (ll penalty = left; penalty <= right; penalty++) {
auto [cost, numSegments] = solveWithPenalty(segments, penalty);
if (numSegments <= k) {
result = min(result, cost + (k - numSegments) * penalty);
}
}
return result;
}
