#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]; vector<pair<int, int>> useful = {{-1, -1}}; int N; bool case1(int i, int j, int k) { return (sq(useful[j + 1].y - 1) - sq(useful[i + 1].y - 1) + 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)) >= (useful[j + 1].y - useful[i + 1].y) * 2 * useful[k].x); } bool case2(int i, int j, int k) { return (sq(useful[j + 1].y - 1) - sq(useful[i + 1].y - 1) + 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)) * (useful[k + 1].y - useful[j + 1].y) < sq(useful[k + 1].y - 1) - sq(useful[j + 1].y - 1) + dp[k] - dp[j] + sq(max(useful[j].x - useful[j + 1].y + 1, 0)) - sq(max(useful[k].x - useful[k + 1].y + 1, 0)) * (useful[j + 1].y - useful[i + 1].y)); } void compute(int lambda, int k) { deque<int> dq; dq.push_back(0); for (int i = 1; i <= N; i++) { while (dq.size() > 1 && case1(dq[0], dq[1], i)) 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; while (dq.size() > 1 && case2(dq[dq.size() - 2], dq.back(), i)) dq.pop_back(); dq.push_back(i); } // cout << dp[N] - lambda * cnt[N] << ' ' << cnt[N] << '\n'; } 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() - 1; ll l = 0, u = (ll)m * m; while (l != u) { ll mid = (l + u + 1) / 2; // cout << l << ' ' << u << " | "; compute(mid, k); if (cnt[N] <= k) l = mid; else u = mid - 1; } compute(l, k); return dp[N] - l * cnt[N]; }