DCP-90: Businessman Asif Back to All Problems

Medium Divide and Conquer > Dynamic Programming


Asif is a very good businessman and he is very friendly and warm towards all of his employees . But he notices that some of them take this as an advantage and aren’t serious about their job . So keeping them in work aren’t beneficial for the company . He wants to sack them . The company has N employees . They are numbered from 1 to N and as a CEO of the company Asif’s id is 0 . The company maintains tree- like hierarchy . Each employee works under a supervisor . The CEO has no supervisor . Each employee report directly to his supervisor . If his supervisor is sacked from his job there is no means to keep him in the job too . You have a description of all employees , his supervisor id , his salary and productivity . The company gets profit from his service as his productivity minus( - ) his salary . Note that **it can be negative** . Company’s total profit is the sum of the profit It gets from all of his active employees. Can you tell the maximum profit the company can get after firing ( possibly none , possible all ) some of its employees. Input: ------ The first line contains an integer T ( 1 <= T <= 50 ) denotes the number of test cases. T test cases follow. There is a integer N ( 1 <= N <= 100 ) number of employees in the first line of every test case . Then N lines follow . Each line contains a description of each employee , Three integer numbers x ( his supervisor’s id , can be any of 0 to N ) , y ( his salary ) and z ( his productivity ) . . Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the maximum profit the company can get . Constraints: ------- 1 <= T <= 50 1 <= N <=100 1 <= y <= 100000 1 <= z <= 100000 Sample Input ------------ 3 3 0 1 3 0 2 2 0 3 1 4 0 3 4 1 5 3 2 2 3 3 1 4 1 0 1 0 Sample Output ------------- Case 1: 2 Case 2: 3 Case 3: 0


Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 1.00
Go 1.00
Java 1.00
JavaScript 1.00
Objective-C 1.00
Perl 1.00
PHP 1.00
Python 1.00
Python3 1.00
Ruby 1.00
VB.Net 1.00

Problem Stats

20/44

Solve/Submission

Ranking

# User Language Timing
01 tariqiitju Cpp14 0.00s
02 sakib_muhit Cpp14 0.00s
03 feodorv C 0.00s
04 Morass Cpp14 0.00s
05 Robbinb1993 Cpp 0.00s
06 prateepm Cpp14 0.00s
07 mh755628 Cpp 0.01s
08 njrafi Cpp14 0.01s
09 moinul_shaon Cpp14 0.29s
10 dipta007 Cpp14 0.39s
11 froghramar Cpp14 0.39s
12 safayet007 Cpp14 0.43s
13 Foyaz05 Cpp14 0.43s
14 ksohan Cpp14 0.43s
15 Mahmudul_Tushar Cpp14 0.45s
16 OsmanHossain Cpp14 0.55s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support