Farmer John is looking at his cows in a magical field and wants to take pictures
of subsets of his cows.

The field can be seen as a \(N \times N\) grid \((1 \leq N \leq 500)\), with a
single stationary cow at each location. Farmer John's camera is capable of
taking a picture of any \(K \times K\) square that is part of the field
\((1 \leq K \leq \min(N, 25))\).

At all times, each cow has a beauty value between \(0\) and \(10^6\). The
attractiveness index of a picture is the sum of the beauty values of the cows
contained in the picture.

The beauty value for every cow starts out as \(0\), so the attractiveness index of
any picture in the beginning is \(0\).

At \(Q\) times \((1 \leq Q \leq 3\cdot 10^{4})\), the beauty of a single cow will
increase by a positive integer due to eating the magical grass that is planted
on Farmer John's field.

Farmer John wants to know the maximum attractiveness index of a picture he can
take after each of the \(Q\) updates.

Problem credits: Brian Law and Cici Liu

SCORING

• Inputs 3-6: \(N \leq 50, Q \leq 100\)
• Inputs 7-10: \(N \leq 50\)
• Inputs 11-18: No additional constraints.

Problem credits: Brian Law and Cici Liu

The first line contains integers \(N\) and \(K\).

The following line contains an integer \(Q\).

Each of the following \(Q\) lines contains three integers: \(r\), \(c\), and \(v\),
which are the row, column, and new beauty value, respectively
(\(1 \leq r, c \leq N, 1 \leq v \leq 10^6\)). It is guaranteed that the new beauty
value is greater than the beauty value at that location before.

Output \(Q\) lines, corresponding to the maximum attractiveness index of a picture
after each update.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Bronze