## Mock CCC '24 Contest 1 S4 - Tommy's Lemonade Stand

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Tommy's passion for lemons led him to embark on a delightful venture – running a lemonade stand! Driven by his desire to create not just a refreshing beverage but also an economically savvy concoction, Tommy meticulously crafts a collection of lemonade recipes. Each recipe is a carefully balanced blend of lemons, sugar, and mint, contributing to both the overall cost and flavour of the lemonade.

Tommy's curiosity has now turned to understanding the intricate relationship between the cost of ingredients and the flavour ratings of his lemonade recipes. The recipe is characterized by three constants – , , and – that influence how the flavour ratings evolve after adding mL of water. Specifically, the flavour ratings can be calculated as . Additionally, Tommy can add any amount of water he wants to each recipe, and he will incur a cost of one dollar for every millilitre of water added. Since Tommy is not a wizard, he cannot add a negative amount of water.

Given Tommy's financial constraints, he finds himself in a situation where he can only afford a lemonade stand capable of supporting him to produce lemonade with up to recipes. Despite the financial challenges, Tommy is determined to ensure that his lemonade stand exudes diversity and uniqueness. Therefore, with careful consideration, he aims to select exactly recipes that offer a varied and appealing range of flavours to attract a broad customer base.

Tommy, with a keen eye on maximizing his lemonade stand's profit, has defined profitability as the ratio of the sum of flavour ratings to the sum of costs. In his quest for the most sought-after lemonade stand in town, Tommy seeks your expertise to determine the maximum possible profitability. Your task is to assist Tommy in selecting a subset of size from the lemonade recipes that will result in the highest achievable profitability.

#### Input Specification

The first line of input contains two space-separated integers, and .

The following lines of input each contain three space-separated integers, , , and .

The following table shows how the available marks are distributed.

Marks Awarded
marks
marks

#### Output Specification

Output the highest achievable profitability of selected recipes.

Your answer will be considered correct if it is within an absolute or relative error of .

#### Sample Input

5 3
1 1 1
3 2 4
4 6 7
6 4 10
4 7 6

#### Sample Output

-2.662422376

#### Explanation for Sample

Tommy is dealing with five lemonade recipes, and he can afford to choose three recipes for his stand. The recipe , , and have respective flavor rating of , , and . The profitability is calculated by dividing the sum of flavour ratings by the sum of costs. After thorough evaluation, the highest achievable profitability is which is approximately , making this combination of recipes the most lucrative for Tommy's lemonade stand.