PROBLEM LINK:
Author: tseccodecell
DIFFICULTY:
Medium
PREREQUISITES:
PROBLEM:
Chef has N books from B1 to Bn. Each book Bi has an author number Ai and happiness factor Hi. Reading book Bi gives Chef happiness P * Hi, where P is the number of authors whose books Chef read before (including the current book). Chef plans to read all books he has. Find the maximum amount of happiness he can gain by reading all books.
QUICK EXPLANATION:
Find the book which has the least happiness from each author. Sort them from smallest to largest happiness. Read these books first and then read all the other books in any order.
EXPLANATION:
We first aim to maximize the number of authors read, so that happiness gained by reading subsequent books increases. We keep the books with higher happiness for later so that they have a higher multiplier. Pick one book by each author with the smallest happiness factor for this purpose, and put it in a list. Read all these books in the list, from the one with the smallest happiness factor to the largest happiness factor. Once we read all the books in this initial list, read all the remaining books. Since the multiplier remains the same for all the remaining books, we only need to multiply the sum of happiness of all remaining books by the multiplier.