레이팅 미적용설명
무더운 여름날, 소 베시는 몹시 게으름을 피우고 싶다. 베시는 짧은 거리만 이동해도 최대한 많은 맛있는 풀에 닿을 수 있는 위치에 자리 잡으려고 한다.
베시가 사는 들판은 N x N 격자의 정사각형 칸(1 <= N <= 400)으로 표현된다. r행 c열의 칸(1 <= r,c <= N)에는 G(r,c) 단위의 풀(0 <= G(r,c) <= 1000)이 있다. 베시는 격자에서 처음 자리 잡은 칸으로부터 최대 K걸음(0 <= K <= 2*N)까지만 움직일 의향이 있다. 한 걸음마다 현재 위치의 바로 북, 남, 동, 서에 있는 칸으로 이동한다.
베시가 격자에서 가능한 최선의 초기 위치를 고른다면 닿을 수 있는 풀의 최대량을 구하는 것을 도와라.
제약
입력 형식
첫째 줄: 정수 N과 K가 주어진다.
둘째 줄부터 1+N째 줄까지: r+1째 줄에는 격자의 r행을 나타내는 N개의 정수가 주어진다.
출력 형식
베시가 가능한 최선의 초기 위치(가장 많은 풀에 닿을 수 있는 위치)를 고를 때 닿을 수 있는 풀의 최대량을 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
lazy.in · 출력을 쓸 파일 lazy.out예제 1
입력
5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9출력
342설명
Output details: Bessie can reach 342 total units of grass if she locates herself in the middle of the grid.
문제 정보
태그