Editorial for WC '18 Contest 3 J2 - Net Weight - Olympiads Online Judge

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$ $N$ Pikachus while maintaining two values $m_1$ $m_{1}$ and $m_2$ $m_{2}$ – the largest and second-largest weights of catchable Pikachus seen so far, respectively. Initially, $m_1 = m_2 = 0$ $m_{1} = m_{2} = 0$ .

When considering the $i$ $i$ -th Pikachu, we should ignore it completely if $W_i > 100$ $W_{i} > 100$ . Otherwise, if $W_i > m_1$ $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$ $m_{2}$ to equal $m_1$ $m_{1}$ , and then set $m_1$ $m_{1}$ to equal $W_i$ $W_{i}$ . Otherwise, if $W_i > m_2$ $W_{i} > m_{2}$ , then we've found a new second-heaviest catchable Pikachu, so we should simply set $m_2$ $m_{2}$ to be equal to $W_i$ $W_{i}$ .

After considering all $N$ $N$ Pikachus in this fashion, $m_1+m_2$ $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$ $m_{1}$ and/or $m_2$ $m_{2}$ will still be equal to $0$ $0$ , which is desirable as it represents Jessie and/or James remaining empty-handed.

Comments

There are no comments at the moment.