QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 4137. 棋盘覆盖

Statistics

在一个 $N \times M$ 个方格组成的棋盘内,有 $K$ 个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘,保证特殊方格不能被覆盖,非特殊方格只能被一个俄罗斯方块覆盖,求最多能容纳的俄罗斯方块的数量。

已知有以下三组俄罗斯方块,一个棋盘可能用其中的某一组。

输入格式

第一行三个整数,$N,M,K$,和一个字符,$type$,为所用的俄罗斯方块组。

接下来 $K$ 行每行两个整数,$X,Y$,表示第 $X$ 行第 $Y$ 列为特殊方格。

输出格式

一个整数,为所求的答案。

样例数据

样例 1 输入

8 8 0 A

样例 1 输出

32

样例 2 输入

7 6 6 C
3 1
3 6
5 3
5 4
5 7
6 7

样例 2 输出

12

子任务

测试点 $N, M$ $K$ $type$
$1 \sim 6$ $0 < N,M \leq 100$ $0 \leq K \leq NM$ A
$7 \sim 12$ $N=M=2^L,\ 0 < L \leq 200\,000$ $K=1$ B
$13 \sim 20$ $0 < N,M \leq 11$ $0 \leq K \leq NM$ C