| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1230799 | changhw | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false), cin.tie(NULL)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
// convex hull trick
struct CHT{
// y = ax + b
struct line{
ll a, b, cnt;
ll eval(ll x) const {
return a*x + b;
}
};
deque<line> dq;
// a와 b의 교점이 c의 교점보다 오른쪽에 있으면 true
static bool chk(line l1, line l2, line l3){
return (l2.b - l1.b) * (l1.a - l3.a) >= (l3.b - l1.b) * (l1.a - l2.a);
}
void insert(ll a, ll b, ll cnt){
line l = {a, b, cnt};
while(dq.size() >= 2 && chk(dq[dq.size() - 2], dq[dq.size() - 1], l))
dq.pop_back();
dq.push_back(l);
}
pll query(ll x){
while(dq.size() >= 2 && dq[0].eval(x) >= dq[1].eval(x))
dq.pop_front();
return {dq[0].eval(x), dq[0].cnt};
}
};
vector<pll> points;
// alien trick
vector<ll> dp(505050), cdp(505050);
ll cost(ll x){
ll ret = points[x+1].first * points[x+1].first;
if(x != -1) {
ll tmp = max(points[x].second - points[x + 1].first + 1, 0LL);
ret -= tmp * tmp;
}
return ret;
}
void solve(ll d){
ll n = points.size();
CHT cht;
ll a = -2 * points[0].first;
ll b = cost(-1) + d;
cht.insert(a, b, 0);
for(int i = 0; i < n; i++){
auto [val, cnt] = cht.query(points[i].second + 1);
dp[i] = val + (points[i].second + 1) * (points[i].second + 1);
cdp[i] = cnt + 1;
if(i == n-1) break;
a = -2 * points[i+1].first;
b = cost(i) + dp[i] + d;
cht.insert(a, b, cdp[i]);
}
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for(int i = 0; i < n; i++){
int x = r[i], y = c[i];
if(x > y) swap(x, y);
points.emplace_back(x, y);
}
sort(points.begin(), points.end());
vector<pll> tp;
for(int i = 0; i < n; i++){
while(!tp.empty() && (tp.back().first == points[i].first))
tp.pop_back();
if(tp.empty() || tp.back().second < points[i].second)
tp.push_back(points[i]);
}
points = tp;
n = points.size();
k = min(n, k);
ll ans = 1e18;
ll begin = 0, end = 1e12;
while(begin < end){
ll mid = (begin + end) >> 1;
solve(mid);
if(cdp[n-1] <= k){
end = mid;
} else {
begin = mid + 1;
}
}
solve(begin);
ans = dp[n-1] - k * begin;
return ans;
}
int main() {
fastio;
int n, m, k;
cin >> n >> m >> k;
vector<int> r(n), c(n);
for(int i = 0; i < n; i++)
cin >> r[i] >> c[i];
cout << take_photos(n, m, k, r, c);
return 0;
}