HeroicSchedule | Topcoder Archive

Problem Statement

Hero has a list of n tasks he can do. Hero can choose which tasks he will perform and in which order. Each task will take him exactly one day, and on each day he can only work on one of the tasks. The days on which Hero can do these tasks are numbered starting from 0. Each task i has three parameters:

start[i] is the first day on which Hero can do this task,
finish[i] is the last such day, and
cost[i] is the amount of money Hero will earn if he completes this task.

Calculate and return the maximum total amount of money Hero can earn by completing some of the given tasks. You are given the ints: n, A, B, C, modStart, modLen, and modCost. Use the pseudocode below to generate the arrays start, finish, and cost:

x[0] = A
for i from 1 to n*3 - 1: x[i] = (x[i-1] * B + C) % (10^9+7);
for i from 0 to n - 1:
	start[i] = x[i*3] % modStart
	finish[i] = start[i] + (x[i*3+1] % modLen)
	cost[i] = x[i*3+2] % modCost

Definition

Class:: HeroicSchedule
Method:: getmax
Parameters:: int, int, int, int, int, int, int
Returns:: int
Method signature:: int getmax(int n, int A, int B, int C, int modStart, int modLen, int modCost)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator. In the given time limit the reference solution would be able to solve any valid test case with the same bounds on the number of tasks and the range of their parameters.

Constraints

n will be between 1 and 2,000,000, inclusive.
A, B and C will be between 0 and 1,000,000,006, inclusive.
modStart, modLen and modCost will be between 2 and 1000, inclusive.

Examples

```
4
```
```
3
```
```
2
```
```
3
```
```
4
```
```
2
```
```
10
```
```
Returns: 15
```
There are four tasks with following start, finish and cost: (3,4,1) (1,2,9) (1,2,3) (1,2,5) One optimal solution looks as follows: On day 0 Hero cannot work on any of the tasks. On day 1 Hero completes the task with cost 5. On day 2 Hero completes the task with cost 9. On day 3 Hero relaxes. On day 4 Hero completes the task with cost 1. The total amount Hero has earned is 5+9+1 = 15.
```
6
```
```
1
```
```
2
```
```
3
```
```
4
```
```
3
```
```
10
```
```
Returns: 17
```
There are six tasks with following start, finish and cost: (1,3,3) (1,2,5) (1,3,1) (1,2,9) (1,3,3) (1,2,5) The optimal solution is to pick tasks with costs 9, 5 and 3 (any subset with these costs can be completed in some order).
```
4
```
```
3
```
```
2
```
```
1
```
```
2
```
```
2
```
```
100
```
```
Returns: 118
```
```
10
```
```
5
```
```
5
```
```
5
```
```
9
```
```
3
```
```
10
```
```
Returns: 23
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.