1
/* Note: This code results in a Timeout. */
2
class Solution {
3
 public:
4
  int n, c;
5
  vector<int> dp;
6
  int compute(const vector<int> &price, const vector<vector<int>> &offers, int needs) {
7
    if (dp[needs] != -1) return dp[needs];
8
    // Compute the min cost to satisfy these needs
9
    int best{}, new_needs, i;
10
    for (int i = 0; i < n; i++) {
11
      c = ((needs >> (i * 4)) & 0xf);
12
      best += c * price[i];
13
    }
14
    if (best == 0) return 0;
15
    for (const vector<int> &offer : offers) {
16
      new_needs = 0;
17
      for (i = 0; i < n; i++) {
18
        c = ((needs >> (i * 4)) & 0xf);
19
        if (c >= offer[i])
20
          new_needs |= ((c - offer[i]) << (i * 4));
21
        else
22
          break;
23
      };
24
      if (i == n) best = min(best, compute(price, offers, new_needs) + offer.back());
25
    }
26
    return dp[needs] = best;
27
  }
28
  int shoppingOffers(vector<int> &price, vector<vector<int>> &special, vector<int> &needs) {
29
    dp.resize((1 << 24) + 10, -1);
30
    n = needs.size();
31
    int needs_hash{};
32
    for (int i = 0; i < n; i++) needs_hash |= ((needs[i]) << (i * 4));
33
    return compute(price, special, needs_hash);
34
  }
35
};