DWITE '07 R3 #3 - Playlist

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 64M
Problem type
DWITE Online Computer Programming Contest, December 2007, Problem 3

There's a library full of legally purchased music and a shiny new mp3 player that requires to be filled with the best possible playlist. Every song comes with a rating from 0 to 5 (inclusive) and takes up a certain amount of space. The best playlist is defined as the one with the highest total of rating points, that still fits into the allowable space.

The input will contain five data sets. The first line will contain the space available in the player, a positive integer. The second line will specify the size of the music library, 1≤N≤100. Followed by N lines in the form title rating space. The title will be a unique single string (no spaces). Rating is an integer 0 to 5. Space is an integer, 1≤S≤30000. Followed by the next data set.

The output will contain five lines, each containing an integer – a max sum of ratings that can fit on the player.

Sample Input

Copy
100
6
song_one 5 25
song_two 5 25
song_three 5 51
song_four 4 50
song_five 3 25
song_six 3 25

Sample Output

Copy
16

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 11
    ACCount_Nine38  commented on Sept. 30, 2018, 4:52 a.m. ← edit 3

    For those of you that are getting WA, you need to loop through and print everything 5 times as asked in the question. The Sample Output is only one example of an output.