Overview

This is a cost minimization problem where we want to set the temperature of each room to the same integer \(T\).
Since the objective function \(\sum S_i|P_i-T|\) is a “weighted absolute value sum,” the optimal \(T\) is the weighted median.

Analysis

This problem asks us to find the integer \(T\) that minimizes the following expression:

\[ f(T)=\sum_{i=1}^{N} S_i \times |P_i-T| \]

Key Insight

Just as the \(T\) that minimizes the unweighted \(\sum |P_i-T|\) is the median,
when weights \(S_i\) are present, the weighted median is optimal.

• Sort the temperatures in ascending order
• Accumulate the weights (here, the room areas) from left to right
• The first temperature where the cumulative weight reaches at least half of the total is the weighted median

Setting \(T\) to this point means that moving 1 unit in either direction will not decrease the cost.

Why a Brute-Force Approach Is Infeasible

For example, trying all values of \(T\) from \(-10^9\) to \(10^9\) results in far too many candidates.
Scanning all rooms for each candidate adds another \(O(N)\) factor, making it completely TLE.

How to Solve It

Sort the temperatures, find the weighted median in a single pass, and then compute the total cost for that \(T\).
This way, the dominant cost is just the \(O(N\log N)\) sorting step.

Algorithm

1. Store the input \((S_i,P_i)\) as \((P_i,S_i)\) in an array and compute the total weight \(W=\sum S_i\).
2. Sort in ascending order of temperature \(P_i\).
3. Prepare \(half=\left\lfloor\frac{W+1}{2}\right\rfloor\) (the threshold for “at least half”).
4. Accumulate weights acc from left to right, and set \(T\) to the first temperature where acc >= half.
5. Compute and output the answer as \(\sum S_i|P_i-T|\).

This procedure is exactly what the provided code implements.

Complexity

• Time complexity: \(O(N\log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (storing room information)

Implementation Notes

• Setting the weighted median threshold as half = (total_weight + 1) // 2 allows us to safely handle “at least half” using integers.

• The cost can become very large, but since Python integers have arbitrary precision, there is no concern about overflow.

• Since the input can be large, using sys.stdin.readline speeds up reading.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    rooms = []
    total_weight = 0

    for _ in range(N):
        s, p = map(int, input().split())
        rooms.append((p, s))
        total_weight += s

    # Weighted median of temperatures
    rooms.sort()  # sort by temperature p
    half = (total_weight + 1) // 2
    acc = 0
    T = rooms[0][0]
    for p, s in rooms:
        acc += s
        if acc >= half:
            T = p
            break

    # Compute minimum cost at weighted median
    ans = 0
    for p, s in rooms:
        ans += s * abs(p - T)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.