QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 512 MB Puntuación total: 100

#2358. 什么?子任务?又是子任务?

Estadísticas

Vasya 正在组织编程竞赛。共有 $n$ 名参赛者报名参加即将到来的比赛。不幸的是,测试系统只有在参赛人数不超过 $m$ 时才能保持稳定。如果不采取任何措施,比赛很可能会出现问题,导致比赛变为非计分赛(unrated)。

Vasya 没有时间购买更多服务器,也没有时间为了提高性能而用其他编程语言重写测试系统。不过,他可以启用一些参赛者非常反感的特性,以至于他们会选择不参加比赛。具体来说,Vasya 可以:

  1. 禁用 HTTPS 连接
  2. 将比赛推迟 10 分钟
  3. 将所有题目的时限设置为 100 毫秒
  4. 将题目拆分为子任务
  5. 诚实地宣布比赛很可能变为非计分赛

请帮助 Vasya 找到一组特性,使得他能够以尽可能多的参赛人数顺利举办比赛。

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($1 < m < n \le 100\,000, 0 \le k \le 100\,000$)。接下来的 $k$ 行包含一对整数 $c_i$ ($1 \le c_i \le n$) 和 $f_i$ ($1 \le f_i \le 5$),表示如果 Vasya 启用了编号为 $f_i$ 的特性,参赛者 $c_i$ 将不会参加比赛。某些 $(c_i, f_i)$ 对可能是相同的。

输出格式

如果无法在参赛人数不超过 $m$ 的情况下举办比赛,请打印短语 “Round will be unrated”(不含引号)。否则,打印一个整数:计分赛能够拥有的最大参赛人数。

样例

样例输入 1

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

样例输出 1

6

样例输入 2

10 9 0

样例输出 2

Round will be unrated

样例输入 3

5 4 3
4 1
4 2
1 2

样例输出 3

4

样例输入 4

2 1 2
1 1
2 1

样例输出 4

0

说明

在第一个样例中,Vasya 的最优策略是启用第一个和第五个特性。这样参赛者 2、3、4 和 9 将不会参加比赛。

在第三个样例中,Vasya 的最优策略是启用第一个特性。这样参赛者 4 将不会参加比赛。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.