레이팅 미적용농부 존(Farmer John)은 마법의 들판에 있는 자신의 소들을 바라보며, 소들의 부분집합을 사진으로 찍고 싶어 한다.
들판은 \(N \times N\) 격자 \((1 \leq N \leq 500)\)로 볼 수 있으며, 각 칸에는 움직이지 않는 소가 한 마리씩 있다. 농부 존의 카메라는 들판의 일부인 임의의 \(K \times K\) 정사각형 영역을 사진으로 찍을 수 있다 \((1 \leq K \leq \min(N, 25))\).
항상 각 소는 \(0\) 이상 \(10^6\) 이하의 아름다움 값을 가진다. 사진의 매력 지수는 사진에 포함된 소들의 아름다움 값의 합이다.
모든 소의 아름다움 값은 \(0\)에서 시작하므로, 처음에는 어떤 사진의 매력 지수도 \(0\)이다.
\(Q\)번 \((1 \leq Q \leq 3\cdot 10^{4})\)에 걸쳐, 농부 존의 들판에 심어진 마법의 풀을 먹은 소 한 마리의 아름다움이 양의 정수만큼 증가한다.
농부 존은 \(Q\)번의 갱신이 있을 때마다, 그 시점에 찍을 수 있는 사진의 최대 매력 지수를 알고 싶어 한다.
문제 제공: Brian Law and Cici Liu
배점
- 입력 3-6: \(N \leq 50, Q \leq 100\)
- 입력 7-10: \(N \leq 50\)
- 입력 11-18: 추가 제약이 없다.
문제 제공: Brian Law and Cici Liu
첫째 줄에 정수 \(N\)과 \(K\)가 주어진다.
다음 줄에 정수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에는 각각 세 정수 \(r\), \(c\), \(v\)가 주어지며, 각각 행, 열, 새로운 아름다움 값을 나타낸다 (\(1 \leq r, c \leq N, 1 \leq v \leq 10^6\)). 새로운 아름다움 값은 그 위치의 이전 아름다움 값보다 큼이 보장된다.
\(Q\)개의 줄을 출력하며, 각 줄은 각 갱신 후 찍을 수 있는 사진의 최대 매력 지수를 나타낸다.
4 2
3
2 2 11
3 4 3
3 1 10011
11
111After the first update, a picture with the maximum attractiveness index is the
picture with upper left corner \((2, 2)\) and lower right corner \((3, 3)\), which
has an attractiveness index of \(11 + 0 + 0 + 0 = 11\).
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 \((2, 1)\) and lower right corner
\((3, 2)\), which has an attractiveness index of \(0 + 11 + 100 + 0 = 111\).
3 1
3
2 2 3
2 2 5
2 2 73
5
7There is only one cow with a positive beauty value, so the maximum
attractiveness index will always include that cow.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Bronze