#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e15;
struct Segment {
lint left, right;
Segment(lint l = 0, lint r = 0): left(l), right(r) {}
bool operator < (const Segment &o) const {
return left < o.left || (left == o.left && right > o.right);
}
bool operator == (const Segment &o) const {
return left == o.left && right == o.right;
}
};
struct ConvexHull { // Convex Hull Trick
struct Line {
lint m, c;
int cnt;
Line(lint M = 0, lint C = INF, int cnt_ = 0): m(M), c(C), cnt(cnt_) {}
lint get(lint x) {
return m * x + c;
}
};
vector<Line> hull = {Line(0, INF)};
int ptr = 0;
void insert(lint m, lint c, int cnt) {
hull.emplace_back(Line(m, c, cnt));
int sz = hull.size() - 1;
while (ptr <= sz - 2 && (hull[sz - 1].c - hull[sz].c) * (hull[sz - 1].m - hull[sz - 2].m) <
(hull[sz - 2].c - hull[sz - 1].c) * (hull[sz].m - hull[sz - 1].m))
hull[sz - 1] = hull[sz], sz--, hull.pop_back();
}
lint query(lint x) {
while (ptr + 1 < hull.size() && hull[ptr].get(x) > hull[ptr + 1].get(x))
ptr++;
return hull[ptr].get(x) + x * x;
}
int cnt_query(lint x) {
query(x);
return hull[ptr].cnt;
}
void clear() {
hull.clear();
hull = {Line(0, INF)};
ptr = 0;
}
};
int N, K;
vector<Segment> segment;
vector<lint> DP; // find optimal answer in O(N)
vector<int> cnt; // K used in DP[i] (optimal)
ConvexHull hull;
void preprocess(int n, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; i++)
segment.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
sort(segment.begin(), segment.end());
vector<Segment> tmp;
tmp.emplace_back(-1, -1);
for (auto s : segment) {
Segment overlap = Segment(min(tmp.back().left, s.left), max(tmp.back().right, s.right));
if (overlap == s) swap(s, tmp.back());
if (overlap == tmp.back()) continue;
tmp.emplace_back(s);
}
segment = tmp, N = segment.size() - 1, K = k;
DP.assign(N + 1, 0), cnt.assign(N + 1, 0);
}
void computeDP(lint lambda) { // returns number of k used, with each photo having penalty lambda (equals to DP[N][K] + K * lambda)
DP[0] = cnt[0] = 0, hull.clear();
for (int n = 1; n <= N; n++) {
lint m = - 2 * segment[n].left;
lint c = + segment[n].left * segment[n].left
- max(0ll, segment[n - 1].right - segment[n].left + 1) *
max(0ll, segment[n - 1].right - segment[n].left + 1)
+ DP[n - 1] + lambda;
hull.insert(m, c, cnt[n - 1] + 1);
cnt[n] = hull.cnt_query(segment[n].right + 1);
DP[n] = hull.query(segment[n].right + 1);
}
}
lint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
lint opt = INF;
preprocess(n, k, r, c);
for (lint le = 0, ri = INF, mid = (le + ri) / 2; le <= ri; mid = (le + ri) / 2) {
computeDP(mid);
if (cnt[N] <= K)
ri = mid - 1, opt = mid;
else
le = mid + 1;
}
computeDP(opt);
return DP[N] - K * opt;
}
