Yet Another Contest 2 P4 - No More Arithmetic

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.0s
Python 5.0s
Memory limit: 512M

Author:
Problem types

Mike is tired of performing arithmetic with squares, so he has decided to break his square up into an array A with N integers. Furthermore, Mike wants to reduce the size of his array, so he will continue to perform the following process, in order, until he is unable to.

  • Select two integers A_i and A_j in the array such that A_i \ge A_j and i \ne j.
  • Select one of the four operations:
    • A_i + A_j
    • A_i - A_j
    • A_i \times A_j
    • A_i \div A_j. Mike may only select this operation if the result is an integer.
  • Increase the total score by the number obtained from performing the selected operation taken modulo M.
  • Remove either A_i or A_j from the array.

Your job is to help Mike find the maximum possible total score that can be obtained.

Constraints

1 \le N \le 2\,000

1 \le M, A_i \le 10^9

M is a prime number.

Subtask 1 [10%]

1 \le N \le 8

Subtask 2 [20%]

1 \le N \le 18

Note that the previous subtask must be passed for this subtask to be evaluated.

Subtask 3 [20%]

M = 2

Every element of A can be expressed in the form 2^p \times 3^q, where p and q are non-negative integers.

Subtask 4 [Up to 50%]

No additional constraints.

In order to obtain all 50\% of the points allocated to this subtask, your submission must adhere to the following memory limits:

  • In Python, your program must not exceed 16 MB of memory usage. Python users are recommended to use Python 2/3 over PyPy 2/3 when submitting.
  • In Java, your program must not exceed 64 MB of memory usage.
  • In all other languages, your program must not exceed 8 MB of memory usage.

If your program produces the correct output on all test cases but does not adhere to the memory limits listed above, then it will only receive 20\% out of the 50\% of points available for this subtask.

Note that the memory constraints listed above only apply to this subtask.

Note that all previous subtasks must be passed for this subtask to be evaluated.

Input Specification

The first line contains two integers N and M.

The next line contains A_1, A_2, \dots, A_N.

Output Specification

On a single line, print the maximum possible score.

Sample Input 1

3 5
8 4 5

Sample Output 1

8

Explanation for Sample Output 1

Mike can first select A_i = 8 and A_j = 4. Then, he will choose the - operation and add (8-4) \bmod 5 = 4 to the total score. Then, he will remove 8 from the array, so the array becomes [4, 5].

Next, Mike selects A_i = 5 and A_j = 4. Then, he will choose the + operation and add (5+4) \bmod 5 = 4 to the total score. Then, he will remove 4 from the array, so the array becomes [5].

Now, the array only consists of one integer. Mike is unable to perform any more moves, and his final score is 4+4 = 8. It can be shown that this is the maximal score.

Sample Input 2

4 2
1 1 1 1

Sample Output 2

3

Explanation for Sample Output 2

Since all elements in the array are equal, the choice of integers which Mike selects and deletes does not matter. Each time, he will choose the \times or \div operation and add 1 to his total score, resulting in a final score of 3.

Sample Input 3

4 7
5 11 42 7

Sample Output 3

17

Sample Input 4

5 13
6 432 209 420 9

Sample Output 4

45

Comments

There are no comments at the moment.