This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
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... |