#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
1804 KB |
Output is correct |
2 |
Correct |
106 ms |
1920 KB |
Output is correct |
3 |
Correct |
86 ms |
1836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
92 ms |
1920 KB |
Output is correct |
2 |
Correct |
94 ms |
1980 KB |
Output is correct |
3 |
Correct |
95 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
1948 KB |
Output is correct |
2 |
Correct |
99 ms |
1948 KB |
Output is correct |
3 |
Correct |
96 ms |
1956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
84 ms |
1920 KB |
Output is correct |
2 |
Correct |
95 ms |
1980 KB |
Output is correct |
3 |
Correct |
89 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
1924 KB |
Output is correct |
2 |
Correct |
93 ms |
1948 KB |
Output is correct |
3 |
Correct |
91 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
1948 KB |
Output is correct |
2 |
Correct |
91 ms |
1920 KB |
Output is correct |
3 |
Correct |
90 ms |
1920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
1920 KB |
Output is correct |
2 |
Correct |
86 ms |
1828 KB |
Output is correct |
3 |
Correct |
88 ms |
1808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
1920 KB |
Output is correct |
2 |
Correct |
95 ms |
1952 KB |
Output is correct |
3 |
Correct |
87 ms |
1948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
80 ms |
1956 KB |
Output is correct |
2 |
Correct |
96 ms |
1988 KB |
Output is correct |
3 |
Correct |
98 ms |
1948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
1964 KB |
Output is correct |
2 |
Correct |
92 ms |
1920 KB |
Output is correct |
3 |
Correct |
95 ms |
2000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
1940 KB |
Output is correct |
2 |
Correct |
94 ms |
1940 KB |
Output is correct |
3 |
Correct |
97 ms |
1940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
1940 KB |
Output is correct |
2 |
Correct |
93 ms |
1940 KB |
Output is correct |
3 |
Correct |
95 ms |
1940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
91 ms |
1940 KB |
Output is correct |
2 |
Correct |
96 ms |
1940 KB |
Output is correct |
3 |
Correct |
95 ms |
1940 KB |
Output is correct |