← 返回题目列表

AtCoder · joig2022_d

D. 草莓2

中文机器翻译题面 查看原题

配点: 100 点

問題文

热爱水果的Bitaro决定尝试一下采摘草莓。在比特罗面前 1 有一张带腿的桌子。桌子的形状是长方形的,有垂直的 H 行,横 W 它被分成一个列网格。在桌子上 N 草莓被放置,i 番目 (1 \leqq i \leqq N) 上面的草莓 A_i 行,从左起 B_i 它位于列的正方形中。同一个方格上可能会放置多个草莓。

Bitaro 垂直地站在他的桌子上。 3 行,横 3 形成一个方形的柱子区域 选择 9 方格并取出这些方格中的所有草莓。这种行为是 仅执行此操作 1 次。

Bitaro想要收集尽可能多的草莓。

给定有关桌子大小和草莓位置的信息,编写一个程序来查找可以收获的最大草莓数量。

制約

  • 3 \leqq H \leqq 1\,000\,000\,000.
  • 3 \leqq W \leqq 1\,000\,000\,000.
  • 1 \leqq N \leqq 60\,000.
  • 1 \leqq A_i \leqq H (1 \leqq i \leqq N).
  • 1 \leqq B_i \leqq W (1 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (14 点) H \leqq 1\,000,W \leqq 1\,000,N \leqq 20.
  2. (16 点) H \leqq 1\,000,W \leqq 1\,000.
  3. (29 点) H \leqq 1\,000\,000,N \leqq 500.
  4. (15 点) H = 3.
  5. (20 点) H \leqq 1\,000\,000.
  6. (6 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为对于该子作业是正确的。

每次提交的分数是所提交源代码被认为正确的子任务分数的总和。

该作业的分数是该作业所有提交内容的最高分数。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

H W
N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

最大可采摘草莓数量为标准产量。 1 行。 在


入力例 1

4 5
7
1 1
1 5
2 2
2 4
3 3
4 2
4 4

出力例 1

5

草莓的排列如图所示(红圈代表草莓)。

いちごの配置の図示

通过选择形成粗框包围区域的正方形, 你可以获得5 草莓。 你不能采摘超过

5 个草莓,所以5 。

此输入示例是一个小作业。 1, 2, 3, 5, 6 满足约束。 当


入力例 2

3 5
6
1 1
1 2
2 1
2 4
2 4
3 4

出力例 2

4

多个草莓可以放置在同一个方块上。

此输入示例满足所有子任务约束。 选择


入力例 3

3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815

出力例 3

9

此输入示例是一个小作业。 3, 4, 5, 6 满足约束。 当


入力例 4

11 11
20
7 7
6 11
5 7
8 8
9 9
5 5
8 4
4 4
4 8
2 6
1 6
6 2
3 3
9 3
7 5
6 1
10 6
6 10
11 6
3 9

出力例 4

4

此输入示例是一个小作业。 1, 2, 3, 5, 6 满足约束。 当