Overview

This is a problem of finding the minimum cost (total distance moved) to move \(N\) cars from their current positions into the specified range \([0, M]\).

Analysis

The key insight of this problem is that “each car can be moved independently of the other cars.” Therefore, to minimize the total cost, we can individually calculate “the minimum cost to bring each car into the range \([0, M]\)” and then sum them up.

When a car is at coordinate \(x\), the minimum cost to move it into the range \([0, M]\) can be classified as follows:

1. When \(x < 0\) The closest coordinate within the range to \(x\) is \(0\). Therefore, it is optimal to move it to coordinate \(0\), and the cost is \(0 - x = -x\).
2. When \(0 \leq x \leq M\) The car is already within the parking area. There is no need to move it, so the cost is \(0\).
3. When \(x > M\) The closest coordinate within the range to \(x\) is \(M\). Therefore, it is optimal to move it to coordinate \(M\), and the cost is \(x - M\).

In this way, the optimal moving distance can be determined by simply performing a straightforward conditional check for each car.

Algorithm

1. Initialize a variable total_cost to \(0\) to hold the total cost.
2. Check each car’s coordinate \(A_i\) in order.
   • If \(A_i < 0\), add \(-A_i\) to total_cost.
   • If \(A_i > M\), add \(A_i - M\) to total_cost.
   • Otherwise (\(0 \leq A_i \leq M\)), do nothing.
3. After the calculation is complete for all cars, output total_cost.

Complexity

• Time Complexity: \(O(N)\) For \(N\) cars, we scan each element once and perform a constant-time check, so the processing completes in linear time.
• Space Complexity: \(O(N)\) If all input is stored in a list or similar structure, memory is needed to hold the coordinates of \(N\) cars.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), which is relatively large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Handling Large Numbers: The total cost can become very large (up to approximately \(2 \times 10^{14}\)), but since Python natively supports arbitrary-precision integers, you can perform calculations without worrying about overflow.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    # N: 車の台数, M: 駐車可能エリアの上限座標
    n = int(input_data[0])
    m = int(input_data[1])
    
    # a: 各車の現在の座標
    a = map(int, input_data[2:])
    
    total_cost = 0
    for x in a:
        # 座標が 0 未満の場合、0 まで移動させるコストを加算
        if x < 0:
            total_cost += -x
        # 座標が M より大きい場合、M まで移動させるコストを加算
        elif x > m:
            total_cost += x - m
            
    # 合計コストを出力
    print(total_cost)

if __name__ == '__main__':
    solve()

---

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