SpecialAgent | Topcoder Archive

Problem Statement

Joe is a special agent. He has several missions he can complete. Now it is day 0. The i-th mission must be completed on day i, and it takes days[i] to complete the mission (including the day it must be completed). For example, if the mission must be completed on day 4 and it takes 3 days, it must be started on day 2 (and takes days 2, 3 and 4). If Joe completes the i-th mission, he receives pays[i] dollars.

Completing a mission is very difficult, so Joe must rest for at least k days after each mission. Return the maximal total pay Joe can get.

Definition

Class:: SpecialAgent
Method:: maxIncome
Parameters:: int[], int[], int
Returns:: int
Method signature:: int maxIncome(int[] days, int[] pays, int k)
(be sure your method is public)

Constraints

days will contain between 1 and 50 elements, inclusive.
Each element of days will be between 1 and 50, inclusive.
pays will contain the same number of elements as days.
Each element of pays will be between 1 and 1000, inclusive.
k will be between 0 and 50, inclusive.

Examples

```
{1,1,1,1}
```
```
{1,3,5,1}
```
```
1
```
```
Returns: 6
```
It is optimal to perform missions 0 and 2. It is impossible to perform missions 1 and 2 because Joe needs to rest for 1 day between missions.
```
{1,2,1,4}
```
```
{1,3,1,3}
```
```
0
```
```
Returns: 4
```
It is best to perform missions 1 and 2.
```
{2,2}
```
```
{3,2}
```
```
0
```
```
Returns: 2
```
Joe cannot perform mission 0 - it must end on day 0, but needs 2 days to be completed.

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.