| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 328811 | tnk2908 | 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.
//
// main.cpp
// aliens
//
// Created by Trần Nam Khánh on 11/18/20.
//
#include <iostream>
#include <vector>
using namespace std;
struct ed
{
int a,b,minsq;
};
struct pt
{
int r,c;
};
vector<ed>ch;
vector<pt>a,b;
vector<pair<int,int> >g;
int n,m,k;
int check(ed a,ed b,ed c)
{
//(b.b-a.b)/(a.a-b.a)
//(c.b-a.b)/(a.a-c.a)
return (b.b-a.b)*(a.a-c.a)>=(c.b-a.b)*(a.a-b.a);
}
void add(int x,int y,int mi)
{
ed a;
a.a=x;
a.b=y;
a.minsq=mi;
while(ch.size()>=2&&check(ch[ch.size()-2],ch[ch.size()-1],a))
{
ch.pop_back();
}
ch.push_back(a);
}
int dis(int x,ed a,ed b)
{
//(b.b-a.b)/(a.a-b.a)
return (b.b-a.b)-x*(a.a-b.a);
}
pair<int,int> cal(int c){
g.clear();
g.resize(n+1);
ch.clear();
g[0]={0,0};
int l=0;
for(int i=1;i<=n;i++)
{
int X=a[i].c;
while(l+1<ch.size()&&dis(X,ch[l],ch[l+1])<0)
{
l++;
}
int tmp=(a[i].c-a[i].r+1)*(a[i].c-a[i].r+1)+g[i-1].first;
if(a[i-1].c>=a[i].r)
{
tmp-=(a[i-1].c-a[i].r+1)*(a[i-1].c-a[i].r+1);
}
g[i].first=tmp+c;
g[i].second=g[i-1].second+1;
if(l<ch.size()&&g[i].first>ch[l].a*a[i].c+ch[l].b+a[i].c*a[i].c+c)
{
g[i].first=ch[l].a*a[i].c+ch[l].b+a[i].c*a[i].c+c;
g[i].second=ch[l].minsq+1;
if(l+1<ch.size()&&dis(X,ch[l],ch[l+1])==0)
{
g[i].second=min(g[i].second,ch[l+1].minsq+1);
}
}else if(l<ch.size()&&g[i].first==ch[l].a*a[i].c+ch[l].b+a[i].c*a[i].c+c)
{
g[i].second=min(g[i].second,ch[l].minsq+1);
}
add(-2*a[i].r+2,tmp+2*a[i].r*a[i].c-a[i].c*a[i].c-2*a[i].c,g[i-1].second);
}
return g[n];
}
int cmp(pt a,pt b)
{
return (a.c<b.c)||(a.c==b.c&&a.r<b.r);
}
void cal2()
{
int lo=0,hi=m*m,ans=0;
while(lo<hi)
{
int mid=(lo+hi+1)>>1;
pair<int,int>tmp=cal(mid);
if(tmp.second>=k)
{
lo=mid;
}else hi=mid-1;
}
ans=cal(lo).first-k*lo;
cout<<ans<<endl;
}
int main(int argc, const char * argv[]) {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
a.resize(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i].r>>a[i].c;
if(a[i].r>a[i].c)
{
swap(a[i].r,a[i].c);
}
}
sort(a.begin()+1,a.end(),cmp);
for(int i=1;i<=n;i++)
{
while(b.size()!=0&&(a[i].r<=b.back().r))
{
b.pop_back();
}
b.push_back(a[i]);
}
a.resize(b.size()+1);
for(int i=0;i<b.size();i++)
{
a[i+1]=b[i];
}
a[0].r=-1;
a[0].c=-1;
n=(int)b.size();
cal2();
return 0;
}
/*
3 7 2
0 3
4 6
3 4
*/