PROBLEM STATEMENT
TopCoder member MEL87H noticed that the time she spends on a problem is
uniquely defined by the point value of the problem. Her submissions always pass
the system test and she never submits a problem more than once. She also knows
how points are assigned. This means that by looking at the points for the
current match's problems, she knows exactly how many points she can get for
each problem and how much time she would spend on each problem. This allows her
to design a strategy for choosing which problems to solve to maximize her score.
You will receive as input an int[], problemPoints, with the point values for
each problem, another int[], times, with the amount of time in minutes required
for MEL87H to solve each problem, and an int[], problemScores, with the scores
she would get for each submitted solution to a problem. You have to return the
maximum score she can get.
NOTES
- The match lasts exactly 75 minutes. If MEL87H solves some set of problems in
exactly 75 minutes, we assume she is able to submit that set of problems.
- The first element of each int[]: problemPoints, times, and problemScores
corresponds to the easy problem, the second element to the medium problem and
the third element to the hard problem.
DISCLAIMER
Input problem scores don't reflect the scores TopCoder would actually assign to
MEL87H for submitting a problem in the specified time in a real competition.
DEFINITION
Class: SRM
Method: bestScore
Parameters: int[] int[] int[]
Returns: int
Method signature (be sure your method is public): int bestScore(int[]
problemPoints, int[] times, int[] problemScores);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- problemPoints contains exactly three elements
- problemPoints is sorted in ascending order
- elements of problemPoints are different from each other
- each element of problemPoints is between 200 and 1200 inclusive and is
divisible by 50
- times contains exactly 3 elements
- each element of times is between 1 and 200 inclusive
- problemScores contains exactly 3 elements
- each element of problemScores is less than the corresponding point value for
a problem and greater than or equal to the corresponding point value multiplied
by .3
EXAMPLES
1. problemPoints[] = {250, 500, 750},
times = {25, 50, 75},
problemScores = {218, 192, 268},
MEL87H will be able to solve the first and the second problem together or only
the third problem; the first choice is better;
return 410
2. problemPoints[] = {250, 750, 1000},
times = {12, 38, 50},
problemScores = {196, 414, 384},
MEL87H will be able to solve the first and the second problem together or the
first and the third problem together; the first choice is better;
return 610
3. problemPoints[] = {300, 800, 1200},
times = {6, 16, 24},
problemScores = {282, 550, 593},
MEL87H will be able to solve all three problems;
return 1425
4. problemPoints[] = {250, 500, 1200},
times = {25, 25, 24},
problemScores = {118, 237, 593},
MEL87H will be able to solve all three problems;
return 948
5. problemPoints[] = {250, 500, 1200},
times = {26, 26, 25},
problemScores = {117, 235, 590},
MEL87H will be able to solve two out of the three problems - the optimal
choices are the second and the third problems;
return 825
6. problemPoints[] = {250, 500, 1000},
times = {100, 100, 100},
problemScores = {75, 150, 300}, return 0