% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
	\renewcommand{\tl}{$0.6$ сек.}
	\renewcommand{\ml}{$1024$ MB}
	\problem{Задача А3. МАТРИЦА}
	\addauthor{Автор: Иван Лупов, Атанас Димитров, Борис Михов}{2025}{12}{20}
	\renewcommand{\header}{
		XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
		Общински кръг, 20 декември 2025 г.\\
		Група A – 11, 12 клас
	}

	Дадена е матрица (таблица) \(A\) с \(N\) реда и \(M\) колони, съдържаща единствено числата \(0\) и \(1\). Редовете и колоните на \(A\) са номерирани, започвайки от \(0\), и стойността на клетката в \(i\)-тия ред и \(j\)-тата колона е \(A_{i,j}\).
	От нея е образувана по-голяма матрица \(B\) чрез долепяне, като матрицата \(A\) се повтаря в \(N \cdot R\) реда и \(M \cdot C\) колони. Формално, \(B_{i,j} = A_{(i \bmod N),(j \bmod M)}\) за \(0 \le i < N \cdot R,\; 0 \le j < M \cdot C\), при следване на аналогичните на горните означения.

	Ще наричаме \textbf{правоъгълник} в $B$ такова множество от клетки, което може да се опише чрез избор на два индекса
	\(r_1\) и \(r_2\) с \(0 \le r_1 \le r_2 < N\cdot R\) и два индекса \(c_1\) и \(c_2\) с \(0 \le c_1 \le c_2 < M\cdot C\),
	така че правоъгълникът съдържа всички клетки, чиито редове са между \(r_1\) и \(r_2\) и чиито колони са между \(c_1\) и \(c_2\).
	Напишете програма \textbf{\texttt{matrix}}, която намира максималната площ (брой клетки) на правоъгълник в \(B\), съставен единствено от клетки със стойност $1$.

	\subsection{Вход}
	На първия ред са дадени четири цели числа \(N, M, R, C\).
	На следващите \(N\) реда е дадена матрицата \(A\) -- по \(M\) символа `0' или `1' на ред.

	\subsection{Изход}
	На стандартния изход изведете едно цяло число -- търсената максимална площ.

	\subsection{Ограничения}
	\begin{itemize}
		\item $1 \leq N, M \leq 2000$
		\item $1 \leq R, C \leq 10^6$
	\end{itemize}

	\subsection{Подзадачи}

	\begin{table}[H]
		\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
			\hline
			\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N, M$ & \textbf{Други ограничения} \\
			\hline
			$0$ & $0$ & $-$ & $-$ & Примерът. \\
			\hline
			$1$ & $10$ & $-$ & $N = 1$ & $R = C = 1$ \\
			\hline
			$2$ & $5$ & $1$ & $N = 1$ & $R = 1$ \\
			\hline
			$3$ & $5$ & $1$ & $N = 1$ & $C = 1$ \\
			\hline
			$4$ & $10$ & $-$ & $N, M \leq 20$ & $R = C = 1$ \\
			\hline
			$5$ & $15$ & $4$ & $N, M \leq 60$ & $R = C = 1$ \\
			\hline
			$6$ & $15$ & $4-5$ & $N, M \leq 300$ & $R = C = 1$ \\
			\hline
			$7$ & $10$ & $1, 4-6$ & $N, M \leq 2000$ & $R = C = 1$ \\
			\hline
			$8$ & $30$ & $0-7$ & $N, M \leq 2000$ & -- \\
			\hline
		\end{tblr}
		\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
	\end{table}

	\pagebreak
	\subsection{Пример}

	\begin{table}[H]
		\begin{tblr}{|l|l|X[j]|}
			\hline
			\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
			\hline
			\texttt{\makecell[lt]{3 4 2 3\\
				0110\\
				1111\\
				0101}} &
			\texttt{12} &
			{Матрицата $B$ има \(N\cdot R=6\) реда и \(M\cdot C=12\) колони и изглежда по следния начин:\\
			\texttt{011001100110\\
				\textbf{111111111111}\\
				010101010101\\
				011001100110\\
				111111111111\\
				010101010101} \\
			Един от правоъгълниците с максимална площ е с удебелен шрифт.} \\
			\hline
		\end{tblr}
	\end{table}

\end{document}
