Overview

This problem asks you to calculate how much battery remains in \(N\) smartphones at time \(T\), and find the total.

Analysis

Key Insight

For each smartphone, the battery remaining at time \(T\) can be calculated independently.

Considering the battery remaining for smartphone \(i\): - Initial charge: \(A_i\) mAh - Consumption over \(T\) seconds: \(B_i \times T\) mAh

A simple calculation gives \(A_i - B_i \times T\), but there is a condition that the battery remaining cannot go below \(0\).

Verification with Examples

For example, when \(A = 100\), \(B = 3\), \(T = 50\): - Consumption is \(3 \times 50 = 150\) mAh - Simple calculation gives \(100 - 150 = -50\) mAh - However, in reality the battery runs out partway through, so the remaining is \(0\) mAh

Conversely, when \(A = 100\), \(B = 1\), \(T = 50\): - Consumption is \(1 \times 50 = 50\) mAh - Remaining is \(100 - 50 = 50\) mAh

Comparison with Naive Approach

If we consider “simulating every second”, since \(T\) can be up to \(10^9\), we would need \(N \times T\) calculations, resulting in TLE.

However, since each smartphone’s remaining battery can be calculated directly, simulation is unnecessary.

Algorithm

1. For each smartphone \(i\), calculate the remaining battery at time \(T\)
2. The remaining battery is given by \(\max(0, A_i - B_i \times T)\)
3. Sum up the remaining battery of all smartphones and output

By using the \(\max\) function, negative values are replaced with \(0\).

Complexity

• Time complexity: \(O(N)\)
  • Because we perform constant-time calculations for each smartphone
• Space complexity: \(O(1)\)
  • Only a variable to hold the sum is used

Implementation Notes

1. Watch out for overflow: \(B_i \times T\) can be as large as \(10^9 \times 10^9 = 10^{18}\). In Python, there is no integer overflow so this is not a problem, but in C++ and similar languages, you need to use the long long type.

2. Using max(0, ...): To guarantee that the battery remaining does not become negative, use the max function to take the maximum with \(0\).

3. Reading input: By reading each smartphone’s information in a loop of \(N\) iterations while simultaneously calculating and adding the remaining battery, you can process efficiently in terms of memory.

   Source Code

N, T = map(int, input().split())
total = 0
for _ in range(N):
    A, B = map(int, input().split())
    remaining = max(0, A - B * T)
    total += remaining
print(total)

---

This editorial was generated by claude4.5opus.