# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
222149 |
2020-04-12T08:21:24 Z |
VEGAnn |
Akvizna (COCI19_akvizna) |
C++14 |
|
1500 ms |
3456 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100100;
const ll OO = 1e18;
const ld E = 1e-9;
vector<int> vc;
ld f[2][N];
int n, k, tp;
void calc(int l, int r, int opl, int opr){
if (l > r) return;
int j = (l + r) >> 1, opt = -1;
for (int pr = max(j, opl); pr <= opr; pr++){
if (f[tp ^ 1][pr] < -E) continue;
ld ad = f[tp ^ 1][pr] + 1.0 - ld(j) / ld(pr);
if (f[tp][j] + E < ad) {
f[tp][j] = ad;
opt = pr;
}
}
assert(opt > -1);
calc(l, j - 1, opl, opt);
calc(j + 1, r, opt, opr);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n >> k;
for (int j = 0; j <= n; j++)
f[0][j] = -1.0;
f[0][n] = 0.0;
for (int i = 1; i <= k; i++) {
tp = (i & 1);
for (int j = 0; j <= n; j++)
f[tp][j] = -1.0;
calc(0, n - 1, 0, n);
}
cout << fixed << setprecision(10) << f[k & 1][0];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
384 KB |
Output is correct |
2 |
Correct |
290 ms |
560 KB |
Output is correct |
3 |
Correct |
367 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
384 KB |
Output is correct |
2 |
Correct |
238 ms |
384 KB |
Output is correct |
3 |
Correct |
385 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
384 KB |
Output is correct |
2 |
Correct |
148 ms |
476 KB |
Output is correct |
3 |
Correct |
356 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
384 KB |
Output is correct |
2 |
Correct |
235 ms |
512 KB |
Output is correct |
3 |
Correct |
375 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
384 KB |
Output is correct |
2 |
Correct |
210 ms |
384 KB |
Output is correct |
3 |
Correct |
334 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
384 KB |
Output is correct |
2 |
Correct |
302 ms |
384 KB |
Output is correct |
3 |
Correct |
413 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
512 KB |
Output is correct |
2 |
Correct |
278 ms |
488 KB |
Output is correct |
3 |
Correct |
446 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
384 KB |
Output is correct |
2 |
Correct |
212 ms |
384 KB |
Output is correct |
3 |
Correct |
349 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
384 KB |
Output is correct |
2 |
Correct |
235 ms |
384 KB |
Output is correct |
3 |
Correct |
394 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1593 ms |
3200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1592 ms |
3328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1589 ms |
3328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1586 ms |
3328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1599 ms |
3328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1599 ms |
3456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1594 ms |
3328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1589 ms |
3328 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1597 ms |
3456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1588 ms |
3456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1591 ms |
3456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1599 ms |
3456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1596 ms |
3456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |