# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
282657 |
2020-08-24T16:55:08 Z |
cgiosy |
Akvizna (COCI19_akvizna) |
C++17 |
|
86 ms |
1952 KB |
#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=1+1e-10;
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-10) {
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 |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
416 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
1792 KB |
Output is correct |
2 |
Correct |
79 ms |
1920 KB |
Output is correct |
3 |
Correct |
74 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
1920 KB |
Output is correct |
2 |
Correct |
86 ms |
1920 KB |
Output is correct |
3 |
Correct |
79 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
1792 KB |
Output is correct |
2 |
Correct |
82 ms |
1920 KB |
Output is correct |
3 |
Correct |
81 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
1920 KB |
Output is correct |
2 |
Correct |
77 ms |
1920 KB |
Output is correct |
3 |
Correct |
75 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
1920 KB |
Output is correct |
2 |
Correct |
80 ms |
1920 KB |
Output is correct |
3 |
Correct |
75 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
1920 KB |
Output is correct |
2 |
Correct |
77 ms |
1920 KB |
Output is correct |
3 |
Correct |
75 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
1920 KB |
Output is correct |
2 |
Correct |
74 ms |
1792 KB |
Output is correct |
3 |
Correct |
75 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
1920 KB |
Output is correct |
2 |
Correct |
81 ms |
1920 KB |
Output is correct |
3 |
Correct |
73 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
1920 KB |
Output is correct |
2 |
Correct |
77 ms |
1920 KB |
Output is correct |
3 |
Correct |
79 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
1920 KB |
Output is correct |
2 |
Correct |
75 ms |
1920 KB |
Output is correct |
3 |
Correct |
80 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
1920 KB |
Output is correct |
2 |
Correct |
79 ms |
1920 KB |
Output is correct |
3 |
Correct |
80 ms |
1952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
1920 KB |
Output is correct |
2 |
Correct |
85 ms |
1920 KB |
Output is correct |
3 |
Correct |
80 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
1920 KB |
Output is correct |
2 |
Correct |
80 ms |
1920 KB |
Output is correct |
3 |
Correct |
79 ms |
1920 KB |
Output is correct |