시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 40 | 15 | 15 | 38.462% |
Heidi is in a big store. She would like to purchase $n$ items.
Today is her lucky day. The store runs a special sale: on every purchase, the customer receives one of the following two promotions:
Heidi would like to buy all $n$ items on her shopping list, each exactly once. She can make an arbitrary number of purchases. For each purchase she'll make, the appropriate promotion will apply.
What is the minimum total price she has to pay to buy all $n$ items?
The first line contains two single space-separated integers $n$ ($1 \le n \le 100\,000$) and $q$ ($0 \le q \le 100$) — the number of items Heidi wants to buy and the percentage discount she gains for purchases of fewer than three items.
The following line contains $n$ single space separated integers $p_1, \dots, p_n$ — the prices of the goods ($100 \le p_i \le 100\,000$, $1 \le i \le n$).
Additionally, it is guaranteed that each $p_i$ will always be divisible by $100$. Hence, the discounted price of each purchase will always be an integer.
Output a single integer — the minimum total price Heidi has to pay in order to buy all $n$ items.
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | $n = 3$ and $100 \le p_i \le 1000$ ($1 \le i \le 3$) |
2 | 18 | $q = 0$ |
3 | 16 | $q = 40$ |
4 | 22 | $100 \le p_i \le 1\,000$ ($1 \le i \le n$) |
5 | 36 | No additional constraints |
7 10 300 200 200 300 100 300 200
1090
3 20 1000 500 100
1280
4 0 200 100 300 200
600
First, Heidi can buy the three items that cost $200$ in a single transaction for $400$ (she gets one of them for free). Then she can purchase the three items that cost $300$ for $600$ (again, one is free). Finally, she can purchase the last remaining item (with cost $100$) with a $10\%$ discount.
In the second example test, if Heidi buys all three items in a single transaction, she receives discount of $100$. However, if she buys each item individually, her discount will be $(1000 + 500 + 100) \cdot 20 / 100 = 320$.