| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 579358 | perchuts | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
using namespace std;
// #include "aliens.h"
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<pair<ll,ll>>pareto;
bool pode(pair<ll,ll>x,pair<ll,ll>z,pair<ll,ll>y){
if(((z.f-y.f)>0&&(x.f-y.f)>0)||((z.f-y.f)<0&&(x.f-y.f)<0))return (y.s-x.s)*(z.f-y.f)>=(y.s-z.s)*(x.f-y.f);
return (y.s-x.s)*(z.f-y.f)<=(y.s-z.s)*(x.f-y.f);
}
pair<ll,ll> solve(ll lambda){
//CHT
deque<pair<pair<ll,ll>,ll>>lines;
int n = sz(pareto);
lines.push_back({{2ll*pareto[0].f,pareto[0].f*pareto[0].f-2ll*pareto[0].f},0});//dummy point
// printf("+ %d %d\n",lines.back().f.f,lines.back().f.s);
int it = 0;
for(int i=0;i<n;++i){
auto [x,y] = pareto[i];
ckmin(it,sz(lines)-1);
while(it+1<sz(lines)&&y*(lines[it+1].f.f-lines[it].f.f)>=lines[it+1].f.s-lines[it].f.s)
++it;
// printf("%d:%d\n",i,it);
ll dpi = lines[it].f.f*(-y)+lines[it].f.s + y*y + 1ll + 2ll*y + lambda;
ll qnt = lines[it].s + 1ll;
// printf("%d\n",dpi-qnt*lambda);
if(i!=n-1){
dpi += pareto[i+1].f*pareto[i+1].f - 2*pareto[i+1].f
- (max(0ll,y-pareto[i+1].f+1ll))*(max(0ll,y-pareto[i+1].f+1ll));
pair<pair<ll,ll>,ll>atual = {{2*pareto[i+1].f,dpi},qnt};
while(sz(lines)>=2&&pode(atual.f,lines[sz(lines)-2].f,lines.back().f)){
// printf("- %lld %lld\n",lines.back().f.f,lines.back().f.s);
lines.pop_back();
}
lines.pb(atual);
// printf("+ %lld %lld\n",lines.back().f.f,lines.back().f.s);
}else return {dpi,qnt};
}
return {0,0};
}
ll take_photos(int n, int m, int k, vector<int> r1, vector<int> c) {
vector<ii>v(n);
for(int i=0;i<n;++i){
++r1[i], ++c[i];
if(r1[i]<=c[i])v[i] = {r1[i],c[i]};
else v[i] = {c[i],r1[i]};
}
sort(all(v));
for(int i=0;i<n;++i){
if(pareto.empty()||pareto.back().second<v[i].s){
if(!pareto.empty()&&pareto.back().first==v[i].f)pareto.pop_back();
pareto.push_back(v[i]);
}
}
//Lagrange opt.
ll l = 0, r = 1e12;//max delta = 1e12 porque m<=1e6, logo lambda <= 1e12
while(l<r){
ll md = (l+r)/2;
pair<ll,ll>cur = solve(md);
if(cur.s>k)l = md+1ll;
else r = md;
}
pair<ll,ll>res = solve(r);
return res.f-res.s*r;
}
int main() {
int n, m, k;
assert(3 == scanf("%d %d %d", &n, &m, &k));
std::vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
assert(2 == scanf("%d %d", &r[i], &c[i]));
}
long long ans = take_photos(n, m, k, r, c);
printf("%lld\n", ans);
return 0;
}