Overview

This is a problem about destroying \(N\) rocks in order. For each rock, you choose either a “hammer (reduces hardness by 1)” or “dynamite (destroys in one hit)”, and you need to find the minimum number of turns to destroy all rocks while using dynamite at most \(K\) times effectively.

Analysis

First, consider the case where all rocks are destroyed using only the hammer. In this case, destroying rock \(i\) takes \(H_i\) turns, so the total number of turns is \(\sum_{i=1}^{N} H_i\).

Next, consider the case where dynamite is used on rock \(i\). - Hammer: Takes \(H_i\) turns - Dynamite: Takes only 1 turn

In other words, by using dynamite on rock \(i\), we can reduce the number of turns by \(H_i - 1\). However, if a rock originally has hardness \(H_i = 1\), using dynamite still consumes 1 turn just like the hammer, so the number of turns saved is \(0\).

To find the minimum number of turns, we need to maximize the “number of turns saved (\(H_i - 1\))” using the limited \(K\) uses of dynamite.

Algorithm

1. Calculate the total number of turns total_hammer_turns if all rocks are destroyed with the hammer.
2. For each rock, calculate the number of turns saved by using dynamite, \(H_i - 1\), and store them in a list (savings).
   • If \(H_i = 1\), the savings are \(0\), so there is no need to include it in the calculation (including it does not change the result).
3. Sort the list in descending order by the number of turns that can be saved.
4. Take up to \(K\) elements from the beginning of the list and compute their sum as the “maximum reduction.”
5. total_hammer_turns - maximum reduction is the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing the sum of rock hardnesses takes \(O(N)\), and sorting the saved turns takes \(O(N \log N)\). Since \(N = 2 \times 10^5\), this is well within the time limit.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the lists storing each rock’s hardness and savings.

Implementation Notes

• Fast input: Since \(N\) can be large, in Python using sys.stdin.read().split() to read all input at once can reduce execution time.

• Using slices: By using slices like savings[:k], even if \(K\) is larger than the number of rocks, no error occurs, and you can safely compute the sum of “up to \(K\) elements.”

• Large numbers: The total number of turns can be very large (up to about \(2 \times 10^{14}\)), but since Python natively supports arbitrary-precision integers, you can compute without worrying about overflow.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します。
    # sys.stdin.read().split() は大量の入力を効率的に処理するのに適しています。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 岩の個数, K: ダイナマイトの最大使用回数
    n = int(data[0])
    k = int(data[1])
    
    # h: 各岩の硬度のリスト
    # 入力の3番目の要素以降が各岩の硬度 H_i に対応します。
    h = list(map(int, data[2:]))
    
    # すべての岩をハンマーのみで破壊した場合の合計ターン数を計算します。
    # 各岩 i に対して H_i 回のハンマー叩きが必要です。
    total_hammer_turns = sum(h)
    
    # ダイナマイトを岩 i に使用した場合、その岩は1ターンで破壊されます。
    # つまり、ハンマーで破壊する場合に比べて (H_i - 1) ターンを節約できます。
    # ただし、H_i = 1 の場合はハンマーでもダイナマイトでも1ターンのため、節約分は 0 です。
    # 節約できるターン数が 0 より大きいもの（H_i > 1）をリストに抽出します。
    savings = []
    for val in h:
        if val > 1:
            savings.append(val - 1)
    
    # 節約できるターン数が多い順にソートします。
    # ダイナマイトの使用回数 K に制限があるため、節約効率が良い岩から優先的に使います。
    savings.sort(reverse=True)
    
    # 最大で K 個のダイナマイトを使用し、節約できるターンの合計（最大削減量）を求めます。
    # Pythonのスライス savings[:k] は、k がリストの長さを超えていても適切に処理されます。
    max_reduction = sum(savings[:k])
    
    # 最小ターン数 = (ハンマーのみの合計ターン数) - (ダイナマイトによる最大削減量)
    print(total_hammer_turns - max_reduction)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.