#include "aliens.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#define int long long
using namespace std;
struct line
{
int a, b;
int getval(int x)
{
return a*x + b;
}
};
struct convhull
{
deque<line> hull;
vector<line> all;
bool bad(line newl)
{
if (hull.size() < 2) return false;
line snlt = hull[hull.size() - 1];
line last = hull.back();
return ((long double) last.b - newl.b) / (newl.a - last.a) <= ((long double) snlt.b - last.b) / (last.a - snlt.a);
}
void insert(int a, int b)
{
line newl;
newl.a = a;
newl.b = b;
all.push_back(newl);
while (bad(newl)) hull.pop_back();
hull.push_back(newl);
}
int query(int x)
{
int m = 1e17;
for (auto l : all) m = min(m, l.getval(x));
return m;
if (hull.empty()) return 0;
while (hull.size() > 1 && hull[0].getval(x) > hull[1].getval(x)) hull.pop_front();
return hull[0].getval(x);
}
};
struct dpstruct
{
int n;
int k;
vector<int> l;
vector<int> r;
int calc()
{
k = min(k, n);
vector<int> dp(n + 1, 1e17);
vector<int> olddp(n + 1, 1e17);
dp[0] = 0;
olddp[0] = 0;
for (int ik = 0; ik < k; ik++)
{
swap(dp, olddp);
convhull hull;
for (int i = 0; i < n; i++)
{
int ovlp = 0;
if (i > 0) ovlp = max(0ll, r[i - 1] - l[i]);
hull.insert(-2*l[i], olddp[i] + l[i]*l[i] - ovlp*ovlp);
dp[i + 1] = hull.query(r[i]) + (r[i]*r[i]);
}
/*
for (int j : dp) cerr << j << " ";
cerr << "\n";*/
}
return dp[n];
}
};
int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
{
vector<pair<int,int>> prs;
for (int i = 0; i < n; i++)
{
prs.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
}
sort(prs.begin(), prs.end());
vector<int> nl;
vector<int> nr;
nl.push_back(prs[0].first);
nr.push_back(-prs[0].second + 1);
int last = -prs[0].second;
for (int i = 1; i < n; i++)
{
prs[i].second = -prs[i].second;
if (last < prs[i].second)
{
nl.push_back(prs[i].first);
nr.push_back(prs[i].second + 1);
}
last = max(prs[i].second, last);
}
dpstruct dps;
dps.n = nl.size();
dps.k = k;
dps.l = nl;
dps.r = nr;
return dps.calc();
}
int take_photos_slow(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
{
vector<pair<int,int>> intervals;
for (int i = 0; i < n; i++)
{
intervals.push_back({min(r[i], c[i]), -max(r[i], c[i])});
}
sort(intervals.begin(), intervals.end());
vector<int> nl;
vector<int> nr;
int mmx = -1;
for (int i = 0; i < n; i++)
{
if (-intervals[i].second > mmx)
{
nl.push_back(intervals[i].first);
nr.push_back(-intervals[i].second);
mmx = -intervals[i].second;
}
}
int nn = nl.size();
vector<vector<int>> dp(nn + 1, vector<int>(k + 1, 1e12));
dp[0][0] = 0;
for (int i = 1; i <= nn; i++)
{
for (int j = 1; j <= k; j++)
{
dp[i][j] = min(dp[i][j], dp[i][j - 1]);
for (int q = 0; q < i; q++)
{
int ol = 0;
if (q > 0 && nl[q] <= nr[q - 1])
{
ol = nr[q - 1] - nl[q] + 1;
ol *= ol;
}
dp[i][j] = min(dp[i][j], dp[q][j - 1] + (nr[i - 1] - nl[q] + 1)*(nr[i - 1] - nl[q] + 1) - ol);
}
}
}
return dp[nn][k];
}
