题目详情题解（0）讨论（0）提交记录（0）

AT_abc205_f.[ABC205F] Grid and Tokens

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 HH 行 WW 列的网格，用 (r, c)(r,\,c) 表示从上往下第 rr 行、从左往右第 cc 列的格子。

有 NN 个棋子，对于第 ii 个棋子（1≤i≤N1 \leq i \leq N），你可以选择以下两种方式之一：

  • 将它放在满足 Ai≤r≤CiA_i \leq r \leq C_i 且 Bi≤c≤DiB_i \leq c \leq D_i 的某一个格子 (r, c)(r,\,c) 上；
  • 不放置该棋子。

这里，不能有两个棋子放在同一行或同一列。

你最多能放置多少个棋子？

输入格式

输入以如下格式从标准输入读入。

HH WW NN A1A_1 B1B_1 C1C_1 D1D_1 A2A_2 B2B_2 C2C_2 D2D_2 ⋮\vdots ANA_N BNB_N CNC_N DND_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    2 3 3
1 1 2 2
1 2 2 3
1 1 1 3

    输出#1

    2

  • 输入#2

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

    输出#2

    3

说明/提示

限制条件

  • 1≤H, W, N≤1001 \leq H,\, W,\, N \leq 100
  • 1≤Ai≤Ci≤H1 \leq A_i \leq C_i \leq H
  • 1≤Bi≤Di≤W1 \leq B_i \leq D_i \leq W
  • 输入均为整数。

样例解释 1

可以将第一个棋子放在格子 (1, 1)(1,\,1)，第二个棋子放在格子 (2, 2)(2,\,2)，第三个棋子不放，这样最多可以放 22 个棋子。无法放置 33 个棋子，因此输出 22。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页