Connection Status:
Competition Arena > Moneymanager

Moneymanager

SRM 691 · 2016-05-02 · by subscriber

SRM 691 · 2016-05-02 · by subscriber · Dynamic Programming, Greedy
Class Name: Moneymanager
Return Type: int
Method Name: getbest
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

One day Hero realized that he has zero experience with practical projects. Thus, he decided to spend one whole year on projects, gaining some experience and making some money along the way. Hero already chose which projects he is going to do. All that remains is to choose the order in which he'll do them. Each project can be described by two positive integers a[i] and b[i]. More precisely, when Hero works on project i, the following two things happen, in order:
  1. First, his work on the project increases his experience by a[i].
  2. Then, when the project is done, he earns money for the project. The amount earned is (b[i] * E), where E is his total amount of experience at the moment of finishing the project.
The number of projects Hero has planned is even. In addition to the projects, Hero has one extra plan: after finishing exactly one half of the projects, he wants to attend a training camp. The training camp will increase his experience by X. He will not earn any money at the training camp. At the beginning, Hero has no experience and no money. You are given the int[]s a and b (both with the same number of elements; that number is even) and the int X. Find and return the maximum total amount of money Hero can earn during the year.

Constraints

  • Number of elements in a will be between 2 and 50, inclusive.
  • Number of elements in a will be even.
  • a and b will contain the same number of elements.
  • Each element in a will be between 1 and 100,000, inclusive.
  • Each element in b will be between 1 and 10, inclusive.
  • X will be between 0 and 100,000, inclusive.
Examples
0)
{1,1}
{2,1}
0
Returns: 5

An optimal solution: Hero works on project #1 (zero-based index). He first gains 1 experience and then he makes 1*1 = 1 money. Hero goes to the training camp and gains X=0 experience. Hero works on project #0. He first gains 1 experience and then he makes 2*2 = 4 money. The total amount of money earned during this solution is 1 + 4 = 5.

1)
{1,1}
{1,5}
10
Returns: 61

An optimal solution: Hero works on project #0. He first gains 1 experience and then he makes 1*1 = 1 money. Hero goes to the training camp and gains 10 experience. Hero works on project #1. He first gains 1 experience and then he makes 5*12 = 60 money. The total amount of money earned during this solution is 1 + 60 = 61.

2)
{4,4,6,6}
{2,2,3,3}
100
Returns: 726

One optimal solution: project #0, project #1, training camp, project #3, project #2.

3)
{44,68,47,81,34,91,24,5,85,59,7,9,100,18,6,34,1,79,91,99,60,2,24,85,96,11,40,13,30,89,74,78,72,13,14,33,96,69,14,18,14,63,95,71,87,57}
{7,4,4,4,1,7,6,5,3,7,2,7,3,1,3,3,3,1,2,7,3,1,5,7,2,1,6,4,3,1,5,6,2,7,5,4,3,7,5,1,6,6,4,6,4,5}
40
Returns: 327332
4)
{43,97,33,97,77,57,67,84,45,30,13,3,3,73,72,49,36,91,11,24,68,76,47,24,37,12,27,98,70,73,29,56}
{5,1,6,3,4,4,3,5,4,4,5,5,5,3,3,6,5,4,5,4,2,7,2,4,3,5,5,2,2,3,5,6}
29
Returns: 159618

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

Coding Area

Language: C++17 · define a public class Moneymanager with a public method int getbest(vector<int> a, vector<int> b, int X) · 89 test cases · 2 s / 256 MB per case

Submitting as anonymous