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 - y.F) / ld(x.F - y.F));}
void add(int i)
{
while (sz(cxt) > 1)
{
int j = cxt[sz(cxt) - 2], u = cxt.back();
ld crs1 = cross({dp[i], ld(1) / ld(i)}, {dp[j], ld(1) / ld(j)});
ld crs2 = cross({dp[u], ld(1) / ld(u)}, {dp[j], ld(1) / ld(j)});
if (crs2 > crs1) break;
otr.pop_back();
cxt.pop_back();
}
int j = cxt.back();
otr.pb(cross({dp[i], ld(1) / ld(i)}, {dp[j], ld(1) / ld(j)}));
cout << cross({dp[i], ld(1) / ld(i)}, {dp[j], ld(1) / ld(j)}) << endl;
cxt.pb(i);
}
void calc(ld cost)
{
dp[n] = 0;
kol[n] = 0;
cxt.clear();
otr.clear();
cxt.pb(n);
otr.pb(1e9);
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) + cost <= otr[md]) r = md; else l = md + 1;
}
int j = cxt[l];
kol[i] = kol[j] + 1;
dp[i] = dp[j] + cost + ld(j - i) * (ld(1) / ld(j));
add(i);
}
}
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 = -1, r = 0;
while (r - l > 0.0000000000001)
{
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... |