1 class Solution {
2 public:
3 int maxTotalReward(vector<int>& rewardValues) {
4 int m = ranges::max(rewardValues);
5 unordered_set<int> s;
6 for (int v : rewardValues) {
7 if (s.contains(v)) {
8 continue;
9 }
10 if (v == m - 1 || s.contains(m - 1 - v)) {
11 return m * 2 - 1;
12 }
13 s.insert(v);
14 }
15
16 ranges::sort(rewardValues);
17 rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
18
19 bitset<100000> f{1};
20 for (int v : rewardValues) {
21 int shift = f.size() - v;
22 f |= f << shift >> (shift - v);
23 }
24 for (int i = m * 2 - 1;; i--) {
25 if (f.test(i)) {
26 return i;
27 }
28 }
29 }
30 };