이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
typedef vector <int> vec;
const ll INF = 1e18;
int n,m,k;
pl a[100005],tmp[100005];
ll d[2][100005];
deque <pl> dq;
ld getX(pl x,pl y) {return (ld)(x.y-y.y)/(y.x-x.x);}
ll take_photos(int N,int M,int K,vec r,vec c) {
n = N, m = M, k = K;
for(int i = 0;i < n;i++) tmp[i] = {min(r[i],c[i])-1,-max(r[i],c[i])};
sort(tmp,tmp+n); n = 0;
int mx = -1;
for(int i = 0;i < N;i++) {
if(-tmp[i].y > mx) a[++n] = {tmp[i].x,-tmp[i].y}, mx = -tmp[i].y;
}
d[0][0] = 0;
for(int i = 1;i <= n;i++) d[0][i] = INF;
a[0] = {-10,-10};
ll ans = INF;
for(int j = 1;j <= k;j++) {
dq.clear();
d[j%2][0] = INF;
for(int i = 1;i <= n;i++) {
pl x = {a[i].x*-2,d[(j-1)%2][i-1]+a[i].x*a[i].x-max(0LL,a[i-1].y-a[i].x)*max(0LL,a[i-1].y-a[i].x)};
while(dq.size() > 1&&getX(dq[dq.size()-2],dq[dq.size()-1]) >= getX(dq[dq.size()-1],x)) dq.pop_back();
dq.push_back(x);
while(dq.size() > 1&&getX(dq[0],dq[1]) <= a[i].y) dq.pop_front();
d[j%2][i] = a[i].y*dq[0].x+dq[0].y+a[i].y*a[i].y;
}
ans = min(ans,d[j%2][n]);
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |