#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define maxn 100010
#define pii pair<int, int>
#define pli pair<ll, int>
int M, N;
int K;
vector<pii> og;
vector<pii> vals;
ll endval;
int si = 0, ei = 0;
//below three will act as my deque
ll dp[maxn];
int numtake[maxn];
int xval[maxn];
int cx;
ll fact = 1LL;
bool done = false;
ll eval(int ii, ll xv) {
ll res = dp[ii] + fact*(xv - xval[ii] + 1LL)*(xv - xval[ii] + 1LL);
// if (done) cout << xval[ii] << " at " << xv << " gives :: " << res << endl;
return res;
}
ll to(int fi, int se) {
//time overtaken
ll c1 = dp[fi];
ll c2 = dp[se];
assert(c1 > c2);
ll x1 = xval[fi];
ll x2 = xval[se];
assert(x1 > x2);
ll numer = x1*x1 + c1 - x2*x2 - c2;
ll denom = 2 * (x1 - x2);
return numer/denom;
}
int go(ll cost) {
si = maxn-1;
ei = maxn-1;
dp[si] = 0;
numtake[si] = 0;
xval[maxn-1] = vals[0].first;
ll lastcost = cost + fact*(vals[0].second - vals[0].first + 1LL) *
(vals[0].second - vals[0].first + 1LL) ;
int lasttake = 1;
// int lastx = vals[0].first;
if (N == 1) {
endval = lastcost;
return 1;
}
for (int i = 1; i < N; i++) {
// cout << " made it to " << i << endl;
// if (done) cout << "lcost1: " << lastcost << endl;
if (vals[i-1].second >= vals[i].first) {
lastcost -= fact*(vals[i-1].second - vals[i].first + 1LL) *
(vals[i-1].second - vals[i].first + 1LL);
}
// if (done) cout << "lcost2: " << lastcost << endl;
--si;
dp[si] = lastcost;
numtake[si] = lasttake;
xval[si] = vals[i].first;
//above adds in cost for taking me
while (si < ei-1) {
if (to(si, si+1) <= to(si+1, si+2)) {
dp[si+1] = dp[si];
numtake[si+1] = numtake[si];
xval[si+1] = xval[si];
++si;
}
else break;
}
ll mycost = 0LL;
while (ei > si && eval(ei, vals[i].second) >
eval(ei-1, vals[i].second)) {
// if (done) cout << "HERE" << endl;
--ei;
}
mycost = eval(ei, vals[i].second) + cost;
//also consider taking myself by myself
if (i == N-1) {
endval = mycost;
return numtake[ei]+1;
}
lastcost = mycost;
lasttake = numtake[ei]+1;
// lastx = vals[i].first;
}
return -1; //should not happen
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
N = n;
M = m;
for (int i = 0; i < n; i++) {
og.push_back(pii(min(r[i], c[i]), 0-max(r[i], c[i])));
}
int bigr = -1;
sort(og.begin(), og.end());
for (int i = 0; i < n; i++) {
int x = og[i].first;
int y = 0-og[i].second;
if (y > bigr) {
// cout << "adding val: " << x << " " << y << endl;
vals.push_back(pii(x, y));
bigr = y;
}
}
N = vals.size();
K = min(k, N);//why not
ll lo = 0LL;
ll hi = fact*m*1LL*m;
while (lo < hi) {
ll mid = (lo+hi)/2;
// cout << "checking: " << mid << endl;
int taken = go(mid);
if (taken > K) {
//took too many, make cost larger
lo = mid+1LL;
}
else {
//took too few, make cost cheaper
hi = mid;
}
}
go(lo);
done = true;
// cout << go(lo) << " " << lo << " :: " << endval << " - " << K << endl;
return (endval - lo * K)/fact;
}
