| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 765115 | oneloveforever | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<ll,ll>
const ll inf=1e18+7;
ll n,m,k;
vector<ii>poll;
ll power(ll x)
{
return x*x;
}
struct node
{
ll x,y,num;
node(ll _x=0,ll _y=0,ll _num=0)
{
x=_x,y=_y,num=_num;
}
};
bool check(node a,node b,node c)
{
//double value_x=(b.y-a.y)/(a.x-b.x);
//double value_y=(c.y-b.y)/(b.x-c.x);
ll value_x=(b.y-a.y)*(b.x-c.x);
ll value_y=(c.y-b.y)*(a.x-b.x);
return (value_x<=value_y);
}
ii get(ll x,node need)
{
ii ans;
ans.x=need.x*x+need.y;
ans.y=need.num;
return ans;
}
ii calc(ll constant)
{
ii trace=make_pair(0,0);
deque<node>convex;
for(ll i=n-1;i>=0;i--)
{
ll used=power(max((ll)0,poll[i].y-poll[i+1].x+1));
node path=node(-2*(poll[i].y+1),trace.x+power(poll[i].y+1)-used,trace.y);
while(convex.size()>=2&&!check(convex[convex.size()-2],convex[convex.size()-1],path))convex.pop_back();
convex.push_back(path);
ll C=poll[i].x;
while(convex.size()>=2&&get(C,convex[0])>=get(C,convex[1]))convex.pop_front();
ii need=get(C,convex[0]);
//cout<<need.x<<" "<<need.y<<endl;
trace.x=need.x+power(poll[i].x)+constant;
trace.y=need.y+1;
//cout<<trace.x<<" "<<trace.y<<" "<<constant<<endl;
//cout<<trace.x<<" "<<trace.y<<" "<<power(poll[i].x)+constant<<" "<<need.x<<" "<<need.y<<endl;
}
return trace;
}
bool cmp(ii a,ii b)
{
if(a.x==b.x)return a.y>b.y;
return a.x<b.x;
}
ll take_photos(ll _n,ll _m,ll _k,vector<ll>r,vector<ll>c)
{
n=_n;
m=_m;
k=_k;
vector<ii>block;
for(ll i=1;i<=n;i++)
{
ll x=min(r[i-1],c[i-1]);
ll y=max(r[i-1],c[i-1]);
block.push_back({x,y});
}
sort(block.begin(),block.end(),cmp);
block.resize(unique(block.begin(),block.end())-block.begin());
vector<ll>q;
for(ll i=n-1;i>=0;i--)
{
while(!q.empty()&&block[q.back()].y<=block[i].y)q.pop_back();
q.push_back(i);
}
reverse(q.begin(),q.end());
for(ll index:q)poll.push_back({block[index].x,block[index].y});
n=(ll)poll.size();
poll.push_back({m,m});
//for(ii node:poll)cout<<node.x<<" "<<node.y<<endl;
k=min(k,n);
ll x=0;
ll y=m*m+1;
ll res=m*m;
for(ll cnt=0;cnt<=50;cnt++)
{
ll mid=(x+y)/2;
ii ans=calc(mid);
if(ans.y<=k)
{
res=mid;
y=mid;
}
else x=mid;
}
ii ans=calc(res);
return ans.x-k*res;
}