시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 128 MB | 396 | 104 | 63 | 23.864% |
꽃밭에 N*N개의 꽃이 N행 N열로 심어져 있다. 이 꽃밭에는 메뚜기가 한 마리 있는데, 메뚜기는 모든 꽃의 꽃잎의 개수를 알고 있다.
메뚜기는 맨 처음에 R행 C열에 있는 꽃 위에 있고, 다음과 같은 규칙을 지키면서 최대한 많은 꽃을 방문하려고 한다.
메뚜기가 최대 몇 개의 꽃을 방문할 수 있는지 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1500)
둘째 줄에 메뚜기가 가장 처음에 있는 위치 R과 C가 주어진다. (1 ≤ R, C ≤ N)
다음 N개 줄에는 꽃잎의 수가 주어진다. 꽃잎의 수는 1,000,000보다 작거나 같다.
첫째 줄에 최대 몇 개의 꽃을 방문할 수 있는지 출력한다.
4 1 1 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7
4
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