고양이 거위와 랜덤 매트릭스
Problem
<사업부>
Cat Goose는 Nick Fury를 위해 0<의 숫자가 포함된 \(n \cdot m\) 크기의 직사각형 테이블을 준비했습니다. /span> code>에서 p−1로. Nick Fury는 이 표의 각 숫자가 0에서 p− 1 , 다른 것과 관계없이
당신의 임무 — 합계가 p로 나누어지는 이 테이블의 직사각형 부분행렬을 찾으십시오. 이러한 모든 부분행렬 중에서 요소의 합이 최대인 부분행렬을 찾아야 합니다.
공식적으로
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) 모든
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) p에 분할하고 이들 중 최대 금액이 있습니다.
<사업부>
입력
첫 번째 줄에는 세 개의 정수 n, m, p(\(1 < ;= n m, p <= 1,000,000\)) — 행렬의 차원과 부분행렬의 합을 나누어야 하는 숫자입니다.
다음 n 줄에는 m 정수, i번째 줄의 j번째 숫자가 포함됩니다. ai,j와 같음 (\(0 <= a_{i,j} <= p ? 1\) ).
a의 각 숫자는 0에서 p−1까지 동등하게 무작위로 독립적으로 선택되도록 보장됩니다.
<사업부>
출력