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$ ~1~ and $2$ ~2~ in the array $A$ ~A~. Then, the Triple value will be equal to ${ones \choose 2}$ ~{ones \choose 2}~ $\times$ ~\times~ $twos$ ~twos~, where $ones$ ~ones~ represents the number of $1$ ~1~s in the array, and $twos$ ~twos~ represents the number of $2$ ~2~s in the array.

Subtask 1

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

Subtask 2

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

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.