Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

Hi Codeforces, could you help me with this problem?

Revision en1, by IWantToBeNutellaSomeday, 2019-09-22 08:47:27

A friend talked me about this problem and i don't know how to solve it or if there is a judge to make submitions.

You will be given an array of $N$ integers $A$. You know that $1 \leq N \leq 2000$ and $1 \leq A_i \leq 10^6$.

Is there any way to know for a fixed $1 \leq k \leq N$ the maximum number of times you can choose $k$ different elements from $A$ with the condition that if you choose indexes $p_1,p_2,...,p_k$ then you have to do $A_{p_i}-=1$ for every $1 \leq i \leq k$ and $A_i \geq 0$ should hold.

My idea is that every time, you have to choose the currently $k$ greatest elements (but i don´t know if this is optimal, i did´nt prove it). And i guess that the time complexity for this would be $O( $$\sum_{i=1}^{n} A_i$$ ) \approx 10^9$ worst case.

Another version

You are free to choose $k$ in such a way that at the end of the process with that $k$ (the process described above) the sum of the remaining elements should be minimum. You have to find the greatest $k$ meet this condition.

Any comment is welcome. Thank you.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 IWantToBeNutellaSomeday 2019-09-22 08:47:27 1115 Initial revision (published)