/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は採掘場で働いています。採掘場には N 個の岩が一列に並んでおり、これらをすべて破壊する必要があります。
i 番目の岩は硬度 H_i を持っています。高橋君は 1 番目の岩から順に N 番目の岩まで、1つずつ処理していきます。ある岩を破壊しない限り、次の岩の処理に移ることはできません。
高橋君は毎ターン、以下の2つの行動のうちいずれか1つを選んで実行します。
- ハンマーで叩く: 現在処理中の岩の硬度を 1 減らす。このとき 1 ターンを消費する。
- ダイナマイトを使う: 現在処理中の岩の硬度を即座に 0 にする。このとき 1 ターンを消費する。ただし、ダイナマイトは合計で K 個しか持っておらず、使用するたびに 1 個消費される。残りが 0 個のときはこの行動を選ぶことはできない。
岩の硬度が 0 になると、その岩は破壊され、次の岩の処理に移ります。すべての岩を破壊すると作業完了です。
高橋君が最適に行動したとき、すべての岩を破壊するのに必要な最小ターン数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq H_i \leq 10^9
- 入力はすべて整数
入力
N K H_1 H_2 \ldots H_N
- 1 行目には、岩の個数を表す整数 N と、ダイナマイトの個数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各岩の硬度を表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
出力
すべての岩を破壊するために必要な最小ターン数を 1 行で出力してください。
入力例 1
3 1 5 2 8
出力例 1
8
入力例 2
5 2 10 3 7 4 6
出力例 2
15
入力例 3
8 3 100 5 200 8 150 3 50 300
出力例 3
169
Score : 366 pts
Problem Statement
Takahashi works at a quarry. There are N rocks lined up in a row at the quarry, and he needs to destroy all of them.
The i-th rock has hardness H_i. Takahashi processes the rocks one by one in order from the 1-st rock to the N-th rock. He cannot move on to processing the next rock until the current rock is destroyed.
Each turn, Takahashi chooses and performs exactly one of the following two actions:
- Strike with a hammer: Reduce the hardness of the rock currently being processed by 1. This consumes 1 turn.
- Use dynamite: Instantly reduce the hardness of the rock currently being processed to 0. This consumes 1 turn. However, Takahashi only has K sticks of dynamite in total, and each use consumes 1 stick. This action cannot be chosen when he has 0 sticks remaining.
When a rock's hardness becomes 0, that rock is destroyed, and he moves on to processing the next rock. The work is complete once all rocks are destroyed.
Find the minimum number of turns required to destroy all rocks when Takahashi acts optimally.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq H_i \leq 10^9
- All inputs are integers
Input
N K H_1 H_2 \ldots H_N
- The first line contains an integer N representing the number of rocks and an integer K representing the number of dynamite sticks, separated by a space.
- The second line contains integers H_1, H_2, \ldots, H_N representing the hardness of each rock, separated by spaces.
Output
Print the minimum number of turns required to destroy all rocks in a single line.
Sample Input 1
3 1 5 2 8
Sample Output 1
8
Sample Input 2
5 2 10 3 7 4 6
Sample Output 2
15
Sample Input 3
8 3 100 5 200 8 150 3 50 300
Sample Output 3
169