#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long lint; typedef pair<lint, lint> pi; vector<pi> v; vector<vector<lint>> dp; struct cht{ vector<pi> v; void clear(){ v.clear(); } long double cross(pi a, pi b){ return ((long double)(b.second - a.second) / (b.first - a.first)); } void add_line(int x, lint y){ while(v.size() >= 2 && cross(v[v.size()-2], v.back()) > cross(v.back(), pi(x, y))){ v.pop_back(); } v.push_back({x, y}); } lint query(int x){ int s = 0, e = v.size()-1; auto f = [&](int p){ return v[p].first * x + v[p].second; }; while(s != e){ int m = (s+e)/2; if(f(m) <= f(m+1)) e = m; else s = m+1; } return f(s); } }cht; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<pi> w; for(int i=0; i<n; i++){ if(r[i] > c[i]) swap(r[i], c[i]); w.push_back({r[i]-1, c[i]}); } sort(w.begin(), w.end(), [&](const pi &a, const pi &b){ return pi(a.first, -a.second) < pi(b.first, -b.second); }); for(auto &i : w){ if(v.empty() || v.back().second < i.second){ v.push_back(i); } } dp.resize(k+1); for(auto &i : dp) i.resize(v.size() + 1); dp[0][0] = 0; for(int i=1; i<=v.size(); i++){ dp[0][i] = 1e18; } for(int i=1; i<=k; i++){ cht.clear(); for(int j=1; j<=v.size(); j++){ cht.add_line(2 * v[j-1].first, dp[i-1][j-1] + 1ll * v[j-1].first * v[j-1].first); dp[i][j] = cht.query(-v[j-1].second) + 1ll * v[j-1].second * v[j-1].second; if(j != v.size()){ lint cost = max(0ll, v[j-1].second - v[j].first); dp[i][j] -= cost * cost; } } } return dp[k][v.size()]; }

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<=v.size(); i++){
                   ^
aliens.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1; j<=v.size(); j++){
                       ^
aliens.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j != v.size()){
                  ^