# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
462291 |
2021-08-10T10:11:11 Z |
grt |
Akvizna (COCI19_akvizna) |
C++17 |
|
1500 ms |
492 KB |
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 3000 + 10;
int n, k;
long double dp[nax];
int cnt[nax];
int main() {_
cin >> n >> k;
long double low = 0.0, high = 100000.0000, mid;
for(int rep = 0; rep < 60; ++rep) {
mid = (low + high) / 2.0;
for(int used = 0; used <= n; ++used) {
dp[used] = 0;
cnt[used] = 0;
for(int u1 = 1; u1 <= used; ++u1) {
if(dp[used] < dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid) {
dp[used] = dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid;
cnt[used] = cnt[used - u1] + 1;
}
}
}
if(cnt[n] <= k) {
high = mid;
} else {
low = mid;
}
}
mid = high;
for(int used = 0; used <= n; ++used) {
dp[used] = 0;
cnt[used] = 0;
for(int u1 = 1; u1 <= used; ++u1) {
if(dp[used] < dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid) {
dp[used] = dp[used - u1] + (long double)u1 / (n - (used - u1)) - mid;
cnt[used] = cnt[used - u1] + 1;
}
}
}
cout << setprecision(10);
cout << fixed;
cout << dp[n] + mid * k; //<< " " << cnt[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1457 ms |
356 KB |
Output is correct |
2 |
Execution timed out |
1586 ms |
344 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1589 ms |
352 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1553 ms |
348 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1527 ms |
348 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1573 ms |
360 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1262 ms |
344 KB |
Output is correct |
2 |
Execution timed out |
1589 ms |
332 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1590 ms |
332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1448 ms |
332 KB |
Output is correct |
2 |
Execution timed out |
1599 ms |
332 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1591 ms |
332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
57 ms |
452 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
57 ms |
456 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
58 ms |
480 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
57 ms |
476 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
57 ms |
484 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
63 ms |
452 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
59 ms |
480 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
60 ms |
484 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
60 ms |
472 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
60 ms |
492 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
61 ms |
452 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
64 ms |
480 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
62 ms |
484 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |