ICPC ECNA 2019 C - Cheese, If You Please

View as PDF

Submit solution

Points: 25
Time limit: 1.0s
Memory limit: 1G

Problem type
ICPC East Central NA Regional Contest 2019, Problem C

The "We Cut The Cheese" specialty food store sells specialized blendings of cheeses. For example, their Italian Blend is made up of 50\% provolone, 30\% mozzarella and 20\% parmesan, while their African Safari is made up of 74\% domiati, 25\% areesh with just a hint (1\%) of bokmakiri. You started working at the store as a cheese blend taster, but two years and 45 pounds later you have worked your way up to head of the accounting office. Every week the store gets various shipments of cheeses, depending on the time of year, market price and other factors. Given these amounts and the percentages required for each cheese blend, you are asked every week to determine the optimal use of these cheeses to maximize profit. When the store just made a few different cheese blends this could be done by hand, but with business expanding faster than a cheese souffle, the number of blends has also grown to the point where a program is now needed to determine the optimal use of the cheese shipments. So the question is: Are you gouda-nough to write such a program?

Input Specification

Input starts with a line containing two positive integers n m (1 \le n,m \le 50), where n is the number of types of cheese used to make the cheese blends and m is the number of different cheese blends offered by the store. The next line contains n integers w_1 w_2 \ldots w_n (0 \le w_i \le 500), where w_i is the number of pounds of cheese type i that the store has on-hand. Following this are m lines of the form p_1 p_2 p_3 \ldots p_n t (0.0 \le p_i \le 100.0, 0.0 \le t \le 10.0), where p_i indicates the percentage of cheese i found in the blend, and t is the profit per pound for the blend. Percentages are given with one decimal place, profits are given with two decimal places.

Output Specification

Output the maximum profit that can be obtained for the given pounds of cheese, blending percentages and profits, assuming all of the blended cheeses get sold. Round your answer to the nearest penny.

Sample Input 1

3 2
100 150 100
50.0 50.0 0.0 3.20
0.0 50.0 50.0 2.80

Sample Output 1

920.00

Sample Input 2

3 2
100 150 100
50.0 50.0 0.0 3.20
0.0 40.0 60.0 2.80

Sample Output 2

1000.00
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.