All submissions for this problem are available.
A retail shop has announced a reward point scheme on pairs of items procured by customers. No point is available on purchase of a single item. The scheme is applicable for n (n > 0) different types of items available in the shop. However, a particular customer will be eligible to get reward for upto 7 out of these n types.
Naturally, these items must be bought as pairs. For every pair of such items (may or may not be of similar type), there is an associated point, which may be different for different pairs. After billing, the computer calculates the maximum reward point that the customer can get by suitably pairing the items (upto 7) marked by the customer. Only two items of a particular type will be considered for reward scheme. There is no reward point for more than two items procured of a particular type. Calculate the maximum reward points that a customer can get after he has purchased a few items and marked the ones for which he/she wants reward points.
For example, suppose, n=4 and the pairwise reward metrics are as follows.
Now, if the customer has purchased 2 items each of type 1 and 2 and 4 items of time 3, and has marked 1, 2, 3 as the items on which he/she wants the reward points, the pairing should be (2,3) => 75, (3,2) => 75 and (1,1) => 55 giving a total of 205 points. Note that there were 4 items of type 3, but only 2 should be used for reward point calculations.
The program should use n = 10 and the following reward matrix.
The first line contains an integer (say, m) - the number of test cases (not more than 500). It is followed by m pairs of lines, each corresponding to a test case. The first line of a pair contains 10 integers, identifying the number of items of each type the customer has bought (each integer is not more than 100). He always buys even number of items. The second line is an array of 10 bits corresponding to the 10 different item types. A bit being ‘1’ indicates that the customer wants a reward on that item, a ‘0’ indicates that the customer does not want reward on the item. There will be at-most 7 '1's in this array. Also, the customer will choose a type iff he has bought atleast 2 items of that type. Each entry in a line is separated by a single blank space.
Output m lines, one for each test case. The output for a test case should contain the maximum reward points that the customer can gain upon optimally pairing 2 items of the types he has chosen.
Input: 3 2 4 6 2 0 0 6 4 2 2 1 1 0 1 0 0 1 1 0 0 0 2 4 2 0 6 2 8 2 2 0 1 1 0 0 1 1 1 0 0 2 4 2 2 2 6 6 6 2 2 1 1 0 0 0 1 1 0 0 0 Output: 220 295 264
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.