#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.y; } ll dp[100001], cnt[100001]{1}; vector<pair<int, int>> useful; 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 < useful.size(); 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; 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]); ll l = 0, u = INT_MAX; while (l != u) { ll mid = (l + u + 1) / 2; compute(mid, k); if (cnt[useful.size() - 1] <= k) l = mid; else u = mid - 1; } compute(l, k); return dp[useful.size() - 1] - l * cnt[useful.size() - 1]; }

aliens.cpp: In function 'void compute(int, int)':
aliens.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < useful.size(); i++) {
                     ~~^~~~~~~~~~~~~~~