이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double f;
//typedef __float128 f;
typedef pair<ll,ll> pll;
typedef pair<f,ll> pfl;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pfl> vp;
typedef vector<int> vi;
struct line {
f c;
f slope;
//pfl y() {return make_pair(c + (curr_x*slope), my_k);}
//pfl operator()(ll x) {return make_pair(c + ((f)x)*slope, my_k);}
pfl operator()(f x) {return make_pair(c + x*slope, my_k);}
ll my_k;
};
typedef vector<line> vl;
#define rep(a,b,c) for(ll a = b; a < c; a++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
pfl operator+ (pfl a, pfl b) {return mp(a.first+b.first,a.second+b.second);}
pfl _dp(f lambda);
void insert(line seg, ll l, ll r, ll idx);
pfl query(ll x, ll l, ll r, ll idx, f curr_x);
ll n;
ll k;
ll s;
vpll p;
vll h;
vp dp;
//f curr_x;
vl tree;
line inf;
long long take_photos(int N, int M, int K, vi R, vi C) {
k = K;
p.clear();
rep(i,0,N) {if (R[i] > C[i]) {swap(R[i],C[i]);}} // Flip over diagonal
rep(i,0,N) {p.pb(mp(C[i],-R[i]));}
sort(all(p)); // Sort in a way that makes worse points come before better points
rep(i,0,N) {
C[i] = p[i].first;
R[i] = -p[i].second;
}
/*cout << "C[i] R[i]" << endl;
rep(i,0,N) {cout << C[i] << " " << R[i] << endl;}*/
// C[i] is in increasing order
// R[i] is in decreasing order
// The first point is the optimal
p.clear();
p.pb(mp(-1,-1)); // thing....
rep(i,0,N) {
while ((C[i] >= p[sz(p)-1].first) && (R[i] <= p[sz(p)-1].second)) { // Prune bad points
p.pop_back();
}
p.pb(mp(C[i],R[i])); // Add points in (x,-y) format to p
}
/*cout << "points:" << endl;
rep(i,0,sz(p)) {cout << p[i].first << " " << p[i].second << endl;}*/
n = sz(p);
h.resize(n,0);
rep(i,0,n-1) {h[i] = p[i].first - p[i+1].second;}
// Prepare Li Chao tree
inf.c = f(10000000000000);
inf.slope = f(0);
s = 1;
ll tempppp = n-1;
for(; tempppp > 0; tempppp>>=1) {s <<= 1;}
/*cout << "h:" << endl;
rep(i,0,n) {cout << h[i] << " ";}
cout << endl;*/
/*rep(i,0,10) {cout << _dp(f(i)).first << endl;}*/
ll ans = 1000000000001;
f lo = f(0.0);
f hi = f(1000000000001);
f mid;
pfl curr;
rep(i,0,64) {
mid = (lo)/f(2) + (hi)/f(2);
//cout << mid << endl;
curr = _dp(mid);
//cout << (long double)(curr.first) << " " << curr.second << " " << (long double)(mid) << endl;
if (curr.second == min(k,n-1)) {
ans = llround(curr.first - mid*curr.second);
//cout << llround((long double)(curr.first - mid*curr.second)) << " " << (curr.first - mid*curr.second) << endl;
break;
} else if (curr.second > min(k,n-1)) {
lo = mid;
} else {
hi = mid;
/*ll tmp = round(curr.first - mid*(f(curr.second))); // Hotfix
ans = min(tmp, ans);*/
}
}
if (ans == 1000000000001) {ans = round(curr.first - mid*(f(k)));} // Based solution
//if (ans==-1) {ans = round(curr.first - mid*(f(curr.second)));}
//cout << n-1 << endl;
return ans;
}
pfl _dp(f lambda) {
// Initialize the Li Chao Tree
tree.clear();
tree.resize(2*s,inf);
dp.clear();
dp.resize(n,mp(f(10000000000000),0));
//dp[0] = mp(f( (p[0].first-p[0].second+1)*(p[0].first-p[0].second+1) ),1);
dp[0] = mp(f(0),0);
//cout << "built xd" << endl;
rep(i,0,n) {
/*rep(j,0,i) {
ll x_i = p[i].first;
ll x_j = p[j].first;
if (h[j] < 0) {
dp[i] = min(dp[i], dp[j] + mp(f( (x_i-x_j+h[j]+1)*(x_i-x_j+h[j]+1) ),1) + mp(lambda,0));
} else {
dp[i] = min(dp[i], dp[j] + mp(f( (x_i-x_j+h[j]+1)*(x_i-x_j+h[j]+1) - (h[j]+1)*(h[j]+1) ),1) + mp(lambda,0));
}
}*/
f curr_x = (f)p[i].first;
if (i!=0) dp[i] = mp(curr_x*curr_x,0) + query(i, 0, n, 1, curr_x) + mp(lambda,1); // wtf based
//cout << "i: " << i << " " << dp[i].first << " " << dp[i].second << endl;
line new_line;
new_line.my_k = dp[i].second; // include k xd
if (h[i] < 0) {
new_line.c = dp[i].first + curr_x*curr_x - 2*curr_x*(f)(h[i]+1) + (f)((h[i]+1)*(h[i]+1));
//new_line.slope = (f)(-2*(curr_x-h[i]-1));
} else {
new_line.c = dp[i].first + curr_x*curr_x - 2*curr_x*(f)(h[i]+1);
//new_line.slope = (f)(-2*(curr_x-h[i]-1));
}
new_line.slope = (f)(-2*(curr_x-h[i]-1));
insert(new_line, 0, n, 1);
}
/*cout << "dp: ";
rep(i,0,n) {cout << dp[i].first - lambda*dp[i].second << "," << dp[i].second << " ";}
cout << endl;*/
return dp[n-1];
}
void insert(line seg, ll l, ll r, ll idx) {
ll m = (l+r)/2;
f curr_x = (f)p[m].first;
if (l+1==r) {
if (tree[idx](curr_x) > seg(curr_x)) {swap(tree[idx],seg);}
return;
}
// make seg the worse one (ie the larger one)
if (tree[idx](curr_x) > seg(curr_x)) {swap(tree[idx],seg);}
// no early returns bc whatever
if (tree[idx].slope > seg.slope) {
// The better (smaller) one has larger slope, which means the worse (larger) will undercut it later. Hence rc
insert(seg, m, r, 2*idx + 1); // rc
} else {
// The better (smaller) one has smaller slopw, which means the worse (larger) will undercut it before. Hence lc
insert(seg, l, m, 2*idx); // lc
}
}
pfl query(ll x, ll l, ll r, ll idx, f curr_x) {
ll m = (l+r)/2;
if (l+1 == r) {return tree[idx](curr_x);}
if (x < m) {
return min(tree[idx](curr_x), query(x, l, m, 2*idx, curr_x)); // lc
} else {
return min(tree[idx](curr_x), query(x, m, r, 2*idx + 1, curr_x)); // rc
}
}
# | 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... |