网格图差异问题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
看起来你很喜欢网格图。
题目描述
- 给出一个 行 列的网格图,每个格子被染成黑色或白色。
- 初始情况下,若 为奇数则 被染成黑色,否则 被染成白色。
- 现在有 个格子的颜色被改变了,即如果是黑色则变为白色,如果是白色则变为黑色。
- 你需要找出一个子矩形,使得矩形中黑色格子和白色格子数量差的绝对值最大,并输出这个值。
- 你可以通过阅读样例解释更好地理解题意。
输入格式
从文件 diff.in
中读入。
- 第一行两个数 ,
- 接下来 行,每行两个数 ,表示一个颜色被改变的格子,保证每个格子至多出现一次。
输出格式
输出到文件 diff.out
中。
- 一行一个整数表示答案。
样例输入输出
3 1
1 1
3 4
1 2
2 1
2 3
3 2
3 4
1 1
1 3
3 1
3 3
2
9
7
样例解释
【样例解释 1】 (1,1) 原本为白色,现在被染成了黑色,以 (1,1) 为左上角,(2,2) 为右下角的矩形中共有 3 黑 1 白,答案为 2。
【样例解释 2】 所有 9 个格子被染成了白色,答案为 9。
【样例解释 3】 除了 (2,2) 的 8 个格子被染成了黑色,答案为 7。
数据范围
测试点分布
- 本题不设子任务捆绑
- 保证被改变颜色的点的位置在整个网格图中均匀随机
- 本题所有测试点等分
- 数据强度具有一定梯度
- 请留意本题不同寻常的时间限制
测试点编号 | 限制 |
---|---|
1~20 | |
21~100 | N/A |
- 编号为 1 的大样例满足测试点 1~20 的限制
- 编号为 2 的大样例满足测试点 21~100 的限制