#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 = {{0, 0}}; int N; bool case1(int i, int j, int k) { return (2 * useful[k].y * (useful[j + 1].x - useful[i + 1].x) <= dp[j] - dp[i] + sq(useful[j + 1].x - 1) + sq(useful[i + 1].x - 1) - sq(max(0, useful[j].y - useful[j + 1].x + 1)) + sq(max(0, useful[i].y - useful[i + 1].x + 1))); } bool case2(int i, int j, int k) { return ((dp[k] - dp[j] + sq(useful[k + 1].x - 1) + sq(useful[j + 1].x - 1) - sq(max(0, useful[k].y - useful[k + 1].x + 1)) + sq(max(0, useful[j].y - useful[j + 1].x + 1))) * (useful[j + 1].x - useful[i + 1].x) <= (dp[j] - dp[i] + sq(useful[j + 1].x - 1) + sq(useful[i + 1].x - 1) - sq(max(0, useful[j].y - useful[j + 1].x + 1)) + sq(max(0, useful[i].y - useful[i + 1].x + 1))) * (useful[k + 1].x - useful[j + 1].x)); } void compute(ll 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); // if (i == N) cout << opt << ' ' << dp[i] << ' ' << dp[i] - lambda * cnt[i] << ' ' << cnt[i] << '\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 + 1, y + 1}); } sort(points.begin(), points.end(), cmp); for (int i = 0; i < n; i++) if (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) / 2; // cout << l << ' ' << u << " |\n"; compute(mid, k); // cout << '\n'; if (cnt[N] > k) l = mid + 1; else u = mid; } compute(l, k); return dp[N] - l * cnt[N]; }