DMPG '17 G1 - FatalWhale and Candies

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.18s
Memory limit: 6M

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

Molly is trying to steal some candy from her best friend FatalWhale. Unfortunately, FatalWhale is very organized and will immediately notice if the total sweetness of candies Molly takes is not a multiple of P. Help Molly determine which candies out of the N FatalWhale has in order to take the maximum sweetness!

Constraints

  • N, P \le 4096
  • You will receive 20\% of the points if you find just the maximum sweetness, but in order to receive these points, you must correctly follow the output specification.
  • Molly will always take at least one candy.

Input Specification

On the first line of input you will find two space-separated integers, N and P.
On the second line of input you will find the sweetness of the N candies, as space-separated integers s_i. (0 \le s_i \le 500\,000)

Output Specification

On the first line you will print the maximum sweetness.
On the second line you will print the number of the candies that Molly takes in order to take the maximum sweetness.
On the third line, you will print the indices of the candies Molly takes.

Sample Input

7 6
178 25 123 34 56 79 100

Sample Output

570
6
1 3 4 5 6 7

Sample Output [for 20% of points]

570
1
1

Comments


  • 1
    juho  commented on May 30, 2017, 10:12 p.m.

    Impossible to do it within time and memory limits with Python.


    • 9
      Xyene  commented on May 31, 2017, 12:05 a.m.

      Not all problems on the judge are solvable in Python by design. In this case, though, your approach's complexity is such that it would TLE on similar cases even if it were implemented in C++ — there is a faster approach.

      Good luck!


      • 2
        jkguipqnjcy49979693  commented on Oct. 16, 2017, 10:05 p.m.

        Yes but is it at least possible to get different Time Limit constraints like on other problems? (I can write C ++ code just fine, but, to be fair, 0.25 seconds is too strict for even Java, let alone Python.)