이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
pll point[100010], arr[100010];
int n, m, k, r;
LL la[100010], lb[100010], dp[100010];
int num[100010], dpnum[100010];
int sz, p;
double cross(int x, int y){return (double)(lb[y]-lb[x])/(la[x]-la[y]);}
void in(LL p, LL q){
la[sz]=p;
lb[sz]=q;
num[sz]=++r;
while(sz>1&&cross(sz-1,sz-2)>cross(sz-1,sz)){
la[sz-1]=la[sz];
lb[sz-1]=lb[sz];
num[sz-1]=num[sz];
sz--;
}
sz++;
}
LL query(LL x){
while(p+1<sz&&cross(p, p+1)<=x)p++;
return lb[p]+la[p]*x;
}
void get_dp(LL cc){
sz=p=r=0;
in(-2*arr[1].F, arr[1].F*arr[1].F);
dpnum[1]=1;
dp[1]=(arr[1].F-arr[1].S+1)*(arr[1].F-arr[1].S+1);
for(int i=2; i<=n; i++){
dp[i]=query(arr[i].S+1)+(arr[i].S+1)*(arr[i].S+1)-cc;
dpnum[i]=dpnum[num[p]]+1;
in(-2*arr[i].F, arr[i].S*arr[i].S+dp[i-1]);
}
}
LL Solve(){
LL l=0, r=(LL)m*m+2000;
while(l<r){
LL mid;
if(l+1==r)mid=r;
else mid=(l+r)/2+1;
get_dp(2*mid+1);
if(dpnum[n]<k)r=mid-1;
else l=mid;
}
get_dp(2*l+1);
int k1=dpnum[n];
LL p1=dp[n]+(LL)dpnum[n]*(2*l+1);
get_dp(2*l+3);
int k2=dpnum[n];
LL p2=dp[n]+(LL)dpnum[n]*(2*l+3);
return (p2*(LL)(k1-k)+p1*(LL)(k-k2))/(LL)(k1-k2);
}
LL take_photos(int _n, int _m, int _k, vector<int> rr, vector<int> c) {
n=_n, m=_m, k=_k;
for(int i=0; i<n; i++){
if(rr[i]>c[i])swap(rr[i], c[i]);
point[i+1]=mp((LL)rr[i]+1, (LL)c[i]+1);
}
sort(point+1, point+n+1);
LL maxx=0;
for(int i=1; i<=n; i++){
if(maxx<point[i].S){
maxx=point[i].S;
if(arr[r].F<point[i].F&&arr[r].S<point[i].S)arr[++r]=point[i];
else arr[r]=point[i];
}
}
n=r;
for(int i=1; i<=n; i++){
arr[i].F*=2;
arr[i].S*=2;
}
return Solve();
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/
# | 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... |