| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 423028 | rumen_m | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 100005;
long long ans[maxn][2];
long long n,m,k;
vector <pair <long long,long long> > w,p;
bool cmp(pair <long long,long long> i, pair <long long,long long> j)
{
if(i.first==j.first)return i.second>j.second;
i.first<j.first;
}
struct CVH
{
vector < pair <long long,long long> > lines;
long long px;
CVH()
{
lines.clear();
lines.push_back({0,0});
px = 0;
}
double intersect( pair <long long, long long> l1, pair <long long,long long> l2)
{
return (double)(l2.second-l1.second)/(l1.first-l1.first);
}
void add_line(long long a, long long b)
{
while(lines.size()>=2)
{
auto l1 = lines.back();
auto l2 = lines[lines.size()-2];
if(intersect(l1,l2)>intersect(l2,{a,b}))lines.pop_back();
else
break;
}
lines.push_back({a,b});
}
pair <long long,long long> query(long long x)
{
while(px<lines.size()-1)
{
if(lines[px].first*x+lines[px].second>=lines[px+1].first*x+lines[px+1].second)px++;
}
return lines[px];
}
};
long long ANS[maxn];
long long take_photos(long long _n, long long _m, long long _k, std::vector<long long> _r, std::vector<long long> _c) {
n = _n;
m = _m;
k = _k;
w.resize(n);
long long i;
for(i=0;i<_r.size();i++)
{
w[i].first = min(_r[i],_c[i]);
w[i].second = max(_r[i],_c[i]);
}
sort(w.begin(),w.end(),cmp);
p.push_back({0,0});
for(i=0;i<n;i++)
{
if(p.back().first<=w[i].first&&w[i].second<=p.back().second)continue;
p.push_back(w[i]);
}
CVH u,v;
for(long long j = 1; j<=k; j++)
{
u = CVH();
for(long long i=1;i<p.size();i++)
{
//cout <<j <<" :: "<<i<<" :::: "<<p[i].first<<" "<<p[i].second<<endl;
auto d = u.query(p[i].second);
long long ans = d.first*p[i].second+d.second+p[i].second*p[i].second;
long long M = -2*(p[i].first-1);
long long B = ANS[i] + (p[i].first-1)*(p[i].first-1) - max((long long) 0,p[i-1].second-p[i].first+1)* max((long long)0,p[i-1].second-p[i].first+1);
//cout<<M<<" "<<B<<endl;
u.add_line(M,B);
ANS[i] = ans;
//cout<<"&& "<<i<<" "<<ANS[i]<<endl;
}
}
// cout<<ANS[p.size()-1]<<endl;
return ANS[p.size()-1];
}