DMOPC '14 Contest 6 P4 - Kittan's Dilemma

View as PDF

Submit solution

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

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 N 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 2 to "Good" Gunmen and 1 to "Bad" Gunmen.

The deck of Dai-Gunzan has limited room — there are exactly M 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 M. 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 N and M, separated by a single space.

The next N lines of input will contain two integers S_i and P_i, the space and protection value of the i-th Gunmen, respectively.

Output Specification

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


Subtask 1 [25%]

1 \le N, M, S_i \le 1\,000

Subtask 2 [75%]

1 \le N \le 100\,000, 1 \le M, S_i \le 10^9

For all subtasks, 1 \le P_i \le 2.

Sample Input

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

Sample Output



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


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

    I got quickscoped Barred from entering a solution :/ kek

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

      if (prot == 4)
          prot = 5;

      • 0
        illuminati  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..

        • 2
          FatalEagle  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.

  • 1
    pyrexshorts  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.

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

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

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

    For N, M and S

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

      Subtask 1 [25%]


      Subtask 2 [75%]


      For all subtasks, 1≤Pi≤2.

      • 0
        kobortor  commented on March 10, 2015, 6:21 p.m.

        Does subtasks 2 include subtask 1?

        • 0
          FatalEagle  commented on March 10, 2015, 6:43 p.m.

          Subtasks are disjoint, but they may share test cases. It all adds up to 100%.