Submission #50750315

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, L, D;
  cin >> N >> L >> D;
  int mm = max(N, L + D) + 1;

  vector<double> py(mm), sum_py(mm);
  py[0] = 1;
  sum_py[0] = 1;
  for (int i = 1; i < mm; i++) {
    int l = max(0, i - D);
    int r = min(L - 1, i - 1);
    if (l <= r) {
      double t = sum_py[r] - (l == 0 ? 0 : sum_py[l - 1]);
      py[i] = t / D;
    }
    sum_py[i] = sum_py[i - 1] + py[i];
  }
//   debug(py);
//   debug(sum_py);

  vector<double> f(mm), g(mm), dp(mm), sum_dp(mm);
  for (int i = mm - 1; i >= 0; i--) {
    int l = min(mm - 1, i + 1);
    int r = min(mm - 1, i + D);
    double t = sum_dp[l] - (r == mm - 1 ? 0 : sum_dp[r + 1]);
    f[i] = t / D;

    g[i] = 0;
    l = N + 1, r = mm - 1;
    if (l <= r) {
      t = sum_py[r] - (l == 0 ? 0 : sum_py[l - 1]);
      g[i] += t;
    }
    l = L, r = i - 1;
    if (l <= r) {
      t = sum_py[r] - (l == 0 ? 0 : sum_py[l - 1]);
      g[i] += t;
    }

    dp[i] = max(f[i], g[i]);
    if (i > N) dp[i] = 0;
    // debug(i, f[i], g[i]);
    sum_dp[i] = dp[i];
    if (i < mm - 1) sum_dp[i] += sum_dp[i + 1];
  }
  cout << fixed << setprecision(10) << dp[0] << '\n';

  return 0;
}

Submission Info

Judge Result