あなたの最大HPは $M$ です。あなたのHPは一日の初めに $1$ だけ減ります。
$N$ 人の魔女がこれからやってきます。
$i$ 番目の魔女がやってくるのは $day[i]$ 日めで、その魔女に勝てる確率は $win[i]$ パーセント、勝つと回復できるHPは $gain[i]$ です。
魔女に負けたらあなたはその時点で死亡します。
魔女と戦うかスルーするか選べるとき、あなたの残りの寿命の期待値を求めてください。SRM 533 Div2 Hard
$2 \le M \le 100{,}000$
$1 \le N \le 50$
$0 \le day[i] \le 5{,}000{,}000$
$0 \le win[i] \le 100$
$1 \le gain[i] \le M$

#include <iostream>
#include <algorithm>
using namespace std;

class MagicalGirl { public: double maxExpectation(int M, vector<int> day, vector<int> win, vector<int> gain); };

struct Witch {
  int day; double win; int gain;
  bool operator<(const Witch &another) const { return day < another.day; }
};

int n, m;
vector<Witch> v;
vector<vector<double>> dp;

// i番目の魔女と戦うか戦わないか悩んでる状態、前回終了時のHPはhp。
// この時点での寿命の期待値を返す。
double rec(int i, int hp) {
  double &res = dp[i][hp];
  if(res > 0) { return res; }
  double r0 = v[i-1].day + hp;
  if(i == n+1) { return res = r0; } // 魔女がいなくなったら今のHPとこれまでの経過日数の和が寿命になる。
  int dif = v[i].day - v[i-1].day; // 前回からの日数。
  if(hp-dif <= 0) { return res = r0; } // 今の魔女が来るまでにHPが0になる。
  double r1 = rec(i+1, hp-dif), // 戦わない。
         // 戦う。
         // i番目に勝ったときのHPは "戦う前のHP + 戦って得られるHP" だが m は超えない。
         // i番目に負けたときはその時点で寿命が尽きる。
         r2 = v[i].win * rec(i+1, min(m, hp-dif+v[i].gain)) + (1-v[i].win) * v[i].day;
  return res = max(r1, r2);
}

double MagicalGirl::
maxExpectation(int _m, vector<int> day, vector<int> win, vector<int> gain) {
  m = _m;
  n = day.size();
  dp.assign(n+2, vector<double>(m+1));
  v.resize(n+1);
  v[0] = Witch(); // 番兵
  for(int i=0; i<n; i++) {
    v[i+1] = Witch({day[i], win[i]/100.0, gain[i]});
  }
  sort(v.begin(), v.end()); // 魔女が登場する順番でソート
  double res = rec(1, m);
  return res;
}
    

#include <iostream>
#include <algorithm>
using namespace std;

class MagicalGirl { public: double maxExpectation(int M, vector<int> day, vector<int> win, vector<int> gain); };

struct Witch {
  int day; double win; int gain;
  bool operator<(const Witch &another) const { return day < another.day; }
};

int n, m;
vector<vector<double>> dp;

double MagicalGirl::
maxExpectation(int m, vector<int> day, vector<int> win, vector<int> gain) {
  int n = day.size();
  dp.assign(n+1, vector<double>(m+1));
  vector<Witch> v(n+1);
  v[0] = Witch();
  for(int i=0; i<n; i++) {
    v[i+1] = Witch({day[i], win[i]/100.0, gain[i]});
  }
  sort(v.begin(), v.end());
  for(int i=n; i>=0; i--) {
    for(int j=0; j<=m; j++) {
      double &res = dp[i][j];
      double r0 = v[i].day + j;
      if(i==n) { res = r0; continue; }
      int dif = v[i+1].day - v[i].day;
      if(j-dif <= 0) { res = r0; continue; }
      double r1 = dp[i+1][j-dif],
             r2 = v[i+1].win * dp[i+1][min(m, j-dif+v[i+1].gain)] + (1-v[i+1].win) * v[i+1].day;
      res = max(r1, r2);
    }
  }
  double res = dp[0][m];
  return res;
}