레이팅 미적용농부 존(Farmer John)의 농장은 N x N 정사각형 격자의 목초지로 나뉘어 있다 (2 <= N <= 15). 지금은 농장 바깥에 울타리가 둘러져 있지만, 소들은 목초지 사이를 자유롭게 오갈 수 있다.
농부 존은 소들을 서로 떼어 놓기 위해 울타리를 치기로 했다. 구역 규제 때문에, 각 울타리는 농장 전체를 가로지르는 수평선 또는 수직선이어야 하고, 울타리가 목초지를 관통할 수는 없다. 농부 존은 최대 K개 (1 <= K <= 2N - 2)의 울타리를 칠 돈밖에 없다.
농부 존은 울타리를 쳐서 결과적으로 생기는 가장 큰 소 그룹의 크기를 최소화하고 싶어 한다 (두 소가 울타리를 지나지 않고 서로에게 도달할 수 있으면 같은 그룹이다). 각 목초지의 현재 소의 수가 주어질 때, 울타리를 최적으로 쳤을 때 가장 큰 소 그룹의 크기를 계산하는 것을 농부 존에게 도와주자.
첫째 줄: 두 정수 N과 K.
둘째 줄부터 1+N번째 줄까지: 각 줄에 농장의 한 행에 대해 각 목초지의 소의 수를 나타내는 N개의 수가 주어진다 (각 목초지의 소는 0마리 이상 1000마리 이하이다).
가장 큰 소 그룹의 가능한 최소 크기.
partition.in · 출력을 쓸 파일 partition.out3 2
1 1 2
1 1 2
2 2 44Output details: Build fences between columns 2 and 3 and between rows 2 and 3, creating 4 groups each with 4 cows.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Gold