#include "aliens.h" #include <bits/stdc++.h> typedef long long ll; using namespace std; #define x first #define y second ll sq(ll a) { return a * a; } bool cmp(pair<int, int> a, pair<int, int> b) { if (a.x == b.x) return (a.y > b.y); return a.x < b.x; } ll dp[100001], cnt[100001]{1}; vector<pair<int, int>> useful; int N; float slope(int i, int j) { return (sq(useful[j + 1].y) - sq(useful[i + 1].y) + dp[j] - dp[i] + sq(max(useful[i].x - useful[i + 1].y + 1, 0)) - sq(max(useful[j].x - useful[j + 1].y + 1, 0))) / (float)(useful[j + 1].y - useful[i + 1].y); } void compute(int lambda, int k) { deque<int> dq; dq.push_back(0); dp[0] = lambda + sq(useful[0].y - useful[0].x + 1); for (int i = 1; i < N; i++) { while (dq.size() > 1 && slope(dq[0], dq[1]) >= 2 * (useful[i].x + 1)) dq.pop_front(); int opt = dq.front(); dp[i] = sq(useful[i].y - useful[opt + 1].x + 1) + dp[opt] - sq(max(0, useful[opt].y - useful[opt + 1].x + 1)) + lambda; cnt[i] = cnt[opt] + 1; if (dp[i] >= sq(useful[i].y - useful[0].x + 1) + lambda) { dp[i] = sq(useful[i].y - useful[0].x + 1) + lambda; cnt[i] = 1; } while (dq.size() > 1 && slope(dq[dq.size() - 2], dq.back()) <= slope(dq.back(), i)) dq.pop_back(); dq.push_back(i); } } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector<pair<int, int>> points; for (int i = 0; i < n; i++) { int x = r[i], y = c[i]; if (x > y) swap(x, y); points.push_back({x, y}); } sort(points.begin(), points.end(), cmp); for (int i = 0; i < n; i++) if (useful.empty() || useful.back().y < points[i].y) useful.push_back(points[i]); N = useful.size(); ll l = 0, u = (ll)m * m; while (l != u) { ll mid = (l + u) / 2; compute(mid, k); if (cnt[N - 1] <= k) u = mid; else l = mid + 1; } compute(l, k); return dp[N - 1] - l * cnt[N - 1]; }