Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. 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.
Для отправки решений необходимо выполнить вход.
|