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>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)
using namespace std;
typedef long long ll;
typedef long double ld;
int kol[N], n, k;
ld dp[N];
//vector <int> cxt;
//
//vector <ld> otr;
//
//ld cross(pair <ld, ld> x, pair <ld, ld> y) {return ld(ld(y.S - x.S) / ld(x.F - y.F));}
//
//void add(int i)
//{
// while (sz(cxt) > 1)
// {
// int j = cxt[sz(cxt) - 2];
//
// ld crs = cross({ld(1) / ld(i), dp[i]}, {ld(1) / ld(j), dp[j]});
//
// if (otr.back() > crs) break;
//
// otr.pop_back();
//
// cxt.pop_back();
// }
//
// int j = cxt.back();
//
// otr.pb(cross({ld(1) / ld(i), dp[i]}, {ld(1) / ld(j), dp[j]}));
//
// cxt.pb(i);
//}
ld clc(int x, int y, ld cost) {return dp[y] + ld(y - x) / ld(y) + cost;}
void calc(ld cost)
{
dp[n] = 0;
kol[n] = 0;
// cxt.clear();
//
// otr.clear();
//
// cxt.pb(n);
for (int i = n - 1; i >= 0; i--)
{
// int l = 0, r = sz(cxt) - 1;
//
// while (l < r)
// {
// int md = (r + l) >> 1;
//
// if (ld(i) > otr[md]) r = md; else l = md + 1;
// }
//
// int j = cxt[l];
//
// kol[i] = kol[j] + 1;
//
// dp[i] = dp[j] + cost + 1 - ld(i) * (ld(1) / ld(j));
//
// add(i);
int l = i + 1, r = n;
while (r - l > 100)
{
int mdl = l + (r - l) / 3;
int mdr = r - (r - l) / 3;
if (clc(i, mdl, cost) > clc(i, mdr, cost)) r = mdr; else l = mdl;
}
dp[i] = 0;
for (int j = l; j <= r; j++)
if (dp[i] < clc(i, j, cost)) {dp[i] = clc(i, j, cost); kol[i] = kol[j] + 1;}
}
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
cout << setprecision(9) << fixed;
ld l = -1e9, r = 0;
while (r - l > 0.000000001)
{
ld md = (r + l) / 2.0;
calc(md);
if (kol[0] <= k) l = md; else r = md;
}
calc(l);
cout << ld(dp[0] - l * ld(kol[0]));
}
# | 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... |