Harvesting the Farm

모든 작물의 행과 열에서 최솟값과 최댓값을 각각 $y_{\min},y_{\max},x_{\min},x_{\max}$라 하자.

기계는 처음에 $S_r$행만 차지한다. $y_{\min}$행과 $y_{\max}$행의 작물을 모두 수확하려면 세로 구간에 $S_r$, $y_{\min}$, $y_{\max}$가 모두 포함되어야 한다. 따라서 확장은 최소 $\max(S_r,y_{\max})-\min(S_r,y_{\min})$번 필요하다.

가로로는 $x_{\min}$열과 $x_{\max}$열을 모두 방문해야 한다. 둘 중 한 끝을 먼저 방문한 뒤 다른 끝으로 가는 두 순서 가운데 짧은 것을 택하면 된다. 최소 이동 횟수는

$$(x_{\max}-x_{\min})+\min(|S_c-x_{\min}|,|S_c-x_{\max}|)$$

이다.

먼저 시작 열에서 필요한 모든 행까지 기계를 확장한다. 이어서 가까운 끝 열로 이동하고 다른 끝 열까지 이동한다. 이 과정에서 모든 작물의 행과 열을 지나므로 모든 작물을 수확한다. 따라서 두 하한을 동시에 달성할 수 있고, 정답은 두 값의 합이다.

서브태스크 1에서는 모든 작물이 시작 열에 있으므로 세로 확장만 고려한다. 서브태스크 2에서는 모든 작물이 시작 행에 있으므로 가로 이동만 고려한다. 서브태스크 3에서는 모든 작물이 시작 열 또는 그 오른쪽에 있으므로 가로 이동 횟수가 $x_{\max}-S_c$이다. 전체 서브태스크에서는 일반식을 사용한다.

각 케이스의 시간 복잡도는 $O(N)$, 추가 공간 복잡도는 $O(1)$이다. 전체 시간 복잡도는 $O(T+\sum N)$이다.

Solution written by GPT5