This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using flt=double;
struct fn {
flt x;
int j, c;
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, K;
cin>>N>>K;
flt l=0, r=2;
cout<<fixed<<setprecision(9);
auto f=[&](flt m, bool skip=true) {
deque<fn> Q;
Q.push_back({0., 0, 0});
for(int i=1; i<=N; i++) {
auto f=[&](fn& a) {
return a.x-flt(a.j)/i+1;
};
flt last=f(Q.front()), prv;
while(Q.size()>1 && last<=(prv=f(*++Q.begin())))
last=prv, Q.pop_front();
fn t{last-=m, i, Q.front().c+1};
if(t.c>K && skip)
return make_pair(t.c, t.x);
while(Q.size() && last>=(prv=f(Q.back())))
Q.pop_back();
Q.push_back(t);
}
fn t=Q.back();
return make_pair(t.c, t.x+K*m);
};
while(r-l>1e-12) {
flt m=(l+r)/2;
auto[k,x]=f(m);
if(k<K) r=m;
else if(k>K) l=m;
else { cout<<x; return 0; }
}
cout<<f((l+r)/2, false).second;
}
# | 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... |
# | 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... |
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |