Codeforces исполнилось 10 лет! Мы рады анонсировать краудфандинг-кампанию. Поздравьте нас по ссылке https://codeforces.com/10years. ×

Help | Looking for editorial | Maximise reward question

Правка en1, от bansal1232, 2019-02-24 09:43:50

Can someone tell me how to approach this problem?

You are given N tasks with following information:

Deadline: Di

Reward: Ri

Time taken to complete the tasks: Pi

The reward is given only when a task is completed within the corresponding deadline.

Write a program to schedule the tasks in order to maximise the reward.

Input format

First line: T (number of test cases)
First line in each test case: N
Next N lines in each test case: Three space-separated integers Di, Ri, and Pi

Output format

For each test case, print the schedule of tasks that maximizes the reward in new line.

Constraints

1≤T≤10

1≤N≤103

1≤D≤103

1≤PD

1≤R≤106

Sample Input

1
6
1 2 1
2 3 1
4 1 2
10 10 10
15 13 10
15 7 5

Sample Output

20

Explanation

If we perform the last two task alone we can get the maximum reward which is 20

Теги #help, #dynamic-programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский bansal1232 2019-02-24 09:43:50 1042 Initial revision (published)