Overview

We want to find the minimum total movement distance (cost) required to bring each car’s position \(A_i\) within the interval \([0, M]\).

Analysis

The key point of this problem is that there are no constraints between cars. In other words:

• Moving one car to any position does not affect the movement of other cars
• Multiple cars may occupy the same coordinate after moving

Therefore, the overall minimum cost is simply the sum of placing each car into the interval \([0,M]\) at minimum cost across all \(N\) cars.

Now, what is the minimum cost when a single car is at coordinate \(x\)?

• When \(0 \le x \le M\): It is already within the range, so no movement is needed and the cost is \(0\)
• When \(x < 0\): The nearest point within the range is \(0\), so moving it to \(0\) is optimal. The cost is \(|x-0| = -x\)
• When \(x > M\): The nearest point within the range is \(M\), so moving it to \(M\) is optimal. The cost is \(|x-M| = x-M\)

Naively searching for “where to move each car” or trying to optimize all cars together would be unnecessarily complex, but thanks to the independence property of this problem, it reduces to the simple form of just summing up each car’s “overflow amount”.

Concrete example: When \(M=10\) - \(x=-3\) → Move to \(0\) (cost \(3\)) - \(x=5\) → Stay as is (cost \(0\)) - \(x=13\) → Move to \(10\) (cost \(3\))

The total \(3+0+3=6\) is the minimum.

Algorithm

1. Initialize total cost ans = 0
2. For each \(A_i\), do the following:
   • If \(A_i < 0\), then ans += -A_i (distance to bring it back to \(0\))
   • If \(A_i > M\), then ans += A_i - M (distance to bring it back to \(M\))
   • Otherwise (\(0 \le A_i \le M\)), add nothing
3. Output ans

This is equivalent to performing a “projection (clipping) onto the interval” for each point and summing up the movement distances.

Complexity

• Time complexity: \(O(N)\) (just examining each car once)
• Space complexity: \(O(1)\) (only a constant number of variables besides the input)

Implementation Notes

• Since \(N\) can be up to \(2\times 10^5\), in Python you can use sys.stdin.buffer.read() for faster input.

• The total cost can be up to around \(N \times 10^9\), but since Python’s int supports arbitrary precision, there is no concern about overflow.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    A = data[2:2+N]

    ans = 0
    for x in A:
        if x < 0:
            ans += -x
        elif x > M:
            ans += x - M
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.