표지판 따라가기

참고: 이 문제의 시간 제한은 8초로, 기본값의 네 배이다.

농부 존에게는 \((N+1)\times (N+1)\) (\(1\le N\le 1500\)) 격자 칸으로 나뉜 큰 정사각형 밭이 있다. 칸 \((i, j)\)는 위에서 \(i\)번째 행, 왼쪽에서 \(j\)번째 열의 칸을 뜻한다. \(1 \le i, j \le N\)인 모든 칸 \((i, j)\)에는 소가 한 마리씩 살고 있으며, 이러한 각 칸에는 오른쪽 또는 아래쪽을 가리키는 표지판도 있다. 또한 \((N+1, N+1)\)을 제외하고, \(i=N+1\)이거나 \(j=N+1\)인 모든 칸 \((i, j)\)에는 소 사료 통이 있다. 각 통의 사료 가격은 다양한데, \((i, j)\)에 있는 통은 소 한 마리를 먹이는 데 \(c_{i, j}\) (\(1 \le c_{i,j} \le 500\))가 든다.

매일 저녁 식사 시간에 농부 존이 저녁 종을 울리면, 각 소는 표지판의 방향을 계속 따라가다가 사료 통에 도착하고, 그 통에서 사료를 먹는다. 그 후 소들은 모두 다음 날을 위해 원래 위치로 돌아간다.

예산을 관리하기 위해 농부 존은 매일 모든 소를 먹이는 데 드는 총비용을 알고 싶어 한다. 그런데 매일 저녁 식사 전에 어떤 칸 \((i, j)\)의 소가 자기 표지판의 방향을 뒤집는다 (오른쪽에서 아래쪽으로, 또는 그 반대로). 표지판은 나중에 다시 뒤집히지 않는 한 다음 날들에도 그 방향을 유지한다.

매일 뒤집히는 표지판의 좌표가 주어질 때, 매일의 비용을 출력하여라 (총 \(Q\)일, \(1 \le Q \le 1500\)).

Problem credits: Benjamin Qi

채점 방식

• 입력 2-4: \(1 \le N, Q \le 50\)
• 입력 5-7: \(1 \le N, Q \le 250\)
• 입력 2-10: 각 칸의 초기 방향과 쿼리는 균등하게 무작위로 생성된다.
• 입력 11-15: 추가 제약이 없다.

Problem credits: Benjamin Qi

첫째 줄에 \(N\) (\(1 \le N \le 1500\))이 주어진다.

다음 \(N+1\)개의 줄에 격자의 행이 위에서 아래 순서로 주어지며, 표지판의 초기 방향과 각 통의 비용 \(c_{i, j}\)를 담고 있다. 이 중 처음 \(N\)개의 줄에는 R 또는 D로 이루어진 길이 \(N\)의 방향 문자열(각각 오른쪽, 아래쪽을 가리키는 표지판)과 그 뒤에 비용 \(c_{i, N+1}\)이 주어진다. \((N+1)\)번째 줄에는 \(N\)개의 비용 \(c_{N+1, j}\)가 주어진다.

다음 줄에 \(Q\) (\(1 \le Q \le 1500\))가 주어진다.

그 다음 \(Q\)개의 줄이 추가로 주어지며, 각 줄에는 해당 날에 표지판이 뒤집히는 칸의 좌표인 두 정수 \(i\)와 \(j\) (\(1 \le i, j \le N\))가 주어진다.

\(Q+1\)개의 줄에 걸쳐, 총비용의 처음 값과 각 뒤집기 이후의 총비용을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > January > Silver