An orbital salvage crew has recovered three kinds of cargo crates from a derelict station. Every Prime crate is worth +1 credit, every Neutral crate is worth 0 credits, and every Faulty crate costs -1 credit to bring home (its disposal fee outweighs its scrap value). The shuttle has a fixed number of open cargo slots, and the crew must fill exactly k of those slots by choosing crates (crates of the same kind are interchangeable, so only how many of each kind are chosen matters). Determine the maximum total credit value the crew can achieve.
A single line containing four space-separated integers:
numPrime numNeutral numFaulty k
— the number of Prime crates available, the number of Neutral crates available, the number of Faulty crates available, and the exact number of crates that must be loaded.
A single integer: the maximum total credit value achievable by loading exactly k crates.
0 <= numPrime, numNeutral, numFaulty <= 500 <= k <= numPrime + numNeutral + numFaultyExample 1
Input
3 4 5 4
Expected
3
Explanation
With 3 Prime, 4 Neutral, and 5 Faulty crates available, load all 3 Prime crates (+3) plus 1 Neutral crate (+0) to fill the 4 required slots. Taking any Faulty crate would only lower the total, so the best achievable value is 3.
Example 2
Input
2 3 5 6
Expected
1
Explanation
Load all 2 Prime crates (+2) and all 3 Neutral crates (+0), which fills 5 of the 6 required slots. Only Faulty crates remain, so 1 Faulty crate (-1) must be loaded to reach exactly 6, giving a total of 2 - 1 = 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →