Editorial for DMOPC '22 Contest 5 P1 - Triple Triplets

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: yzhao123

It is optimal to use only the integers 1 and 2 in the array A. Then, the Triple value will be equal to {ones \choose 2} \times twos, where ones represents the number of 1s in the array, and twos represents the number of 2s in the array.

Subtask 1

This subtask was meant for suboptimal implementations of the full solution or brute forcing for each N by hand.

Subtask 2

Loop over all possible values of twos and calculate the Triple value for each, taking the maximum value for the answer.

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.