## Editorial for Wesley's Anger Contest 3 Problem 5 - Triangle: The Root of All Evil

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

For subtask 1, checking all subsets of rods will suffice, taking the most optimal and valid subset. To check if a subset is valid simply check all triplets of the remaining rods and verify that the triangle inequality does not hold.

An optional optimization is to notice that the easiest way to break the triangle inequality is to find the two largest rods present that is less than the remaining rod. Sorting the rods by length in increasing order allows us to check if .

Time Complexity: , or with the optimization.

For subtask 2, we can build on the idea of the optional optimization using dynamic programming. Let return the maximum value subset for the first rods with and being the indices of the two largest rods being kept. To solve the original problem we can simply subtract this from the total sum of all the rod values. For the transition, we can build onto these solutions as long as the next rod we keep does not form the triangle inequality.

Time Complexity:

For subtask 3, we can go for a greedy approach. In order to keep as many rods as possible, it is optimal to keep the ones with the smallest length, as this allows a greater range of possible rods to keep.

Time Complexity: