540B - School Marks

The problem has two ideas :

1- ensuring that sum does not exceed some value : x.

2- median adjustment.

__ first notice that we cant solve this problem by filling our vector with value >= y ; why ? because he said that sum must not exceed value : x , so we have to take care of our cumulative sum.

So,to solve this problem we need to keep track of where our median falls (i.e. in the required area where median is greater than or equal : y or in the "-1" rejected region where median ((n+1)/2) falls where it is less than y (and his mom would punish him).

so,to clarify more here's an example, he started by giving us k elements as follows :

k = 4 , n = 9 , y = 3;

1 3 4 5 , so here counter of elements greater than or equal to y (3) = 3 ,and lower (less than 3) equals 1 , what that means ? greater_Elements_counter + 1 > lower_Elements_counter ,which ensures that our median must falls in the area where : v [ (n+1) / 2] must be >= y , that the first part.

The second part comes as how to fill the remaining (n-k) elements in a way that we try to have out two conditions fulfilled (1 && 2 listed above). the idea is simple enough to follow : if our Greater_counter + 1 > lower_counter means we have condition 2 done and have to take care of condition 1 where sum < x , so minimize ? yes , put the smallest possible value : 1.

My code (tried to comment it as possible) : [submission:http://mirror.codeforces.com/contest/540/submission/13006828]

high Quality code : [submission:http://mirror.codeforces.com/contest/540/submission/10948313]

I tried my best , so of course anything unclear or wrong , please ask me to handle it ASAP. __

Thanks :).