Editorial for WC '18 Contest 3 J2 - Net Weight


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.

We'll iterate over the N Pikachus while maintaining two values m_1 and m_2 – the largest and second-largest weights of catchable Pikachus seen so far, respectively. Initially, m_1 = m_2 = 0.

When considering the i-th Pikachu, we should ignore it completely if W_i > 100. Otherwise, if W_i > m_1, then we've found a new heaviest catchable Pikachu, demoting the previous heaviest one to now be the second-heaviest – therefore, we should first set m_2 to equal m_1, and then set m_1 to equal W_i. Otherwise, if W_i > m_2, then we've found a new second-heaviest catchable Pikachu, so we should simply set m_2 to be equal to W_i.

After considering all N Pikachus in this fashion, m_1+m_2 comes out to the sum of the two heaviest catchable Pikachus' weights, which is the answer we're looking for. Note that if there were fewer than two catchable Pikachus, m_1 and/or m_2 will still be equal to 0, which is desirable as it represents Jessie and/or James remaining empty-handed.


Comments

There are no comments at the moment.