레이팅 미적용설명
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 \(N \times M\) 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (\(N\), \(M\))으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
제약
입력 형식
첫째 줄에 \(N\), \(M(1 \le N,\) \(M \le 1{,}000)\)이 주어진다. 다음 \(N\)개의 줄에는 \(M\)개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.
출력 형식
첫째 줄에 최대 가치의 합을 출력한다.
예제 1
입력
5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15
출력
319
문제 정보
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2002 > 2차 대회 > 고등부 1번