| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 217028 | Blagojce | 새로운 문제 (COCI19_akvizna) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;
struct line{
int K;
ld m, b;
bool isq;
ld x;
ld eval(ld X) const{
return X * m + b;
}
ld intersect(const line &l) const{
return 1.0 * (l.b - b) / (m - l.m);
}
bool operator < (const line &l) const{
if(l.isq) return x < l.x;
else return m > l.m;
}
};
set<line> hull;
typedef set<line>::iterator iter;
bool cPrev(iter it){
return it != hull.begin();
}
bool cNext(iter it){
return it != hull.end() && next(it) != hull.end();
}
bool bad(const line &l1, const line &l2, const line &l3){
return l1.intersect(l3) <= l1.intersect(l2);
}
bool bad(iter it){
return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}
iter update(iter it){
if(!cPrev(it)) return it;
ld x = prev(it)->intersect(*it);
line l = *it;
l.x = x;
it = hull.erase(it);
return hull.insert(it, l);
}
void addLine(ld m, ld b, int K){
line l;
l.K = K;
l.m = m, l.b = b, l.isq = false;
l.x = -inf;
iter it = hull.lower_bound(l);
it = hull.insert(it, l);
if(bad(it)){
hull.erase(it);
return;
}
while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
while(cNext(it) && bad(next(it))) hull.erase(next(it));
it = update(it);
if(cPrev(it)) update(prev(it));
if(cNext(it)) update(next(it));
}
pair<int,ld> query(ld x){
line q;
q.x = x;
q.isq = true;
iter it = --hull.lower_bound(q);
int K = it->K;
ld ret = it->eval(x);
it ++;
if(it != hull.end()){
ld ret2 = it->eval(x);
if(abs(ret - ret2) < eps){
K = min(K, it->K);
}
}
return {K, ret};
}
ld ANS;
int calculate(ld lambda, int N){
hull.clear();
addLine(0, 0, 0);
fr(i, 1, N){
pair<int, ld> best = query(-1.0/i);
ld currans = -best.nd + 1 - lambda;
addLine(-i, -currans, best.st + 1);
}
pair<int, ld> best = query(-1.0/N);
ANS = -best.nd + 1 - lambda;
return best.st + 1;
}
ld solve(int N, int K){
ld l = 0, r = 1;
ld best = 0;
fr(j, 0, 100){
ld mid = (l + r) / 2;
int i = calculate(mid, N);
if(i <= K){
best = mid;
r = mid-eps;
}
else{
l = mid + eps;
}
}
calculate(best, N);
return ANS + K*best;
}
int main()
{
int N, K;
cin >> N >> K;
cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
return 0;
}