Editorial for WC '18 Contest 3 J2 - Net Weight
Submitting an official solution before solving the problem yourself is a bannable offence.
We'll iterate over the Pikachus while maintaining two values and – the largest and second-largest weights of catchable Pikachus seen so far, respectively. Initially, .
When considering the -th Pikachu, we should ignore it completely if . Otherwise, if , 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 to equal , and then set to equal . Otherwise, if , then we've found a new second-heaviest catchable Pikachu, so we should simply set to be equal to .
After considering all Pikachus in this fashion, 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, and/or will still be equal to , which is desirable as it represents Jessie and/or James remaining empty-handed.
Comments