Overview

This problem asks for the minimum cost to move cars that are outside the parking area \([0, M]\) into the area. We can consider each car independently and only move cars that are outside the area to the nearest boundary.

Analysis

Key Insight

The key point of this problem is that each car can be moved independently. In other words, moving one car does not affect the movement of any other car.

For each car, we consider the following three cases:

1. If the coordinate is less than \(0\): The car is sticking out to the left of the area, so it needs to be moved to coordinate \(0\)
2. If the coordinate is greater than \(M\): The car is sticking out to the right of the area, so it needs to be moved to coordinate \(M\)
3. If the coordinate is between \(0\) and \(M\) inclusive: The car is already inside the area, so no movement is needed

Why is moving to the boundary optimal?

For example, consider a car at coordinate \(-5\). To bring this car into the area, it needs to be moved at least to coordinate \(0\). Moving it further than coordinate \(0\) (e.g., to coordinate \(3\)) would incur unnecessary extra cost.

Therefore, it is optimal to move cars outside the area to the nearest boundary (\(0\) or \(M\)).

Concrete Example

For \(N = 3\), \(M = 10\), \(A = [-3, 5, 15]\):

• Car 1 (coordinate \(-3\)): Move to \(0\) → Cost \(|-3 - 0| = 3\)
• Car 2 (coordinate \(5\)): Already inside the area → Cost \(0\)
• Car 3 (coordinate \(15\)): Move to \(10\) → Cost \(|15 - 10| = 5\)

Total cost: \(3 + 0 + 5 = 8\)

Algorithm

1. For each car’s coordinate \(A_i\), compute the following:
   • If \(A_i < 0\), add cost \(-A_i\) (= \(|A_i - 0|\))
   • If \(A_i > M\), add cost \(A_i - M\) (= \(|A_i - M|\))
   • If \(0 \leq A_i \leq M\), cost is \(0\)
2. Sum up the costs of all cars and output the result

Complexity

• Time complexity: \(O(N)\)
  • We only need to check and compute once for each car
• Space complexity: \(O(N)\)
  • For storing the input as an array (can be reduced to \(O(1)\) if needed)

Implementation Notes

• Since the coordinates \(A_i\) range from \(-10^9\) to \(10^9\), the total cost can be as large as approximately \(N \times 10^9 \approx 2 \times 10^{14}\). A 64-bit integer type is required, although in Python there is no need to worry about integer overflow.

• Be careful with boundary values: cars at \(A_i = 0\) or \(A_i = M\) do not need to be moved (make sure to correctly use \(<\) and \(>\) in the conditions).

  Source Code

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    total_cost = 0
    for a in A:
        if a < 0:
            # 座標が0未満の場合、0まで移動
            total_cost += -a
        elif a > M:
            # 座標がMより大きい場合、Mまで移動
            total_cost += a - M
        # 0 <= a <= M の場合は移動不要（コスト0）
    
    print(total_cost)

solve()

---

This editorial was generated by claude4.5opus.