Overview

For each rock that takes \(H_i\) turns to destroy using only a hammer, this problem asks which rocks to use dynamite on (which destroys in 1 turn) to minimize the total number of turns.

Analysis

There are essentially two ways to destroy each rock:

• Hammer only: Hit rock \(i\) a total of \(H_i\) times, so \(H_i\) turns
• Use dynamite: Destroy in one hit, so \(1\) turn

Therefore, using dynamite on rock \(i\) saves [ H_i - 1 ] turns compared to using only the hammer (this is the “benefit”).

The key insight here is that although rocks must be processed in order, the choice of which rocks to use dynamite on does not affect other rocks.
This is because the number of turns needed to destroy each rock is determined independently, and the total turns is simply their sum.

Thus, the total turns we want to minimize is:

• First, destroying everything with the hammer takes \(\sum H_i\) turns
• Then, for rocks where dynamite is used, replace \(H_i\) with \(1\) (i.e., reduce by \(H_i - 1\))

In other words, “the larger the turn savings \(H_i - 1\), the more valuable it is to use dynamite on that rock.”
Since the ordering of \(H_i - 1\) is the same as the ordering of \(H_i\), the optimal strategy is to greedily select up to \(K\) rocks with the largest hardness \(H_i\) and use dynamite on them (greedy approach).

Why a naive approach doesn’t work

Simulating each turn could require up to \(\sum H_i\) operations, but since \(H_i \le 10^9\), this is far too slow.
This problem doesn’t require “reducing by 1 each turn” — it can be reformulated as simply choosing whether each rock costs \(H_i\) or \(1\), which allows for an efficient solution.

Concrete example

For example, when \(H=[5,2,4],\ K=1\):

• All hammer: \(5+2+4=11\) turns
• Using dynamite on one rock:
  • Use on \(5\): \(11-(5-1)=7\)
  • Use on \(4\): \(11-(4-1)=8\)
  • Use on \(2\): \(11-(2-1)=10\)

Using it on the rock with maximum hardness \(5\) is optimal.

Algorithm

1. Compute \(total = \sum_{i=1}^{N} H_i\) (total turns if using only the hammer).
2. Sort \(H\) in descending order.
3. Take the sum of the top \(K\) elements: \(sum\_k = \sum_{i=1}^{K} H_i\).
4. Since the top \(K\) rocks go from “\(H_i\) turns” to “\(1\) turn”, the total turns become [ total - sum_k + K ]
   • \(-sum\_k\): subtract the original \(H_i\) costs
   • \(+K\): add back since each dynamite use takes 1 turn

※ When \(K=0\), simply output \(total\).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the array)

Implementation notes

• “Maximizing the savings \(H_i - 1\)” is equivalent to “selecting in descending order of \(H_i\)”, so we just need to sort in descending order and use the first \(K\) elements.

• Although \(H_i\) and \(\sum H_i\) can be large, Python’s int has arbitrary precision, so there is no concern about overflow.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    total = sum(H)
    if K == 0:
        print(total)
        return
    H.sort(reverse=True)
    sum_k = sum(H[:K])
    ans = total - sum_k + K
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.