| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 525912 | songc | 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>
using namespace std;
typedef long long ll;
struct point{
ll x,y;
bool operator < (point a)const{
return y>a.y||(y==a.y&&x<a.x);
}
};
struct line{
ll a,b;
int c;
ll f(ll x){
return a*x+b;
}
};
vector<point> V;
set<point> S;
deque<line> DQ;
int N,K,cnt[100100];
ll M,dt[100100];
line getLine(int i,ll lm){
line ret;
ll c=V[i+1].y-1;
ret.a=-2*c*2;
ll over=V[i].x>=V[i+1].y?(V[i].x-V[i+1].y+1):0;
ret.b=(c*c+over*over)*2+dt[i]+lm;
ret.c=cnt[i];
return ret;
}
bool chk(line a,line b,line c){
return ((__int128)a.b-c.b)*(c.a-b.a)>=((__int128)b.b-c.b)*(c.a-a.a);
}
int CHT(ll lm){
DQ.clear();
DQ.push_back(getLine(0,lm));
for(int i=1;i<=N;i++){
while(DQ.size()>=2&&DQ[0].f(V[i].x)>=DQ[1].f(V[i].x)) DQ.pop_front();
dt[i]=DQ.front().f(V[i].x)+2*V[i].x*V[i].x;
cnt[i]=DQ.front().c+1;
line nx=getLine(i,lm);
while(DQ.size()>=2&&chk(DQ[DQ.size()-2],DQ[DQ.size()-1],nx)) DQ.pop_back();
DQ.push_back(nx);
}
return cnt[N];
}
int main(){
int i;
ll x,y;
scanf("%d %lld %d",&N,&M,&K);
for(i=0;i<N;i++){
scanf("%lld %lld",&x,&y);
x++,y++;
if(x<y) swap(x,y);
V.push_back({x,y});
}
sort(V.begin(),V.end(),[&](point a,point b){return a.x<b.x||(a.x==b.x&&a.y>b.y);});
for(auto &k:V){
while(!S.empty()&&*S.begin()<k) S.erase(S.begin());
S.insert(k);
}
V.clear();
V.push_back({0,0});
for(auto &k:S) V.push_back({k.x,k.y});
reverse(V.begin()+1,V.end());
N=V.size()-1;
K=min(K,N);
ll lo=0,hi=1000000000000ll;
ll ans=lo;
while(lo<=hi){
ll mid=(lo+hi)/2;
if(CHT(2*mid-1)>=K) ans=mid,lo=mid+1;
else hi=mid-1;
}
CHT(2*ans);
printf("%lld",(dt[N]-K*2*ans)/2);
return 0;
}