문제
바닷가에 있는 정올시에는 여러 지역들 이 정방형 격자 형태로 나뉘어져 있다.
각 지역에는 한 가구만 살고 있으며 가 장 왼쪽 위에 있는 지역에는 수산시장 이 있다. (수산시장이 있는 지역에도 한 가구가 산다.)
각 지역에서 수산시장으로 이동하려면 다음의 두 가지 방법만을 이용하여 이 동한다.
1. 바로 위에 붙어있는 지역으로 이동 2. 바로 왼쪽에 붙어있는 지역으로 이동
각 지역에 사는 사람들은 매일 수산시장으로 출근하면서 지나가는 지역에서 조개를 주워 수산시장에서 판다.
(출발하는 지역과 수산물 시장이 있는 지역에서도 조개를 주울 수 있다.)
각 지역에는 자연보호를 위해 그 지역 을 지나가는 한 가구가 주울 수 있는 조개 개수의 최댓값이 있다.
(여러 가구가 지나가면 가구마다 최댓값만큼 조개를 주울 수 있을 정도로 조개는 충분하다.)
예를 들어, 격자의 크기가 3 (행) × 3 (열) 이고 지역마다 한 가구가 주울 수 있는 조개 개수의 최댓값이 다음의 왼 쪽 표와 같다고 하자.
각 지역에서 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값은 오른쪽 표와 같다.
예를 들면, 맨 오른쪽 아래 격자에서 출발해서 최대로 조개를 줍는 방법은 위쪽으로 2번 이동하고 왼쪽으로 두 번 이동하는 방법이며
총 8+6+7+2+3=26개의 조개를 주울 수 있다.
그리고 이 도시의 아홉 지역에서 수산시장에 팔 수 있는 조개 개수의 최댓값을 모두 합하면 3+5+12+7+9+18+12+15+26=107 개다.
정올시의 성실한 공무원들은 주기적으로 각 지역의 조개 숫자를 조사하여 한 가구가 주울 수 있는 조개 개수의 최댓값을 수정한다.
하지만 급격한 변화는 위험하므로 최댓값을 +1이나 -1만큼만 조정하는 것이 가능하다.
조정하지 않은 지역의 조개 개수의 최댓값은 그대로 유지된다.
예를 들면, 위의 왼쪽 표에서 격자의 1행, 2열의 2가 3으로 바뀐다면
각 지역에서 주울 수 있는 조개 개수의 최댓값과 각 지역에서 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값이 다음과 같이 바뀐다.
격자 칸마다 주울 수 있는 조개 개수의 최댓값의 초기 값이 주어지고,
격자 칸에서 주울 수 있는 조개 개수의 최댓값의 변화를 입력으로 받아,
각 지역에서 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값을 계산해서 그 합을 출력 하는 프로그램을 작성하라.
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 격자의 행(열)의 개수를 나타내는 정수 N(2≤N≤1,500)이 주어진다.
다음 N줄에는 각 격자 칸에서 주울 수 있는 조개의 개수가 제일 윗 행부터 순서대로 한 줄에 한 행씩 주어진다.
한 행의 값은 가장 왼쪽 열의 값부터 하나씩 나열된다. 주어지는 값들은 0이상 1,000이하이다.
다음 N개의 줄에는 각 줄에 변화 명령이 하나씩 주어진다. 변화 명령의 첫 글자는 U 혹은 D이다.
이어서 빈칸을 하나 두고 두 자연수가 주어지는데, 첫 번째는 행 번호, 두 번째는 열 번호이다.
첫 글자가 U인 경우 행 번호, 열 번호에 해당하는 격자 칸에서 주울 수 있는 조개의 개수가 1 증가한다.
D인 경우 해당 격자 칸에서 주울 수 있는 조개의 개수가 1 감소한다. 감소한 결과가 음수가 되는 경우는 없다.
각 변화에 대해서 아래에 지정한 값을 출력해야 한다. 주어진 각 변화 명령은 이전 변화들이 모두 적용된 결과에 적용된다.
출력
표준 출력으로, 초기에 각 격자 칸의 입력을 기준으로 모든 지역에서 팔 수 있는 조개 개수의 최댓값의 합을 출력한다.
그 다음, 각 변화 명령 에 대해 그 변화 명령을 적용한 후, 모든 지역에서 팔 수 있는 조개 개수의 최댓값의 합을 출력 한다.
전체 출력은 N+1줄임에 주의하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 12점 | N≤100 |
| #2 | 34점 | 변화는 모두 D이고 출력의 첫 줄이 20,000,000이하인 입력만 주어진다. |
| #3 | 54점 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제
3
3 2 7
4 2 6
5 3 8
U 1 2
D 3 2
U 1 2
107
111
110
114
로그인해야 코드를 작성할 수 있어요.