DMOPC '14 Contest 6 P4 - Kittan's Dilemma

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kittan is in charge of the battleship-like Dai-Gunzan and therefore is responsible for choosing which Gunmen should stay on Dai-Gunzan's deck to patrol. Kittan has possible Gunmen to choose from. Unfortunately, Kittan doesn't have the patience to carefully assess each individual Gunmen's capabilities, so he labels each as "Good" or "Bad", based on a cursory glance. He assigns a protection value of to "Good" Gunmen and to "Bad" Gunmen.

The deck of Dai-Gunzan has limited room — there are exactly units of space for patrolling Gunmen to use. Kittan is a busy man, so he assigned Jorgun to keep track of the amount of space each Gunmen takes up. He also assigned Balinbow to figure out the maximum sum of protection values Dai-Gunzan can have by taking a subset of available Gunmen whose total space consumption does not exceed . Unfortunately, while Jorgun is barely smart enough to measure Gunmen, Balinbow desperately needs your help in this optimization problem.

Input Specification

The first line of input will contain two integers and , separated by a single space.

The next lines of input will contain two integers and , the space and protection value of the Gunmen, respectively.

Output Specification

The first and only line of output should be the maximum protection value Dai-Gunzan can have.

Sample Input

5 11
1 1
6 2
3 1
5 2
4 2

Sample Output

5

Explanation

Take the Gunmen that use 1, 4, and 5 space for a total protection value of .

• commented on March 16, 2015, 10:16 p.m.

I got quickscoped Barred from entering a solution :/ kek

• commented on March 16, 2015, 10:31 p.m.

http://www.dmoj.ca/tos/

if (prot == 4)
prot = 5;

• commented on March 16, 2015, 10:48 p.m.

LOL thanks, i noticed that in my submission. Didn't read the TOS and decided to be cheap, sorry about that. I don't know why my program didn't work for that one case..

• commented on March 16, 2015, 11:10 p.m.

I've deleted the offending submission. Don't do it again. Instead, figure out why your program doesn't work, fix it, and resubmit.

• commented on March 12, 2015, 9:14 p.m.

I'm stuck on this question.

Mod Edit: Do not post full solutions or algorithms in the comments.

• commented on March 12, 2015, 11:00 p.m.

Idea : Try seperating the "good" gunmen and the "bad" ones

• commented on March 10, 2015, 6:18 p.m.

For N, M and S

• commented on March 10, 2015, 6:19 p.m.

1≤N,M,Si≤1000