With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one.
To mazimize the effect her magic, she can pick one diagonal whose
i - j = l (-n <= l <= n) in one action. When two
diagonals have differnt i - j, then they cannot be modified
in the same operation.
Therefore, we can iterate over the diagonals and sum up the minimum value for each diagonal.
from collections import defaultdict
for _ in range(int(input())):
n: int = int(input())
a: list[list[int]] = []
for _ in range(n):
a.append(list(map(int, input().split())))
min_in_diagonal = defaultdict(int)
for row_i in range(n):
for col_i in range(n):
diff: int = row_i - col_i
min_in_diagonal[diff] = min(min_in_diagonal[diff], a[row_i][col_i])
print(-sum(min_in_diagonal.values()))Fruits 400 Pork 400 Pasta 500 Mashed potatoes 150 Protein shake 300
Total 1750 kcal
MUST:
TODO: