Overview

This is a problem where, given information about multiple payments made during a trip, you need to calculate the amount each person should ultimately receive or pay.

Analysis

For each payment, we need to manage the following two pieces of information: 1. The amount actually paid by the person who covered the expense (\(P_i\) paid \(C_i\) yen) 2. The amount each user should originally bear (\(\frac{C_i}{K_i}\) yen)

In a straightforward approach, processing all users for each payment is sufficiently efficient since the total sum of the number of users \(K_i\) across all \(M\) payments is at most \(10^5\).

Algorithm

1. Prepare an array initializing the settlement amount \(D_j\) to 0 for each person \(j\)
2. For each payment:
   • Add \(C_i\) to the \(D\) value of the person \(P_i\) who covered the expense (for the amount they advanced)
   • Subtract \(\frac{C_i}{K_i}\) from the \(D\) value of all users of that payment (for the amount they should bear)
3. After processing all payments, output \(D_j\) for each person

If \(D_j\) is positive, it means that person should receive \(D_j\) yen; if negative, it means they should pay \(|D_j|\) yen.

Complexity

• Time complexity: \(O(\sum_{i=1}^{M} K_i)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Efficiency is improved by reading input data all at once

• Process the list of users for each payment sequentially

• Use integer division (the problem guarantees that \(\frac{C_i}{K_i}\) is an integer)

• Since person numbers are 1-indexed, allocate the array with size \(n+1\)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    index = 2
    
    D = [0] * (n + 1)
    
    for _ in range(m):
        P = int(data[index]); index += 1
        C = int(data[index]); index += 1
        K = int(data[index]); index += 1
        per_person = C // K
        
        for i in range(K):
            person = int(data[index]); index += 1
            D[person] -= per_person
        
        D[P] += C
    
    for j in range(1, n + 1):
        print(D[j])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.