SRM469 Div1 Medium

500
メモ化して復元

const int T = 1 << 20;
int t[T];
int path[T];

vector<int> L, S;

int rec(int bit)
{
  if (t[bit] != -1) return t[bit];

  int s = 74;
  for (int i = 0; i < L.size(); ++i) {
    if (bit & (1 << i)) s += 47 - L[i];
  }

  int best = 0;
  int next = -1;
  for (int i = 0; i < L.size(); ++i) {
    if (bit & (1 << i)) continue;
    if (S[i] <= s && L[i] <= s + 47) ; else continue;
    int tmp = rec(bit ^ (1 << i)) + 1;
    if (best < tmp) {
      best = tmp;
      next = i;
    }
  }

  path[bit] = next;
  return t[bit] = best;
}

class TheMoviesLevelTwoDivOne {
public:
  vector <int> find(vector <int> L_, vector <int> S_) 
  {
    L = L_;
    S = S_;
    fill(t, t + T, -1);

    rec(0);
    vector<int> ret;
    set<int> used;
    for (int i = 0; path[i] != -1; i = i ^ (1 << path[i])) {
      ret.push_back(path[i]);
      used.insert(path[i]);
    }
    for (int i = 0; i < L.size(); ++i) {
      if (used.count(i)) ; else ret.push_back(i);
    }
    return ret;
  }

};