class Solution {
        /**
        Each rewardValues[i] can be collect once; can only collect rewardValues[i] > current reward value j.
        dp problem: decide whether collect or not at each position; dp[i][j] = if we can get reward value `j` from `rewardValues[0...i]`.
        At each rewardValues[i] = x, consider choose or not choose:
        if not choose, `dp[i][j] = dp[i - 1][j]`, i.e. if the same subproblem that if we can get reward value x from [0...i - 1].
        if choose, `dp[i][j] = dp[i - 1][j - x]`, where j must satisfy j - x < x and j - x >= 0, i.e. x <= j < 2x. The problem becomes "getting value j when choosing x depends on the subproblem that can we get value `j - x` from rewardValues[0...i - 1]".
        Associate two situations:
        {
            dp[i][j] = dp[i - 1][j] || dp[i - 1][j - x], when x <= j < 2x;
            dp[i][j] = dp[i - 1][j], when j < x or j >= 2x
        } 
        Since we cannot choose any smaller value if we choose bigger values first, the optimal approach is to choose from the smallest values first. Hence, the array must be sorted under the problem's description.
        Assuming the maximum of rewardValues[] is m, the maximum reward we can collect must < 2*m.
        [a1, a2, ..., an], an = m
        a1 + a2 + ... + an-1 + an, if we can choose all values, then a1 + a2 + ... + an-1 < m, so the total maximum value must < 2*m.
         */
    public int maxTotalReward(int[] rewardValues) {
        int n = rewardValues.length;
        Arrays.sort(rewardValues);
        int c = 2 * rewardValues[n - 1];
        boolean[] dp = new boolean[c + 1];
        dp[0] = true;
        int ans = 0;
        int pre = -1;
        for(int i = 0; i < n; i++){
            int x = rewardValues[i];
            if(x == pre) continue;
            for(int j = c; j >= x; j--){
                if(j < 2 * x){
                    dp[j] |= dp[j - x];
                }
                if(dp[j]){
                    ans = Math.max(ans, j);
                }
            }
            pre = x;
        }
        return ans;
    }
}

import java.math.BigInteger;
class Solution {
    /**
    Same problem as 3180.
    But 3181's dataset is much larger, optimization has to be done.
    From the dp equation: dp[j] |= dp[j - x], this can be done using a bitset.
    Use a binary number, the initial state is the lowest digit being 1, indicating dp[0] = true;
    For each rewardValues[i] = x, the state transfer equation is dp[j] |= dp[j - x], which is equivalent to: if dp[s] = true, for all s < x, dp[s + x] = true, where s is the current reachable sum.
    This is equivalent to taking all reachable sums `s < x`, shifting them by `x`, and OR-ing back.
    Final result is the highest set bit of the bitset.
    In this way, each `j` is not processed separately, but processed in a batch(32/64) with a bitset.
     */
    public int maxTotalReward(int[] rewardValues) {
        int n = rewardValues.length;
        int mx = 0;
        for(int x : rewardValues) mx = Math.max(mx, x);
        
        // The maximum value we can get < 2 * mx
        // 1) If we can get mx - 1, we can get mx.
        // i.e. the answer is certainly = mx - 1 + mx = 2*mx - 1
        // 2) If there are two values sum to mx - 1, we can get 2*mx - 1.
        Set<Integer> set = new HashSet<>();
        int target = mx - 1;
        for(int x : rewardValues){
            if(x == mx - 1) return 2 * mx - 1;
            if(set.contains(x)) continue;
            if(set.contains(target - x)) return 2 * mx - 1;
            set.add(x);
        }
        Arrays.sort(rewardValues);
        BigInteger f = BigInteger.ONE;
        int ans = 0;
        int pre = -1;
        for(int i = 0; i < n; i++){
            int x = rewardValues[i];
            if(pre == x) continue;
            BigInteger mask = BigInteger.ONE.shiftLeft(x).subtract(BigInteger.ONE);
            // do operation for all bits <= x
            f = f.or(f.and(mask).shiftLeft(x)); // dp[s + x] |= dp[s]
            pre = x;
        }
        return f.bitLength() - 1;
    }
}