| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 172819 | figter001 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll oo = 1e18;
int n,k;
vector<pair<int,int>> segments;
vector<ll> rem;
int cnt;
struct con{
int l,used;
ll prev;
con(int left,int uu,ll pp){
l = left;used = uu;prev = pp;
}
pair<ld,int> getcost(ld x){
ld d = l-x;
return {d*d + prev ,used};
}
ld tover(con rhs){
ld l1 = l,l2 = rhs.l;
ld c = prev - rhs.prev;
ld all = l1*l1 - l2 * l2 + c;
ld rem = 2 * l1 - 2 * l2;
all /= rem;
return all;
}
};
pair<ll,ll> calc(ll cst){
pair<ll,int> curbest = {0,0};
int fptr=0,bptr=0;
vector<con> bag(cnt+2,con(0,0,0));
for(int i=0;i<cnt;i++){
int l = segments[i].first;
int r = segments[i].second;
con nxt = con(l-1,curbest.second+1,curbest.first + cst-rem[i]);
while(bptr - fptr >= 2 && bag[bptr-2].tover(bag[bptr-1]) >= bag[bptr-2].tover(nxt))bptr--;
bag[bptr++] = nxt;
while(fptr + 1 < bptr && bag[fptr].getcost(r) >= bag[fptr+1].getcost(r))fptr++;
curbest = bag[fptr].getcost(r);
}
return curbest;
}
ll find_answer(){
ll md,lo=0,hi=1e11,lamda = -1;
pair<ll,ll> tst = calc(0);
if(tst.second <= k)return tst.first;
while(lo <= hi){
md = (lo + hi)/2;
ll used = calc(md).second;
if(used <= k){
hi = md-1;
lamda = md;
}else{
lo = md+1;
}
}
assert(lamda != -1);
pair<ll,ll> ans = calc(lamda);
return ans.first - lamda * k;
}
ll solve(int N,int m,int K,vector<pair<int,int>> a){
n = N;k = K;
vector<pair<int,int>> tmp;
for(int i=0;i<n;i++){
int r = a[i].first;
int c = a[i].second;
tmp.push_back({max(r,c) , min(r,c)});
}
sort(tmp.begin(),tmp.end());
set<pair<int,int>> st;
for(int i=0;i<n;i++){
int l = tmp[i].second;
int r = tmp[i].first;
while(st.size() && -st.begin()->first >= l){
st.erase(st.begin());
}
st.insert({-l,r});
}
while(st.size()){
pair<int,int> it = *st.begin();
st.erase(st.begin());
it.first = -it.first;
// cout << it.first << ' ' << it.second << endl;
segments.push_back(it);
}
sort(segments.begin(),segments.end());
cnt = segments.size();
rem.resize(cnt);
for(int i=1;i<cnt;i++){
int fr = segments[i].first;
int bf = segments[i-1].second;
if(bf >= fr){
rem[i] = bf - fr + 1;
rem[i] *= rem[i];
}
}
ll ans = find_answer();
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout << fixed;
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
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;
cout << solve(n,m,k,a) << endl;
}