Overview

For each warehouse’s inventory, we apply multiple “outgoing amounts” and “incoming amounts” all at once, then find the warehouse number with the maximum final inventory (smallest number in case of ties).

Analysis

Since delivery instructions are applied “all at once” rather than sequentially, the order doesn’t matter. The final inventory of warehouse \(i\) is computed by combining:

• Initial inventory \(P_i\)
• Total incoming amount (from other warehouses to \(i\))
• Total outgoing amount (from \(i\) to other warehouses)

This gives us: \(P_i + (\text{total incoming}) - (\text{total outgoing})\)

Naively “updating all warehouse states for each instruction” requires \(M\) updates, which appears to be \(O(M)\), but the key insight is that it’s sufficient to simply “aggregate all inflows and outflows, then compute the final values.” Even when there are many instructions for the same warehouse, we can accumulate the net change for each warehouse and compute the final inventory just once at the end.

The effective technique here is using a “difference (delta) array.” For each warehouse \(i\), we prepare a delta value \(\Delta_i\):

• If moving \(w\) from \(u \to v\): warehouse \(u\) decreases by \(w\), so \(\Delta_u -= w\)
• Warehouse \(v\) increases by \(w\), so \(\Delta_v += w\)

We accumulate these changes. Finally, we look at \(P_i + \Delta_i\) for each warehouse and find the maximum.

(Example) \(P=[10,5,7]\), instructions: “\(1\to2\) move \(3\)” and “\(3\to2\) move \(2\)” \(\Delta=[-3, +5, -2]\), so the final values are \([7,10,5]\), and the maximum is warehouse 2.

Algorithm

1. Initialize an array delta of length \(N\) with \(0\) (net change for each warehouse).
2. For each delivery instruction \((U, V, W)\):
   • delta[U] -= W
   • delta[V] += W (adjust indices to 0-index).
3. Compute the final inventory P[i] + delta[i] for each warehouse \(i\) and track the maximum value.
4. When multiple warehouses share the maximum inventory, we need the smallest number. By iterating from left to right and updating only when >, the smallest number is naturally retained.
5. Convert back to 1-index and output.

Complexity

• Time complexity: \(O(N + M)\) (aggregating \(M\) delivery instructions + finding the maximum over \(N\) warehouses)
• Space complexity: \(O(N)\) (the delta array delta)

Implementation Notes

• Since delta amounts and final inventories can involve many additions and subtractions of values up to \(10^9\), 64-bit integers may be required depending on the language (Python handles this automatically with arbitrary precision integers).

• Since the input size can be large, using sys.stdin.buffer.readline in Python improves speed.

• To select the smallest number in case of ties, use > instead of >= in comparisons to retain the “first maximum found.”

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    delta = [0] * N

    for _ in range(M):
        u, v, w = map(int, input().split())
        u -= 1
        v -= 1
        delta[u] -= w
        delta[v] += w

    max_val = -10**30
    ans = 0
    for i in range(N):
        val = P[i] + delta[i]
        if val > max_val:
            max_val = val
            ans = i

    print(ans + 1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.