bzoj#P3577. 玩手机
玩手机
题目描述
现在有一堆手机放在坐标网格里面(坐标从 开始),坐标 的格子有 个手机。
玩手机当然需要有信号,不过这里的手机与基站与我们不太一样。基站分为两种:发送站和接收站(以下简称为 A 站和 B 站)。每个手机必须同时与一个 A 站和一个 B 站通信才能工作。
每个基站有一个正方形的覆盖范围(平行于网格)。覆盖范围可以用左下角和右上角的坐标表示(范围包括边角)。显然,手机只有在某个基站的范围内才能与这个基站通信。除此之外,每个基站还有最大接入的手机数量限制。
求最大同时工作的手机数量。
输入格式
第一行四个整数 ,表示坐标网格的规模是 ,共有 个 A 站和 个 B 站。
接下来是一个 的矩阵,第 行第 列的数为 。
接下来 行,每行 个数 ,表示第 个 A 站最大接入 个手机,覆盖范围为 。
接下来 行,每行 个数 ,含义同上。
输出格式
一个整数,即最大同时工作的手机数量。
3 3 1 2
1 1 1
1 1 1
1 1 1
100 1 1 3 3
4 1 1 2 2
4 2 2 3 3
7
数据规模与约定
对于 的数据满足 ,,,,,,。
题目来源
Streaming #2 by saffah