시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB227383522.581%

문제

You have to buy $N$ items to prepare RUN Spring Contest.

In Daejeon, there is a famous local currency, Ontongdaejeon.

Using Ontongdaejeon, you can get a cashback point when purchasing an item - precisely 10 percent of the cash you have paid as a cashback point.

If you have already got some cashback point from the previous purchases, you can use it instead of any non-negative integer amount of cash you want.

 Specifically, you can use the cashback point with the following steps:

  1. Let $c$ be the amount of cashback point you already have and $p$ be the price of an item you want to purchase.
  2. You should determine the amount of cashback point to use. Let this be $x$.
  3. $x$ should satisfy following conditions:
    • $x \le p$
    • $x \le c$
    • $x$ must be an non-negative integer.
  4. Then, you can use $x$ cashback points and $p-x$ cash to buy the item.
  5. After buying the item, the cashback point you would have is $(c-x) + \dfrac{p-x}{10}$.

Find the minimum amount of cash required to buy $N$ items in a given order.

Before buying the first item, you have no cashback points.

입력

The first line contains one integer $N$, where $N$ denotes the number of items.

The second line contains $N$ space-separated integers $P_1. P_2, ..., P_N$ where $P_i$ denotes the price of $i$-th item.

출력

Find the minimum amount of cash required to buy all $N$ items in a given order using Ontongdaejeon.

제한

  • $1 \le N \le 200\,000$
  • $1 \le P_i \le 10^9$ $(1 \le i \le N)$

서브태스크 1 (14점)

This subtask has an additional constraint:

  • $N \le 2$

서브태스크 2 (26점)

This subtask has additional constraints:

  • $N \le 100$
  • $P_i \le 100$ ($1 \le i \le N$)

서브태스크 3 (60점)

This subtask has no additional constraint.

예제 입력 1

3
100 10 12

예제 출력 1

111

예제 입력 2

1
100

예제 출력 2

100

출처

University > KAIST > 2022 KAIST RUN Spring Contest B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.