Connection Status:
Competition Arena > AlienAndHamburgers

AlienAndHamburgers

SRM 605 · 2013-12-22 · by Witaliy

SRM 605 · 2013-12-22 · by Witaliy · Brute Force, Greedy, Sorting
Class Name: AlienAndHamburgers
Return Type: int
Method Name: getNumber
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Alien Fred wants to destroy the Earth. But before he does that, he wants to eat some hamburgers.

You are given two int[]s: type and taste. They describe all hamburgers available in the shop he found. Each hamburger has a type (some positive integer) and a taste (some, possibly negative, integer). For each i, type[i] represents the type of i-th hamburger (0-based index), and taste[i] represents the taste of i-th hamburger. It is possible that different hamburgers have the same type but a different taste.

Fred wants to eat some subset of those hamburgers (possibly none or all of them). Eating the chosen hamburgers will give him some amount of joy. This amount can be computed as Y * A, where Y is the number of different types of hamburgers eaten, and A is their total taste.

Return the largest possible amount of joy he can get.

Constraints

  • type will contain between 1 and 50 elements, inclusive.
  • type and taste will contain the same number of elements.
  • Each element of type will be between 1 and 100, inclusive.
  • Each element of taste will be between -100,000 and 100,000, inclusive.
Examples
0)
{1, 2}
{4, 7}
Returns: 22

In this case, the best choice is to choose both hamburgers. The number of different types is 2, and the total taste is 11. Thus, the answer is 2*11 = 22.

1)
{1, 1}
{-1, -1}
Returns: 0

Note that sometimes the best choice is not to eat any hamburgers. In such a case the amount of joy is 0.

2)
{1, 2, 3}
{7, 4, -1}
Returns: 30
3)
{1, 2, 3, 2, 3, 1, 3, 2, 3, 1, 1, 1}
{1, 7, -2, 3, -4, -1, 3, 1, 3, -5, -1, 0}
Returns: 54
4)
{30, 20, 10}
{100000, -100000, 100000}
Returns: 400000

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

Coding Area

Language: C++17 · define a public class AlienAndHamburgers with a public method int getNumber(vector<int> type, vector<int> taste) · 151 test cases · 2 s / 256 MB per case

Submitting as anonymous