시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 659 | 235 | 189 | 34.239% |
태균이는 분필과 바닥만 있으면 언제든지 할 수 있는 재미있는 게임을 하나 만들었습니다.
바닥에 N×M 사각 격자를 그린 뒤 각 칸에 정수들을 쓰고 다음의 규칙을 따라 게임을 진행합니다.
칸에 적힌 수들이 주어지면 게임에서 낼 수 있는 최대 점수를 구해주세요.
첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다.
i+1 번째 줄에는 i (1 ≤ i ≤ N) 번째 행에 있는 쓰여있는 정수 ai,1, ai,2, ..., ai,m (-100 ≤ ai,j ≤ 100) 이 순서대로 주어집니다.
첫 번째 줄에 게임에서 낼 수 있는 최대 점수를 출력합니다.
4 3 2 3 -5 4 2 0 0 1 -3 1 -2 9 1
21
1행 2열에서 시작하여 3행 2열로 이동하면 (-5) × (-3) = 15 점을 얻을 수 있습니다.
3행 2열에서 4행 1열로 이동하면 (-3) × (-2) = 6 점을 얻을 수 있습니다.
총 15 + 6 = 21 점을 획득했고 이보다 더 좋은 방법은 없으므로 문제의 정답이 됩니다.
2 2 2 100 100 -100 -100
-10000
6 6 3 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0
4
University > 경북대학교 > 2019 Goricon C번