_3180. Maximum Total Reward Using Operations I.md

3180. Maximum Total Reward Using Operations I

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Completed during Weekly Contest 401 (q3)

Back to top

---

First completed : July 07, 2024

Last updated : July 07, 2024

---

Related Topics : Array, Dynamic Programming

Acceptance Rate : 29.62 %

---

Solutions

• Weekly Contest 401/m3180 q3 converted.py
• Weekly Contest 401/m3180 q3 v2.py
• Weekly Contest 401/m3180 q3.c

Python

m3180 q3 converted.py

# https://leetcode.com/problems/find-the-n-th-value-after-k-seconds/description/

# Converted this from the C code and also passes :l

''' Notes:
    Max output will be at most 2x the max reward there is
'''

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()

        helperArr = [True] + [False] * (2000 * 2)

        for reward in rewardValues :
            for j in range(reward - 1, -1, -1) :
                if helperArr[j] :
                    helperArr[j + reward] = True
        
        for i in range(2000 * 2, -1, -1) :
            if helperArr[i] :
                return i
        return -1

m3180 q3 v2.py

# https://leetcode.com/problems/find-the-n-th-value-after-k-seconds/description/

''' Notes:
    Max output will be at most 2x the max reward there is
'''

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()

        maxx = max(rewardValues)
        helperArr = [True] + [False] * (maxx * 2)

        for reward in rewardValues :
            for j in range(reward - 1, -1, -1) :
                if helperArr[j] :
                    helperArr[j + reward] = True
        
        for i in range(maxx * 2, -1, -1) :
            if helperArr[i] :
                return i
        return -1

C

m3180 q3.c

// https://leetcode.com/problems/maximum-total-reward-using-operations-i/description/
// https://leetcode.com/contest/weekly-contest-401/


// Tried doing this *after* the contest thinking huh if I spent an hour
// trying to do this quesiton in python and kept getting TLEs, what if I just
// wrote a brute forcey thing in C. Did it in 10 minutes right after the contest
// and it immediately passed. Sigh.

int compareHelper(const void* one, const void* two) {
    return *((int *) one) - *((int *) two);
}

int maxTotalReward(int* rewardValues, int rewardValuesSize) {
    int maxVall = 0;
    for (int i = 0; i < rewardValuesSize; i++) {
        if (maxVall < rewardValues[i]) 
            maxVall = rewardValues[i];
    }

    bool helper[2000 * 2 + 1] = {false};

    qsort(rewardValues, rewardValuesSize, sizeof(int), compareHelper);

    helper[0] = true;
    for (int i = 0; i < rewardValuesSize; i++) {
        for (int j = rewardValues[i] - 1; j >= 0; j--) {
            if (helper[j]) {
                helper[j + rewardValues[i]] = true;
            }
        }
    }

    for (int i = 2000 * 2; i >= 0; i--) {
        if (helper[i]) 
            return i;
    }

    return -1;
}