P9313 [EGOI 2021] Shopping Fever / Shopping Fever

Day 2 Problem A. Translated from [EGOI2021 shoppingfever](https://stats.egoi.org/media/task_description/2021_shoppingfever_en.pdf).

Heidi is in a large store. She wants to buy $n$ items. Today is her lucky day. The store is having a promotion: for each bill, the customer gets one of the following two discounts: 1. If at least $3$ items are bought, the cheapest one is free. 2. If fewer than $3$ items are bought, this bill gets a $q\%$ discount. Heidi wants to buy all $n$ items without buying any item more than once. She may split the purchase into any number of bills. For each bill, the corresponding discount policy will be applied. What is the minimum amount of money she needs to pay to buy all $n$ items?

The first line contains two integers $n, q$ — the number of items and the discount percentage when buying fewer than $3$ items. The second line contains $n$ integers $p_i$ — the prices of the items. It is also guaranteed that each item price is divisible by $100$. Therefore, the discounted price for each bill is always an integer.

One line with one integer — the minimum amount of money needed.

**Explanation for Sample $1$** Heidi first buys three items priced at $200$, paying $400$ (one item is free). Then she buys three items priced at $300$, paying $600$ (again, one item is free). Finally, she buys the remaining item priced at $100$ and gets a $10\%$ discount. --- **Explanation for Sample $2$** If Heidi buys three items in a single bill, she gets a discount of $100$. However, if she buys the three items in three separate bills, the discount becomes $(1000+500+100)\cdot\frac{20}{100}=320$. --- **Constraints** For all testdata, $1\le n\le 10^5$, $0\le q\le 100$, $100\le p_i\le 10^5$, and $100\mid p_i$. - Subtask 1 ($8$ points): $n=3$, $100\le p_i\le 10^3$. - Subtask 2 ($18$ points): $q=0$. - Subtask 3 ($16$ points): $q=40$. - Subtask 4 ($22$ points): $100\le p_i\le 10^3$. - Subtask 5 ($36$ points): no additional constraints. Translated by ChatGPT 5