Overview

A problem where you calculate the difference between the amount each person paid upfront and the amount they should actually bear.

Analysis

In this problem, for each payment, we record “who paid how much upfront” and “who should bear how much,” then finally compute the difference \(D_j\) for each person.

A straightforward approach would be to add the share amount to all users for each payment. However, this is sufficiently fast. The key points are reading the input quickly and performing the calculations efficiently.

For each payment, there is one person who pays upfront and multiple users, so we add the paid amount to that person and add the share (\(C_i / K_i\)) to each user. By the constraints, \(\frac{C_i}{K_i}\) is always an integer.

Simply performing this process naively is fast enough. However, if input parsing is slow, it may result in TLE, so we use a fast input method.

Algorithm

1. Prepare arrays to record “amount actually paid upfront” and “amount that should be borne” for each person.
2. For each payment, do the following:
   • Add \(C_i\) to the “amount actually paid upfront” for the person \(P_i\) who paid.
   • Add \(\frac{C_i}{K_i}\) to the “amount that should be borne” for each user \(B_{i,j}\).
3. Finally, compute and output “amount paid upfront − amount that should be borne” for each person.

Complexity

• Time complexity: \(O(M + \sum K_i)\)
• Space complexity: \(O(N + \sum K_i)\)

※ Since \(\sum K_i \leq 10^5\), this is sufficiently fast.

Implementation Notes

• Since fast input is necessary, it is recommended to read everything at once using sys.stdin.read.

• Since the indices for actual_paid and should_pay are handled as 1-indexed, the array size should be \(N+1\).

• Since the share for each payment is guaranteed to be an integer, it can be computed directly using division.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    # D[j] = 実際に立て替えた金額 - 本来負担すべき金額
    actual_paid = [0] * (N + 1)
    should_pay = [0] * (N + 1)
    
    for _ in range(M):
        P = int(data[idx])
        idx += 1
        C = int(data[idx])
        idx += 1
        K = int(data[idx])
        idx += 1
        burden = C // K
        actual_paid[P] += C
        for __ in range(K):
            b = int(data[idx])
            idx += 1
            should_pay[b] += burden
            
    for j in range(1, N + 1):
        D = actual_paid[j] - should_pay[j]
        print(D)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.