| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 328835 | tnk2908 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// main.cpp
// aliens
//
// Created by Trần Nam Khánh on 11/18/20.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ed
{
long long a,b,minsq;
};
struct pt
{
long long r,c;
};
vector<ed>ch;
vector<pt>a,b;
vector<pair<long long,long long> >g;
long long n,m,k;
long long 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(long long x,long long y,long long 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);
}
long long dis(long long x,ed a,ed b)
{
//(b.b-a.b)/(a.a-b.a)
return (b.b-a.b)-x*(a.a-b.a);
}
pair<long long,long long> cal(long long c){
g.clear();
g.resize(n+1);
ch.clear();
g[0]={0,0};
long long l=0;
for(long long i=1;i<=n;i++)
{
long long X=a[i].c;
while(l+1<ch.size()&&dis(X,ch[l],ch[l+1])<0)
{
l++;
}
long long 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];
}
long long cmp(pt a,pt b)
{
return (a.c<b.c)||(a.c==b.c&&a.r<b.r);
}
long long cal2()
{
long long lo=0,hi=m*m,ans=0;
while(lo<hi)
{
long long mid=(lo+hi+1)>>1;
pair<long long,long long>tmp=cal(mid);
if(tmp.second>=k)
{
lo=mid;
}else hi=mid-1;
}
ans=cal(lo).first-k*lo;
if(lo<m*m)ans=min(ans,cal(lo+1).first-k*(lo+1))
return ans;
}
int64_t take_photos(int N,int M,int K,vector<int> r,vector<int> c) {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
n=N;m=M;k=K;
a.resize(n+1);
for(long long i=1;i<=n;i++)
{
a[i].r=r[i-1];
a[i].c=c[i-1];
if(a[i].r>a[i].c)
{
swap(a[i].r,a[i].c);
}
}
sort(a.begin()+1,a.end(),cmp);
for(long long 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(long long i=0;i<b.size();i++)
{
a[i+1]=b[i];
}
a[0].r=-1;
a[0].c=-1;
n=(long long)b.size();
k=min(k,n);
return cal2();
}
/*
3 7 2
0 3
4 6
3 4
*/