| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 179 | 74 | 53 | 40.458% |
모험하던 푸앙이는 정체불명의 던전에 도착했다. 던전은 $N \times N$ 정사각형 모양이다. 던전의 모든 칸엔 몬스터가 배치되어있다. $A_{ij}$는 $(i,,円j)$에 위치한 몬스터가 주는 경험치를 의미한다. 많은 몬스터를 죽여 레벨업을 위한 경험치인 $R$ 이상을 모으고 싶은 푸앙이는 던전의 시작점인 $(0,,0円)$부터 끝점인 $(N - 1,,円N - 1)$까지 $N^2$개의 칸을 모두 걸어 다닌다. 던전의 한 칸당 한 번, 푸앙이는 발도술을 사용할 수 있다. 발도술은 푸앙이로부터 $x,ドル $y$축이 증가하는 방향으로 $K \times K$정사각형 영역만큼의 범위를 가진다. 발도술을 사용하면, 던전 내부와 발도술 영역에 있는 몬스터 중 1ドル$마리를 사냥하여 경험치를 얻을 수 있다. 던전의 특수성으로, 사냥 당한 몬스터는 즉시 리스폰된다. 푸앙이는 되도록 적은 힘으로 발도술을 사용하면서 레벨업을 하고 싶다. 푸앙이가 레벨업을 할 수 있는 발도술 영역 $K$의 최솟값을 출력하시오.
다음은 $K = 3$ 일 때 푸앙이가 $(1,,1円)$ 지점에서 시전한 발도술 영역이다.
첫 번째 줄에 $N$ $(3 \leq N \leq 1,000円),ドル 정수 $R$ $(1 \leq R \leq 10^{12})$이 공백으로 구분되어 주어진다.
둘째 줄부터 $N$개의 줄에는 던전 정보가 주어진다. 던전 정보는 공백을 사이로 두고 던전 각 칸에 위치한 몬스터가 주는 경험치가 정숫값으로 주어진다. $(0 \leq A_{ij} \leq 10,000円,000円)$
푸앙이가 레벨업을 할 수 있는 발도술 영역 $K$의 최솟값을 출력하시오. 만약 푸앙이가 레벨업 하는 것이 불가능하다면 $-1$을 출력하시오.
5 124 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
5
5 120 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
4
5 300 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
-1
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2022 중앙대학교 프로그래밍 경진대회 (CPC) > Division 1 G번