Overview

Given the current score for each subject and the study time required to raise it by one point, find the minimum total study time needed to bring all subjects to at least the passing score.

Analysis

For each subject, additional study is only needed if the current score \(A_i\) is below the passing score \(T\). The required score increase is \((T - A_i)\) points, and multiplying this by the unit study time \(C_i\) gives the study time needed for that subject. Since subjects already at or above the passing score require zero study time, it is sufficient to simply calculate only the failing subjects.

Algorithm

1. Read the number of subjects \(N\) and the passing score \(T\) from input
2. Read \(A_i\) and \(C_i\) for each subject
3. For each subject:
   • If \(A_i < T\): add the product of the required score increase \((T - A_i)\) and \(C_i\) to the total study time
   • If \(A_i \geq T\): add nothing (no study needed)
4. Output the total study time

Complexity

• Time complexity: \(O(N)\)
  • Because we process data for \(N\) subjects
• Space complexity: \(O(1)\)
  • Input data is processed sequentially, using almost no additional memory

Implementation Notes

• Efficient I/O is possible by reading all input data at once before processing

• During processing of each subject, we only need to check whether the score is below the passing score, leading to a simple implementation

• Since everything can be handled with integer types, be careful about type conversions

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    A = []
    C = []
    index = 2
    total_time = 0
    for i in range(n):
        a = int(data[index])
        c = int(data[index+1])
        index += 2
        if a < T:
            needed = T - a
            total_time += needed * c
    print(total_time)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.