레이팅 미적용설명
메뚜기 한 마리가 꽃밭에 있다. 꽃밭에는 \(N\)행 \(N\)열로 배열된 \(N \cdot N\)송이의 꽃이 있다. 밭의 각 꽃에 대해 꽃잎이 몇 장인지 알고 있다.
메뚜기는 처음에 행 \(R\), 열 \(C\)의 꽃 위에 있다. 목표는 다음 규칙을 지키면서 최대한 많은 꽃을 방문하는 것이다:
- 인접한 행이나 열로만 뛸 수 있다. 인접한 행으로 뛰면 열은 적어도 두 칸 이동해야 하고, 인접한 열로 뛰면 행은 적어도 두 칸 이동해야 한다. 다시 말해, 꽃 \((r_1, c_1)\)에서 꽃 \((r_2, c_2)\)로 뛸 수 있는 조건은:
- \(|r_1 - r_2| = 1\)이고 \(|c_1 - c_2| > 1\), 또는
- \(|c_1 - c_2| = 1\)이고 \(|r_1 - r_2| > 1\)
- 다음 꽃의 꽃잎 수는 이전 꽃의 꽃잎 수보다 순증가해야(순수하게 더 커야) 한다.
메뚜기가 방문할 수 있는 꽃의 최대 개수를 계산하는 프로그램을 작성하시오.
제약
입력 형식
첫째 줄에 꽃밭의 크기인 정수 \(N\) (\(1 \le N \le 1500\))이 주어진다.
둘째 줄에 메뚜기의 초기 위치인 정수 \(R\) (\(1 \le R \le N\))와 \(C\) (\(1 \le C \le N\))가 주어진다.
다음 \(N\)개의 줄에는 공백으로 구분된, 각각 \(1\,000\,000\)보다 작은 양의 정수 \(N\)개가 주어진다. 꽃들의 꽃잎 수이다.
출력 형식
정수 하나, 즉 메뚜기가 방문할 수 있는 꽃의 최대 개수를 출력한다.
채점: 전체 점수의 \(50\%\)에 해당하는 테스트 데이터에서는 \(N\)이 최대 \(100\)이다. 전체 점수의 \(80\%\)에 해당하는 테스트 데이터에서는 \(N\)이 최대 \(1000\)이다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 60점 | \(N \le 100\) |
Subtask 2 | 36점 | \(N \le 1000\) |
Subtask 3 | 24점 | No additional constraints (\(N \le 1500\)). |
예제 1
입력
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7출력
4예제 2
입력
5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13출력
21문제 정보
태그