問題一覧 > 通常問題

No.2884 Pieces on Squares

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 20
作問者 : Iroha_3856 / テスター : Rac tikuwa_ hiro1729
お気に入りにしたユーザー ProblemId : 11329 / 自分の提出
問題文最終更新日: 2024-09-08 14:51:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 445 (菁々祭プログラミングコンテスト2024) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。