Editorial for Girls Invitational '19 J3 - Essay Scores

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

One can observe that the N lines can always be split in such a way that the K lines with the largest values will be the score of the paragraph they are in.

Thus, we can sort the values, and sum up the largest K of them.

Time Complexity: \mathcal{O}(N\log N)

For Java users TLEing on the last case, see this page.


There are no comments at the moment.