2092: [USACO 2026 First Contest, Bronze] Problem 3. Photoshoot
文件提交：无需freopen
内存限制：256 MB
时间限制：2.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
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×N grid (1 <= N <= 500), with a single stationary cow at each location.
Farmer John's camera is capable of taking a picture of any K×K square that is part of the field (1 <= K <= 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 <= Q <= 3 * 104), 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.
The field can be seen as a N×N grid (1 <= N <= 500), with a single stationary cow at each location.
Farmer John's camera is capable of taking a picture of any K×K square that is part of the field (1 <= K <= 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 <= Q <= 3 * 104), 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.
输入
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 <= r, c <= N, 1 <= v <= 106).
It is guaranteed that the new beauty value is greater than the beauty value at that location before.
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 <= r, c <= N, 1 <= v <= 106).
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.
样例输入
4 2
3
2 2 11
3 4 3
3 1 100样例输出
11
11
111提示
After the first update, a picture with the maximum attractiveness index is the picture with upper left corner and lower right corner , which has an attractiveness index of .
The second update does not affect the maximum attractiveness index.
After the third update, the picture with the maximum attractiveness index changes to the picture with upper left corner and lower right corner , which has an attractiveness index of .
SAMPLE INPUT:
3 1
32 2 3
2 2 5
2 2 7
SAMPLE OUTPUT:
3
5
7
There is only one cow with a positive beauty value, so the maximum attractiveness index will always include that cow.
SCORING:
Inputs 3-6: N <= 50, Q <= 100
Inputs 7-10: N <= 50
Inputs 11-18: No additional constraints.