No.2884 Pieces on Squares
タグ : / 解いたユーザー数 20
作問者 :
Iroha_3856
/ テスター :
Problem Statement
There is a grid with $H$ rows and $W$ columns.
$N$ pieces are placed on this grid, and the $i$-th piece is placed at row $A_i$, column $B_i$.
Initially, all $HW$ squares are white.
You perform the following two operations in order.
- Choose some of the $H$ rows (you may choose $0$ or $H$ of them) and flip the colors of all squares contained in those rows.
- Choose some of the $W$ columns (you may choose $0$ or $W$ of them) and flip the colors of all squares contained in those columns.
Here, to flip the color of a square means to change a white square to black and a black square to white.
Consider choosing appropriate rows and columns in the operations so that all pieces are placed on white squares.
Find the maximum possible number of black squares on the grid in this case.
It can be proved that, under the constraints, it is possible to reach a state in which all pieces are placed on white squares.
Input
$H\ W\ N$ $A_1\ B_1$ $A_2\ B_2$ $\vdots$ $A_N\ B_N$
All inputs satisfy the following constraints.
- $1 \leq H, W \leq 5000$
- $1 \leq N \leq \min(HW, 2 \times 10^5)$
- $1 \leq A_i \leq H$
- $1 \leq B_i \leq W$
- If $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$
- All inputs are integers
Output
Output the answer, followed by a newline.
Sample
Sample 1
Input
3 3 3 1 2 3 2 2 3
Output
5
Representing squares without a piece as - and squares with a piece as @, the grid looks as follows.
-@- --@ -@-
If you choose rows $1, 3$ and column $2$, the grid looks as follows, representing white squares as . and black squares as #.
#.# .#. #.#
In this case, all pieces are on white squares, and the number of black squares on the grid is $5$.
The number of black squares on the grid cannot be made greater than $5$, so output $5$.
Sample 2
Input
2 2 3 1 1 1 2 2 1
Output
0
Representing squares without a piece as - and squares with a piece as @, the grid looks as follows.
@@ @-
If you choose rows $1, 2$ and columns $1, 2$, the grid looks as follows, representing white squares as . and black squares as #.
.. ..
In this case, all pieces are on white squares, and the number of black squares on the grid is $0$.
The number of black squares on the grid cannot be made greater than $0$, so output $0$.
Sample 3
Input
5 5 9 4 1 2 2 2 3 3 1 4 3 4 4 3 4 3 3 5 2
Output
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。