在不遠的未來,貴老師接續了薛老師的志業,執教資訊中數導論。
資訊中數導論這學期有 \(N\) 名學生,也剛好有 \(N\) 份作業。
「我貴某人這輩子只要把資訊中數導論教好就夠了」,這樣子想的貴,正開始驗收他這學期的教學成果。
貴點開了資訊中數導論公開成績的表格,這是一個 \(N \times N\) 的表格,代表著每個學生每個作業的繳交情況。
表格中每格都是 0
或 1
:
表格中第 \(i\) 列第 \(j\) 行是 0
代表第 \(i\) 名學生有繳交第 \(j\) 份作業。
表格中第 \(i\) 列第 \(j\) 行是 1
代表第 \(i\) 名學生缺交了第 \(j\) 份作業。
貴老師認為在表格裡的一個全部都是 0
的子矩形越大越能體現出 仁
。
不過為了展現他自身的仁性,貴老師可以接受恰好一名學生的某次作業補交。
即,貴可以將表格中的某個 1
改為 0
,不過僅限一次。
現在,貴想知道在所有可能的修改方法中(或是維持原樣),最能體現出 仁
的方式是怎樣的。
即,貴想知道在所有可能的修改方法中(或是維持原樣),最大的全部都是 0
的子矩形能有多大?
請你告訴貴這個問題的答案吧!(你肯定不會讓貴失望的吧?)
第一行輸入兩個正整數 $N, M$。
接下來 $M$ 行每行輸入兩個正整數 $x, y$,代表資訊中數導論公開成績的表格中第 $x$ 列第 $y$ 行是 1
。任何沒被提到的格子的內容都是 0
。
請注意可能會有相同的 $x, y$ 限制。
輸出一個整數代表在貴修改表格後(或是維持原樣),最能體現出 仁
的全部都是 0
的子矩形的大小。
IOICamp 2021 Day3 pF
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資 | 0 |
2 | 0~10 | 無額外限制 | 100 |