### Alma_s's blog

By Alma_s, history, 4 weeks ago,

I was recently solving 1316E - Team Building problem but I couldn't understand why we sorted the audience array. Can anyone help?

• +4

 » 4 weeks ago, # |   0 I think it's because that the total number of people is not $n$.So choosing audience is done greedily.. just pick the ones with highest $a_i$.This way you don't have to add another dimension $(the \space number \space of \space audience)$ to your $dp$ state.
•  » » 4 weeks ago, # ^ |   0 Or as the Tutorial says: SpoilerIf we don't choose $i$ as a player, then we can take him as an audience member or not take him at all. I claim that if the number of audience members chosen till now $\lt$ $k$ , then we must select $i$ as an audience member , We can prove this. If we don't select $i$ as audience, we will need to select some $j$ ($j \gt i$ ), strength in that case will include $a_j$ but not $a_i$ , but as $a_i \ge a_j$ , it is always better to select $i$ .
•  » » » 4 weeks ago, # ^ |   0 iam down