Maximum Number of Groups Getting Fresh Donuts LeetCode solution in C++

1
class Solution {
2
  typedef long long ll;
3
#define vi(x) vector<x>
4
 public:
5
  unordered_map<string, ll> dp;
6
  string s;
7
  ll func(ll rem) {
8
    if (dp.find(s) == dp.end()) {
9
      dp[s] = -1;
10
    }
11
    ll &ans = dp[s];
12
    if (ans == -1) {
13
      ans = 0;
14
      ll bs = s.size();
15
      for (ll i = 1; i < bs; ++i) {
16
        if (s[i] > '0') {
17
          --s[i];
18
          ans = max(ans, func((bs + rem - i) % bs) + !rem);
19
          ++s[i];
20
        }
21
      }
22
    }
23
    return ans;
24
  }
25
  int maxHappyGroups(int bs, vector<int> &v) {
26
    s.assign(bs, '0');
27
    ll ans = 0;
28
    for (ll it : v) {
29
      if (it % bs == 0) {
30
        ++ans;
31
      } else if (s[bs - it % bs] > '0') {
32
        ++ans;
33
        --s[bs - it % bs];
34
      } else {
35
        ++s[it % bs];
36
      }
37
    }
38
    return ans + func(0);
39
  }
40
};