eolymp
bolt
Try our new interface for solving problems
Məsələlər

Defense of a Kingdom

Defense of a Kingdom

Theodore implements a new strategy game "Defense of a Kingdom". On each level player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column. The penalty of the position is a number of cells in the largest undefended rectangle. For example, the position shown on the picture has penalty \textbf{12}. \includegraphics{https://static.e-olymp.com/content/d0/d05b476b18d283929eff1165117b78c4530a80c1.jpg} Help Theodore write a program that calculates the penalty of the given position. \InputFile The first line of the input file contains three integer numbers: \textbf{w} - width of the grid, \textbf{h} - height of the grid and \textbf{n} - number of crossbow towers (\textbf{1} ≤ \textbf{w}, \textbf{h} ≤ \textbf{40000}; \textbf{0} ≤ \textbf{n} ≤ \textbf{min(w, h)}). Each of the following \textbf{n} lines of the input file contains two integer numbers \textbf{x_i} and \textbf{y_i} - the coordinates of the cell occupied by a tower (\textbf{1} ≤ \textbf{x_i} ≤ \textbf{w}; \textbf{1} ≤ \textbf{y_i} ≤ \textbf{h}). \OutputFile Output a single integer number - the number of cells in the largest rectangle that is not defended by the towers.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
15 8 3
3 8
11 2
8 6
Çıxış verilənləri #1
12
Müəllif Georgiy Korneev