#include <iostream>
#include <vector>
#include <algorithm>
#define rep(s, e) for(ll i = s; i < e; i++)
#define rep(e) for(ll i = 0; i < e; i++)
#define what(x) cout << #x << ": " << x << endl;
#define upmin(a, b) a = min(a, b)
#define pr(v) cout << #v << ": " << endl; for(auto it = v.begin(); it != v.end(); it++) cout << *it << " "; cout << endl;
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
const ll inf = 1e18;
/*
Solution:
dp[i][j] = min cost to do first i cells with jj squares
do each layer with D&C
Complexity:
O(k*nlogn)
Should get 60
*/
struct seg {
ll s, e;
seg() {}
seg(ll s, ll e) : s(s), e(e) {};
void print() {
cout << "(" << this->s << ", " << this->e << ")" << endl;
}
inline bool operator<(const seg& other) {
if (this->s < other.s) return true;
if (this->s > other.s) return false;
return (this->e > other.e);
}
};
ll get_size(ll s, ll e)
{
if (e < s) return 0;
ll len = e - s + (ll)1;
return len * len;
}
bool comp_seg(const seg& s1, const seg& s2) {
if (s1.s < s2.s) return true;
if (s1.s > s2.s) return false;
return (s1.e > s2.e);
}
using vs = vector<seg>;
seg to_seg(ll x, ll y) {
seg tans = seg(min(x, y), max(x, y));
return tans;
}
ll n, m, k;
vs arr;
vvll dp;
void D_C(ll layer, ll l, ll r, ll optl, ll optr)
{
ll i = (l + r) / 2;
//what(l);
//what(r);
ll opt = 0;
ll optval = inf;
for (ll j = optl; j <= min(optr, i); j++) {
ll lastlen = get_size(arr[j].s, arr[i].e);
//ll inter = get_size(arr[j].e, arr[i].s);
ll inter = 0;
if (j > 0) inter = get_size(arr[j].s, arr[j-1].e);
ll curcost = lastlen - inter;
//what(i);
//what(j);
if (j > 0) curcost += dp[layer - 1][j - 1];
if (optval > curcost) {
optval = curcost;
opt = j;
}
}
dp[layer][i] = optval;
if (l +1 >= r) return;
D_C(layer, l, i, optl, opt);
D_C(layer, i, r, opt, optr);
}
ll take_photos(int N, int M, int K, vi r, vi c)
{
n = N, m = M, k = K;
vs segs(n);
rep(n) {
segs[i] = to_seg(r[i], c[i]);
}
sort(segs.begin(), segs.end(), comp_seg);
/*
for (auto it : segs) {
it.print();
}
*/
arr.push_back(segs[0]);
for (ll i = 1; i < n; i++) {
seg cur = segs[i];
if (arr[arr.size() - 1].e >= cur.e) continue;
arr.push_back(cur);
}
n = arr.size();
/*
what(n);
for (auto it : arr) {
it.print();
}
*/
dp.resize(k+1, vll(n, inf));
for (ll layer = 1; layer <= k; layer++) {
D_C(layer, 0, n, 0, n);
}
ll ans = inf;
for (ll layer = 0; layer <= k; layer++) {
upmin(ans, dp[layer][n - 1]);
}
/*
for (ll layer = 0; layer <= k; layer++) {
pr(dp[layer]);
}
*/
return ans;
}
/*
(5, 7, 2, [0, 4, 4, 4, 4], [3, 4, 6, 5, 6])
5 7 2
0 3
4 4
4 6
4 5
4 6
// 25
(2, 6, 2, [1, 4], [4, 1])
2 6 2
1 4
4 1
// 16
3 10 3
1 1
2 2
3 3
*/
