SRM533 Div2 Hard

1000
メモ化する。
memo[N番目の魔女まで][残りライフ]

const int N = 50 + 2;
const int M = 100000 + 2;
double memo[N][M];

struct S {
  double w;
  int g;
  int d;
  S(double w_, int g_, int d_)
    : w(w_), g(g_), d(d_) {};
};

vector<S> v;

double rec(int nth, int m, int max_m)
{
  if (m <= 0) return v[nth].d + m;
  if (nth == v.size()) return v.back().d + m;
  if (memo[nth][m] < 0) ; else return memo[nth][m];

  int next;

  next = min(m + v[nth].g, max_m);
  if (nth + 1 < v.size()) next -= v[nth + 1].d - v[nth].d;
  double fight = 0;
  fight += rec(nth + 1, next, max_m) * v[nth].w;
  fight += v[nth].d * (1.0 - v[nth].w);

  next = m;
  if (nth + 1 < v.size()) next -= v[nth + 1].d - v[nth].d;
  double ignore = rec(nth + 1,next, max_m);

  return memo[nth][m] = max(fight, ignore);
}

bool cmp(S a, S b)
{
  return a.d < b.d;
}

class MagicalGirl {
public:
  double maxExpectation(int M, vector <int> D, vector <int> W, vector <int> G)
  {
    fill(&memo[0][0], &memo[N - 1][M], -1);

    v.clear();
    for (int i = 0; i < D.size(); ++i) {
      v.push_back(S((double)W[i] / 100.0, G[i], D[i]));
    }
    sort(v.begin(), v.end(), cmp);

    return rec(0, M - v[0].d, M);
  }
};