#include "aliens.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#define int long long
using namespace std;
struct line
{
int a, b, num;
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() - 2];
line last = hull.back();
long double int1 = ((long double) (last.b - newl.b)) / ((long double)(newl.a - last.a));
long double int2 = ((long double) (snlt.b - last.b)) / ((long double)(last.a - snlt.a));
return int1 <= int2;
}
void insert(int a, int b, int num)
{
line newl;
newl.a = a;
newl.b = b;
newl.num = num;
while (bad(newl)) hull.pop_back();
hull.push_back(newl);
}
pair<int,int> query(int x)
{
if (hull.empty()) return {0, -1};
while (hull.size() > 1 && hull[0].getval(x) >= hull[1].getval(x)) hull.pop_front();
return {hull[0].getval(x), hull[0].num};
}
};
struct dpstruct
{
int n;
int k;
int m;
vector<int> l;
vector<int> r;
pair<int,int> run(int c)
{
vector<int> dp(n + 1, 1e17);
dp[0] = 0;
vector<int> nr(n + 1, -1);
nr[0] = 0;
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], dp[i] + l[i]*l[i] - ovlp*ovlp + c, i);
auto q = hull.query(r[i]);
dp[i + 1] = q.first + (r[i]*r[i]);
nr[i + 1] = nr[q.second] + 1;
}
/*
for (int i : dp) cerr << i << " ";
cerr << "\n";
for (int i : nr) cerr << i << " ";
cerr << "\n";
*/
return {dp[n], nr[n]};
}
int calc()
{
k = min(k, n);
int minb = -1;
int maxb = m*m + 1;
while (maxb - minb > 1)
{
int mid = (minb + maxb)/2;
if (run(mid).second < k)
{
maxb = mid;
}
else
{
minb = mid;
}
}
if (run(minb).second == k)
{
return run(minb).first - k*minb;
}
auto rmin = run(minb);
auto rmax = run(maxb);
int minres = rmin.first - rmin.second*minb;
int maxres = rmax.first - rmax.second*maxb;
int resdiff = (maxres - minres) / (rmin.second - rmax.second);
/*
cerr << minb << " " << rmin.first << " " << rmin.second << " " << minres << "\n";
cerr << maxb << " " << rmax.first << " " << rmax.second << " " << maxres << "\n";
cerr << resdiff << "\n";*/
return minres + resdiff*(rmin.second - k);
}
};
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.m = m;
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];
}
