이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<ii> vii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define float long double
deque<iii> dq;
ii dp[100005];
int f(iii line, int x) {
return line.fi.fi * x + line.fi.se;
}
ii query(int x) {
while(dq.size() > 1) {
if(f(dq[0], x) < f(dq[1], x)) dq.pop_front();
else break;
}
return mp(f(dq[0], x),dq[0].se);
}
float intersect(int a, int b, int c, int d) {
return (float)(d - b) / (a - c);
}
float intersect(iii p1, iii p2) {
return intersect(p1.fi.fi, p1.fi.se, p2.fi.fi, p2.fi.se);
}
void ins(int m, int c, int idx) {
iii line = mp(ii(m, c),idx);
while(dq.size() > 1) {
int s = dq.size();
if(intersect(dq[s - 1], line) < intersect(dq[s - 2], line)) dq.pop_back();
else break;
}
dq.push_back(line);
}
ii getCst(int n, vii &pts, int cst) {
dq.clear();
int prvCst = 0, prvSz = 0;
REP(i,0,n){
int m = 2*pts[i].fi, c = 2*pts[i].fi-pts[i].fi*pts[i].fi-prvCst;
if(i){
c+=max((int)0,pts[i-1].se-pts[i].fi+1)*max((int)0,pts[i-1].se-pts[i].fi+1);
}
ins(m,c,prvSz);
prvCst=(pts[i].se+1)*(pts[i].se+1)-query(pts[i].se).fi+cst;
prvSz=query(pts[i].se).se+1;
}
return mp(prvCst,prvSz);
}
bool comp(ii a, ii b) {
if(a.fi==b.fi) return a.se>b.se;
return a.fi<b.fi;
}
long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
ii pts[n];
REP(i,0,n)if(r[i]>c[i])swap(r[i],c[i]);
REP(i,0,n) pts[i]=mp(r[i],c[i]);
sort(pts,pts+n,comp);
vector<ii> imptPts;
REP(i,0,n) if(imptPts.empty()||pts[i].se>imptPts.back().se) imptPts.pb(pts[i]);
int relN = imptPts.size();
int l=-1,h=(int)m*(int)m;
while(h-l>1){
int lambda=(l+h)/2;
if(getCst(relN,imptPts,lambda).se<=(int)k)h=lambda;
else l=lambda;
}
return (long long)getCst(relN,imptPts,h).fi-(int)k*h;
}
# | 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... |