TheProgrammingContestDivOne
SRM 502 · 2010-11-01 · by rng_58
Problem Statement
The duration of the contest is T minutes and they are given N tasks. Solutions can be submitted at any time during the contest, including exactly T minutes after the start of the contest. If they solve the i-th task immediately after the start of the contest, they get maxPoints[i] points and it decreases by pointsPerMinute[i] points per minute. In other words, if they solve the i-th task t minutes after the start of the contest, they will get maxPoints[i] - t * pointsPerMinute[i] points. It takes them requiredTime[i] minutes to solve the i-th task.
Return the maximal points they can get.
Constraints
- T will be between 1 and 100,000, inclusive.
- maxPoints will contain between 1 and 50 elements, inclusive.
- maxPoints, pointsPerMinute and requiredTime will contain the same number of elements.
- Each element of maxPoints will be between 1 and 100,000, inclusive.
- Each element of pointsPerMinute will be between 1 and 100,000, inclusive.
- Each element of requiredTime will be between 1 and 100,000, inclusive.
100000
{652, 743, 587, 4926}
{6, 5, 3, 4}
{4, 5, 3, 6}
Returns: 6731
90
{742, 207}
{20, 13}
{82, 20}
Returns: 0
100000
{100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 4998725
80
{290, 787, 919}
{1, 12, 7}
{5, 57, 65}
Returns: 714
1
{1}
{1}
{1}
Returns: 0
74
{502}
{2}
{47}
Returns: 408
They can solve the task 47 minutes after the start of the contest. They will get 502 - 2 * 47 = 408 points.
40000
{100000, 100000}
{1, 100000}
{50000, 30000}
Returns: 0
They don't have time to solve the first task. If they solve the second task, they will get negative points (100000 - 100000 * 30000 = -2999900000 points), so they shouldn't solve it.
75
{250, 500, 1000}
{2, 4, 8}
{25, 25, 25}
Returns: 1200
First, they can solve the third task 25 minutes after the start of the contest. They get 1000 - 8 * 25 = 800 points. Second, they can solve the second task 50 minutes after the start of the contest. They get 500 - 4 * 50 = 300 points. Third, they can solve the first task 75 minutes after the start of the contest. They get 250 - 2 * 75 = 100 points. In total, they can get 800 + 300 + 100 = 1200 points.
30
{100, 100, 100000}
{1, 1, 100}
{15, 15, 30}
Returns: 97000
The best strategy is solving only the third task.
Submissions are judged against all 158 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheProgrammingContestDivOne with a public method int find(int T, vector<int> maxPoints, vector<int> pointsPerMinute, vector<int> requiredTime) · 158 test cases · 2 s / 256 MB per case