HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN112 Questions 2016 > problem:


15-HW-5. 50935 - Max Discount

CEN112 Questions 2016

Start: Mar.30.2016 at 03:10:22 PM
Finish: Apr.01.2016 at 05:00:00 AM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (3)

Contest problems

• 15-FE-3. 50994 - The Most Crowded...
• 15-FE-4. 50995 - Group Average
• 15-FE-6. 50989 - Rectangles and Points
• 15-FE-7. 50990 - Two Neighbors
• 15-FE-8. 50991 - Intersecting Circles
• 15-HW-2. 50932 - Shifting rows and...
• 15-HW-3. 50933 - Sum of the Bigges...
• 15-HW-4. 50934 - Selling Cars
• 15-HW-5. 50935 - Max Discount
• 15-MdtE-1. 50915 - Trip to Korca
• 15-MdtE-2. 50916 - Ascending Num...
• 15-MdtE-3. 50913 - Manhattan Distance
• 15-MdtE-4. 50917 - Descending Nu...
• 15-MdtE-5. 50912 - Trip to Librazhd
• 15-MdtE-6. 50914 - Buy 3, Pay 2
• 15-PE-1. 50865 - Apartment Building...
• 15-PE-2. 50866 - Buy the cheapest

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Max Discount

The promotional season is over. The administration is happy with the results. And, they want to continue the campaign with a small change. As in previous Buy3 Pay2 campaign, the clients are free to choose any consecutive 3 items in the given order. Then, the cheapest of the group (3 items) will be free. However, this time clients cannot change the order of items. The purpose is to maximize the discount.

Question: Write a program that takes price of n items, then maximizes the profit for the client.

Input specification
You will be given an integer in the beginning: the number of items (n). In the following line, you will be given n integers, prices of n items where 0 ≤ n ≤ 30

Output specification:
Show one integer: max discount that the client can get.

Sample Input I
7
10 20 17 7 16 19 16
Sample Output I
26
Sample Input II
8
8 15 16 12 20 18 16 15
Sample Output II
28

Explanation:
For sample 1: Without changing the order of items, the client can choose (10 + 20 + 17) (16 + 19 + 16) and have $26 discount.
For sample 2: The client can choose (20 + 18 + 16) (15 + 16 + 12) and have $28 discount.



Для отправки решений необходимо выполнить вход.

www.contester.ru