Score Hacker

C. Score Hacker

No Submission Yet

Problem Statement

Uh Oh! Ms. Strict's class just had an exam, and all \(N\) students failed, each with score \(a_i\). Even more unfortunately, Ms. Strict's class has been chosen by the Massachusetts Department of Education to assess LHS' academic readiness!

In order to save the school's reputation, Principles Snehpets has hired you, a PRO HACKER, to hack into the system and change the students' scores. However, it would be very suspicious if the scores' total sum changes, or if any score is negative. In addition, increasing or decreasing a score by \(1\) costs \(1\) dollar, and since LHS is so broke, you can only spend at most \(K\) dollars. Help Principles Snehpets find the maximum possible median score after the changes.

Formally, given an array \(a_1, a_2, \cdots, a_N\), find the maximum number \(x\) such that there exists another sequence \(b_1, b_2, \cdots, b_N\) with median \(x\), such that \(b_i \geq 0\), \(\left(\sum{a_i}\right) = \left(\sum{b_i}\right)\), and \(\left(\sum{|a_i - b_i|}\right) \leq K\). Also note that since \(N\) is guarenteed to be odd, the median is always the \(\frac{N + 1}{2}\)-th largest element.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(N \leq 2 \cdot 10^5\)
\(0 \leq K \leq 10^{18}\)
\(0 \leq a_i \leq 10^9\)
It is guaranteed that \(N\) is odd
(Note that you may need 64 bits integer types such as long long in your solution)

Input Format

The first line has two integers \(N\), and \(K\) ― the number of elements and the maximum cost
The next line contains \(N\) integers, where the \(i\) th number is the score of the \(i\) th student, \(a_i\)

Output Format

Output the maximum achievable median after the changes.

Sample Input

5 8
1 3 5 7 9

Sample Output


Sample Explanation

A valid way is to subtract \(1\) point from the first student and \(3\) points from the second student, distribute \(3\) points to the third student, and \(1\) point to the fourth student. This gives the array \([0,0,8,8,9]\), which has a median of \(8\).

Credit: CodeTiger

Contact Us
LIT Discord Server