| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 522419 | lohacho | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
const int NS = (int)2e5 + 4;
int n;
vector<int> line[NS];
int f, r;
int cross(vector<int> x, vector<int> y){
int val = (x[1] - y[1]) / (y[0] - x[0]);
return val + (val >= 0 && (x[1] - y[1]) % (y[0] - x[0]) ? 1 : 0);
}
void push(int a, int b, int c){
while(f + 1 < r && cross({a, b}, line[r - 1]) <= cross(line[r - 1], line[r - 2])) --r;
line[r++] = {a, b, c};
}
pair<int, int> get(int x){
while(f + 1 < r && line[f][0] * x + line[f][1] >= line[f + 1][0] * x + line[f + 1][1]) ++f;
return {line[f][0] * x + line[f][1], line[f][2]};
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<pair<int, int>> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
if(a[i].first > a[i].second){
swap(a[i].first, a[i].second);
}
}
sort(a.begin(), a.end());
vector<pair<int, int>> stk = {a[0]};
for(int i = 1; i < n; ++i){
if(stk.back().first == a[i].first) ma(stk.back().second, a[i].second);
else if(stk.back().second < a[i].second) stk.push_back(a[i]);
}
a = stk; n = (int)a.size();
int low = (int)-1e13, high = (int)1e13;
auto sol = [&](int pl)->pair<int, int>{
f = r = 0;
vector<pair<int, int>> dp(n);
push(-(a[0].first - 1) * 2 * 2, (a[0].first - 1) * (a[0].first - 1) * 2, 0);
for(int i = 0; i < n; ++i){
auto rv = get(a[i].second);
dp[i] = {rv.first + a[i].second * a[i].second * 2 + pl, rv.second + 1};
auto nsame = 0;
if(i + 1 < n && a[i + 1].first <= a[i].second){
nsame = (a[i].second - a[i + 1].first + 1) * (a[i].second - a[i + 1].first + 1);
}
if(i + 1 < n) push(-(a[i + 1].first - 1) * 2 * 2, ((a[i + 1].first - 1) * (a[i + 1].first - 1) - nsame) * 2 + dp[i].first, dp[i].second);
}
return dp[n - 1];
};
mi(k, n);
while(low < high){
int mid = low + high >> 1;
auto rv = sol(mid * 2 + 1);
//cout << low << ' ' << high << ' ' << mid << ' ' << rv.first << ' ' << rv.second << endl;
if(rv.second <= k){
high = mid;
}
else{
low = mid + 1;
}
}
low = low * 2;
auto rv = sol(low);
//cout << rv.first << ' ' << rv.second << ' ' << low << endl;
cout << ((rv.first - k * low) >> 1) << '\n';
return 0;
}