Compute Remaining GPUs With Switching Limits

You operate n GPU clusters, and cluster i can serve at most cap[i] GPUs on any single day. Every morning each cluster is fully available again, because all GPUs lent out the previous day come back overnight. You are handed a log of usage entries, each one a triple (day, cluster, used) meaning that on day, cluster cluster handed out used GPUs. The log may arrive in arbitrary order, and it may hold several entries for the same cluster on the same day — those amounts simply add together. The log is guaranteed to be consistent: for any day and any cluster, the summed used values never exceed that cluster's capacity. Days are numbered starting at 0, and every entry refers to a day inside the requested range.

Part 1. For each day 0, 1, ..., num_days - 1, in that order, report how many GPUs are still free in every cluster at the close of that day. Return a 2D array in which row d lists the leftover amount of each cluster (in cluster-index order) for day d.

Part 2. One new workload runs once per day and occupies exactly one cluster on that day. It may pick a different cluster on any day, with no limit on how often it changes. Whatever is still free in the cluster it picks — after the logged usage of that day is removed — is what the workload gets. Compute the largest total number of GPUs this workload can obtain over the full horizon.

Part 3. The same workload, except that it may change clusters at most k times in total. Changing is counted only when the cluster used on some day differs from the cluster used on the immediately following day; repeating the same cluster counts as no change. Compute the maximum total GPUs the workload can obtain across all days. When k is 0, the workload is locked to a single cluster for the whole horizon.

Example 1 (Part 1):

Input: cap = [9, 5, 12], num_days = 3, usages = [(1, 2, 1), (0, 0, 4), (0, 1, 2), (2, 0, 2), (0, 0, 3), (1, 1, 5)]

Output: [[2, 3, 12], [9, 0, 11], [7, 5, 12]]

Explanation: On day 0 the two entries for cluster 0 combine to 7, leaving 2; cluster 1 leaves 3 and cluster 2 is untouched at 12. Day 1 spends 5 from cluster 1 and 1 from cluster 2, and day 2 spends 2 from cluster 0.

cap = [9, 5, 12]
num_days = 3
usages = [[1, 2, 1], [0, 0, 4], [0, 1, 2], [2, 0, 2], [0, 0, 3], [1, 1, 5]]

[[2, 3, 12], [9, 0, 11], [7, 5, 12]]

Example 2 (Part 1):

Input: cap = [6, 4], num_days = 2, usages = []

Output: [[6, 4], [6, 4]]

Explanation: With nothing logged, both days close with every cluster at its full capacity.

Example 3 (Part 2):

Input: cap = [9, 5, 12], num_days = 3, usages = [(1, 2, 1), (0, 0, 4), (0, 1, 2), (2, 0, 2), (0, 0, 3), (1, 1, 5)]

Output: 35

Explanation: The closing remainders are [2, 3, 12], [9, 0, 11], [7, 5, 12]; taking the largest value of each day gives $12 + 11 + 12 = 35$.

Example 4 (Part 2):

Input: cap = [8, 3], num_days = 3, usages = []

Output: 24

Explanation: Every day the workload takes the 8 GPUs of cluster 0, for $8 \times 3 = 24$.

Example 5 (Part 3):

Input: cap = [10, 5], num_days = 4, usages = [(1, 0, 8), (3, 0, 8)], k = 1

Output: 27

Explanation: The daily remainders are [10, 5], [2, 5], [10, 5], [2, 5]. Stay on cluster 0 for the first three days and move to cluster 1 only on the last day: $10 + 2 + 10 + 5 = 27$.

Example 6 (Part 3):

Input: cap = [10, 5], num_days = 4, usages = [(1, 0, 8), (3, 0, 8)], k = 3

Output: 30

Explanation: Alternating each day uses three changes, the whole allowance, and collects $10 + 5 + 10 + 5 = 30$.

Constraints:

Part 1 and Part 2:

• $0 \le \text{num\_days} \le 9000$
• $0 \le \text{len(cap)} \le 150$
• $0 \le \text{len(usages)} \le 150000$
• Every used value is non-negative.
• For every day and cluster, the summed used values stay within that cluster's capacity.

Part 3:

• $0 \le \text{num\_days} \le 400$
• $0 \le \text{len(cap)} \le 80$
• $0 \le \text{len(usages)} \le 150000$
• $k \ge 0$
• Every used value is non-negative.
• For every day and cluster, the summed used values stay within that cluster's capacity.