Company Score with Manager Caps
Problem statement
A company has n employees with IDs 0 to n - 1. Employee i has the score scores[i] and reports to the manager managers[i]. The top employee has managers[i] == -1. Everyone else reaches the top employee by following managers.
A manager holds back the people who report to them. Each employee's effective score is:
- their own score, if they are the top employee or have been trained;
- otherwise, the smaller of their own score and their manager's effective score.
So an untrained employee can never do better than the person they report to, and a low score near the top holds back everyone below it. A trained employee keeps their own score and is no longer held back by anyone above them. They still hold back the people who report to them, like any other manager.
The company's total score is the sum of all effective scores. You may train at most t employees. Return the highest total score you can reach.
Function
maxCompanyScore(scores: int[], managers: int[], t: int) → longExamples
Example 1
scores = [5,8,3,6]managers = [-1,0,0,1]t = 0return = 18No one is trained. Employee 0 is the top employee and keeps 5. Employee 1 reports to 0, so it gets min(8, 5) = 5. Employee 2 gets min(3, 5) = 3. Employee 3 reports to employee 1, whose score is now 5, so it gets min(6, 5) = 5.
The total is 5 + 5 + 3 + 5 = 18.
Example 2
scores = [4,9,2,7,8]managers = [2,0,-1,0,3]t = 1return = 20Employee 2 is the top employee with score 2, so with no training every score is cut to 2 and the total is 10.
Train employee 3. It keeps its 7, and employee 4 reports to it, so employee 4 gets min(8, 7) = 7. Employees 0 and 1 still get 2. The total is 2 + 2 + 2 + 7 + 7 = 20.
Training employee 0 gives 2 + 4 + 4 + 4 + 4 = 18, employee 1 gives 17, and employee 4 gives 16, so 20 is the best.
Example 3
scores = [1,5,10,10]managers = [-1,0,1,1]t = 2return = 22With no training every score is 1, for a total of 4. Training only employee 1 gives 1 + 5 + 5 + 5 = 16, the best single choice.
Adding a second person to employee 1 gives at most 1 + 5 + 10 + 5 = 21. Training employees 2 and 3 instead gives 1 + 1 + 10 + 10 = 22, which is the best pair.
Constraints
1 <= n <= 500, wheren == scores.lengthmanagers.length == n1 <= scores[i] <= 10^9-1 <= managers[i] <= n - 1- Exactly one employee has
managers[i] == -1. Every other employee has a manager other than themselves, and following managers from any employee reaches the top employee. 0 <= t <= min(10, n)