// SOLVED SUBTASK 1 (04 pts)
// SOLVED SUBTASK 2 (12 pts)
// SOLVED SUBTASK 3 (09 pts)
// SOLVED SUBTASK 4 (16 pts)
// SOLVED SUBTASK 5 (19 pts)
// UNSOLVED SUBTASK 6 (40 pts)
// [+-+]----------------------
// TOTAL 60/100 pts
#include "aliens.h"
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
struct Coordinate {
long long row, col;
Coordinate(long long row, long long col) : row(std::min(row, col)), col(std::max(row, col)) {}
bool operator<(const Coordinate& other) const {
if (row == other.row) {
return col > other.col;
}
return row < other.row;
}
};
struct Range {
long long start, end;
Range(long long start, long long end) : start(start), end(end) {};
long long merge(const Range& other) const {
return 2 * (other.start - start) * (other.end - end) - (other.start > end ? (other.start - end - 1) * (other.start - end - 1) : 0);
}
};
struct Parabola {
long double h, v;
long double evaluate(long double x) {
return (x - h) * (x - h) + v;
}
};
long double intersect(Parabola a, Parabola b) {
return (b.h * b.h + b.v - a.h * a.h - a.v) / (2.0 * (b.h - a.h));
}
struct ConvexHull {
std::vector<Parabola> parabolas;
std::vector<long double> left;
std::vector<int> indexes;
std::vector<int> cnts;
std::map<long double, int> mp;
int counter = 0;
void insert(Parabola p, int cnt) {
while (!parabolas.empty() && intersect(p, parabolas.back()) < left.back()) {
parabolas.pop_back();
mp.erase(left.back());
left.pop_back();
indexes.pop_back();
cnts.pop_back();
}
if (parabolas.empty()) {
parabolas.push_back(p);
left.push_back(-1e18); // neg infty
indexes.push_back(counter);
} else {
long double x = intersect(p, parabolas.back());
parabolas.push_back(p);
left.push_back(x);
if (mp.count(x)) {
if (cnt > cnts[mp[x]]) {
mp[x] = parabolas.size() - 1;
}
} else {
if (cnts.back() > cnt) {
mp[x] = parabolas.size() - 2;
} else {
mp[x] = parabolas.size() - 1;
}
}
indexes.push_back(counter);
}
cnts.push_back(cnt);
++counter;
// std::cout << "inserted (x-" << p.h << ")^2 + " << p.v << '\n';
}
std::pair<int, long double> min(long double x) {
int index = std::upper_bound(left.begin(), left.end(), x) - left.begin() - 1;
if (mp.count(x)) {
int index = mp[x];
}
return {indexes[index], parabolas[index].evaluate(x)};
}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
std::vector<Coordinate> points;
for (size_t i = 0; i < n; ++i) {
points.push_back(Coordinate(r[i], c[i]));
}
std::sort(points.begin(), points.end());
std::vector<Range> ranges;
long long furthestStart = -1;
long long furthestEnd = -1;
for (size_t i = 0; i < points.size(); ++i) {
Coordinate point = points[i];
if (point.row > furthestStart && point.col > furthestEnd) {
ranges.emplace_back(point.row, point.col);
furthestStart = point.row;
furthestEnd = point.col;
}
}
ranges.push_back({(long long)1e15, (long long)1e15});
long double lo = 0, hi = 5e13;
while (lo < hi - 0.0001) {
long double penalty = std::floor((hi + lo) / 2.0);
ConvexHull hull;
std::vector<long long> cnt;
hull.insert(Parabola{(long double)ranges[0].start, 0.0}, 0);
cnt.push_back(0);
for (size_t range = 0; range < ranges.size() - 1; ++range) {
auto [from, best] = hull.min(ranges[range].end + 1);
hull.insert(Parabola{(long double)ranges[range + 1].start, (long double)best - std::pow(std::max(0ll, ranges[range].end - ranges[range + 1].start + 1), 2) + penalty}, cnt[from] + 1);
cnt.push_back(cnt[from] + 1);
}
if (cnt.back() >= k) {
// std::cout << "if we penalise by " << penalty << ", we want to take " << cnt.back() << '\n';
lo = penalty + 1;
// std::cout << "update lo\n";
} else {
hi = penalty;
// std::cout << "update hi\n";
}
}
long double penalty = hi - 1;
long double ans = 0;
{
ConvexHull hull;
std::vector<long long> cnt;
hull.insert(Parabola{(long double)ranges[0].start, 0.0}, 0);
cnt.push_back(0);
for (size_t range = 0; range < ranges.size() - 1; ++range) {
auto [from, best] = hull.min(ranges[range].end + 1);
hull.insert(Parabola{(long double)ranges[range + 1].start, (long double)best - std::pow(std::max(0ll, ranges[range].end - ranges[range + 1].start + 1), 2) + penalty}, cnt[from] + 1);
cnt.push_back(cnt[from] + 1);
ans = best + penalty;
}
}
// std::cout << penalty << '\n';
return ans - std::min(k, (int)ranges.size() - 1) * penalty;
}
