Overview

This problem involves delivering packages from a warehouse located at coordinate \(0\) on a one-dimensional line to multiple destinations using a cart with capacity \(K\). By considering the positive and negative directions independently and greedily delivering to the farthest destinations first, we can find the minimum total travel distance.

Key Observations

There are three important insights for solving this problem:

1. The positive and negative directions can be considered independently Consider a delivery route that delivers packages to both a positive coordinate \(a > 0\) and a negative coordinate \(b < 0\) in a single trip. The travel distance would be \(a + |a - b| + |-b| = 2a + 2|b|\). This is exactly the same as making separate round trips to \(a\) (distance \(2a\)) and to \(b\) (distance \(2|b|\)). Therefore, there is no benefit to mixing deliveries in the positive and negative directions, and we can calculate them completely separately.

2. Process farther destinations first (greedy approach) When traveling to a far destination, we can deliver packages to closer destinations along the way. To minimize travel distance, the optimal strategy is to process destinations from farthest to nearest, using the remaining capacity on the cart during the last round trip to a destination for delivering to closer destinations.

3. Batch calculations to avoid TLE Since the number of packages \(D_i\) can be up to \(10^9\), a naive approach that processes packages one by one or simulates each round trip individually will result in Time Limit Exceeded (TLE). Therefore, we need to use division to compute the required number of round trips in \(O(1)\).

Algorithm

1. Divide the destinations into a group with positive coordinates and a group with negative coordinates. For negative coordinates, take the absolute value and treat them as distances from the warehouse.
2. Sort each group in descending order of distance from the warehouse (farthest first).
3. For each group, perform the following calculation:
   • Initialize the remaining loading capacity capacity of the cart to \(0\).
   • Process destinations in order from farthest to nearest.
   • First, for the current destination’s required quantity \(d\), consume the capacity carried over from farther destinations (reduce both \(d\) and capacity).
   • If \(d > 0\) still remains, round trips between the warehouse and this destination are needed.
   • The required number of round trips trips is \(\lceil d / K \rceil\).
   • Add \(2 \times x \times trips\) to the total travel distance.
   • Calculate the remaining capacity after these round trips and update capacity for the next closer destination.

Complexity

• Time complexity: \(O(N \log N)\)
  • Grouping destinations and processing each destination takes \(O(N)\), but sorting in descending order of distance takes \(O(N \log N)\), giving the overall time complexity.
• Space complexity: \(O(N)\)
  • Arrays storing destinations in the positive and negative directions each hold at most \(N\) elements, requiring \(O(N)\) memory.

Implementation Tips

• Ceiling division technique: The required number of round trips trips can be computed as (d + K - 1) // K, which performs ceiling division without conditional branching.

• Remaining capacity calculation: capacity = (K - (d % K)) % K is a concise way to correctly set capacity to \(0\) when \(d\) is exactly divisible by \(K\) (i.e., all packages fit perfectly with no remaining space).

• Unified processing: By converting negative coordinate groups to their absolute values as -x at the input stage, we can compute the answer using exactly the same loop logic as for the positive group.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    
    pos = []
    neg = []
    
    idx = 2
    for _ in range(N):
        x = int(data[idx])
        d = int(data[idx+1])
        idx += 2
        if x > 0:
            pos.append((x, d))
        else:
            neg.append((-x, d))
            
    pos.sort(key=lambda item: item[0], reverse=True)
    neg.sort(key=lambda item: item[0], reverse=True)
    
    ans = 0
    
    for group in (pos, neg):
        capacity = 0
        for x, d in group:
            if capacity > 0:
                take = min(d, capacity)
                d -= take
                capacity -= take
            
            if d > 0:
                trips = (d + K - 1) // K
                ans += 2 * x * trips
                capacity = (K - (d % K)) % K
                
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.