| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 165894 | Segtree | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include"aliens.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 50010
vector<ll> l,r;
ll Tei(int i){
ll tei=l[i]*l[i];
tei-=max(0LL,r[i]-l[i])*max(0LL,r[i]-l[i]);
return tei;
}
namespace cht{
struct line{
ll a,b;
line(ll a,ll b){
this->a=a,this->b=b;
}
ll f(ll x){
return a*x+b;
}
};
long double crox(line a,line b){
return (long double)(b.b-a.b)/(long double)(a.a-b.a);
}
ll p;
vector<line> v;
void add(ll a,ll b){
if(b>=1e17)return;
line c=line(a,b);
while(v.size()>=2){
if(crox(v[v.size()-2],v[v.size()-1])>crox(v[v.size()-1],c)){
v.pop_back();
chmin(p,(ll)v.size()-1);
}
else break;
}
v.push_back(c);
}
ll qry(ll x){
if(v.size()==0)return 1e17;
while(p+1<v.size()){
if(crox(v[p],v[p+1])<(long double)x)p++;
else break;
}
return v[p].f(x);
/*ll ans=1e17;
for(auto t:v)chmin(ans,t.f(x));
return ans;*/
}
void init(){
v.clear();
p=0;
}
};
ll dp[N],cop[N];
ll take_photos(int n,int m,int K,vector<int> R,vector<int> C){
vector<P> v;
for(int i=0;i<n;i++){
if(R[i]>C[i])swap(R[i],C[i]);
v.push_back(make_pair((ll)R[i],(ll)-C[i]));
}
sort(v.begin(),v.end());
ll rnd=-1;
r.push_back(-1);
for(auto p:v){
ll x=p.first,y=-p.second+1;
if(y<=rnd)continue;
rnd=y;
l.push_back(x);
r.push_back(y);
}
n=l.size();
if(n==1)return (r[1]-l[0])*(r[1]-l[0]);
dp[0]=Tei(0);
ll ans=1e17;
for(int k=1;k<=K;k++){
cht::init();
for(int i=0;i<=n;i++)cop[i]=1e17;
for(int i=1;i<=n;i++){
cht::add(-2*l[i-1],dp[i-1]);
chmin(cop[i],cht::qry(r[i])+r[i]*r[i]);
/*for(int j=0;j<i;j++){
chmin(dp[i][k],dp[j][k-1]-2*r[i]*l[j]+r[i]*r[i]);
}*/
if(i==n)chmin(ans,cop[i]);
cop[i]+=Tei(i);
//cout<<i<<" "<<k<<" "<<dp[i][k]<<endl;
}
for(int i=0;i<=n;i++)dp[i]=cop;
}
return ans;
}