Connection Status:
Competition Arena > HeroicSchedule

HeroicSchedule

SRM 726 · 2017-12-18 · by subscriber

SRM 726 · 2017-12-18 · by subscriber · Greedy
Class Name: HeroicSchedule
Return Type: int
Method Name: getmax
Arg Types: (int, int, int, int, int, int, int)
Problem Statement

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

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
0)
2000000
111111
22222
33333
1000
1000
1000
Returns: 1994616
1)
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.

2)
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).

3)
4
3
2
1
2
2
100
Returns: 118
4)
10
5
5
5
9
3
10
Returns: 23

Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HeroicSchedule with a public method int getmax(int n, int A, int B, int C, int modStart, int modLen, int modCost) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous