Overview

Given \(N\) devices, you must choose exactly \(K\) of them to set to energy-saving mode, which halves their power consumption (rounded down). The goal is to minimize the total power consumption.

Analysis

To minimize the total power consumption, the key insight is to focus on the “reduction amount” — that is, “how much power can be saved by setting each device to energy-saving mode.”

For each device \(i\), the power reduction \(D_i\) when set to energy-saving mode can be expressed as: $\(D_i = A_i - \lfloor A_i / 2 \rfloor\)$

For example, if \(A_i = 13\), the power after energy-saving mode is \(\lfloor 13 / 2 \rfloor = 6\), so the reduction is \(13 - 6 = 7\).

In this problem, we need to set exactly \(K\) devices to energy-saving mode. To minimize the overall total, the optimal strategy is to select the \(K\) devices with the largest reduction \(D_i\), in descending order. Since each device can be set to energy-saving mode at most once, a simple greedy approach of computing and comparing the reductions is applicable.

Algorithm

The problem can be solved with the following steps:

1. For each device \(i\), compute the reduction \(D_i = A_i - (A_i // 2)\) and store it in a list.
2. Sort the list of reductions in descending order.
3. Sum the first \(K\) elements of the list. This gives the “maximum total reducible power.”
4. Output the total initial power consumption of all devices minus the maximum reduction computed in step 3.

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing the reductions takes \(O(N)\), sorting the reduction list takes \(O(N \log N)\), and computing the sum takes \(O(N)\). This is sufficiently fast for the constraint \(N = 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for storing the input data and the list of reductions.

Implementation Notes

• Integer division: In Python, the // operator can be used to obtain the floor (integer value with the fractional part truncated) for positive numbers.

• Fast input: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() is faster than calling input() repeatedly, reducing execution time.

• Handling large values: The final total can be as large as \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\), but since Python natively supports arbitrary-precision integers, there is no need to worry about overflow.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に処理するのに適しています
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # 1番目の要素は機器の台数 N、2番目の要素は省エネモードに設定する台数 K
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 3番目以降の要素は各機器の消費電力 A_i
    # 全ての A_i を整数のリストに変換
    a = list(map(int, input_data[2:]))
    
    # 各機器を省エネモードにしたときに削減できる電力を計算する
    # 消費電力 A_i の機器を省エネモードにすると floor(A_i / 2) になるため、
    # 削減される電力は A_i - floor(A_i / 2) となる。
    # Pythonの // 演算子は正の数に対して小数点以下を切り捨てる（floor）動作をする。
    reductions = [x - (x // 2) for x in a]
    
    # 全体の消費電力を最小化するためには、削減できる電力を最大化すればよい。
    # 削減量のリストを降順（大きい順）にソートする。
    reductions.sort(reverse=True)
    
    # 全機器の初期の消費電力の合計を計算
    total_initial_power = sum(a)
    
    # 削減量が大きい方から K 台分の削減量を合計する
    # スライス reductions[:k] を使うことで、上位 K 個の要素を取得できる。
    max_total_reduction = sum(reductions[:k])
    
    # 最終的な消費電力の合計 = (初期の合計) - (最大化された削減量の合計)
    print(total_initial_power - max_total_reduction)

if __name__ == '__main__':
    solve()

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