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

AT_joi2021_yo2_c.イベント巡り (Event Hopping)

通过率：0%

AC君温馨提醒

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

题目描述

某地有两个镇。为简便，分别称其为 11 镇和 22 镇。

在一段时间内，这两个镇共举行了 NN 次活动。第 ii 次活动在 PiP_i 镇举行，时间从 (Si+0,1)(S_i+0,1) 持续到到 (Si+0.9)(S_i+0.9)。若想参与第 ii 次活动，需要在这段时间内在 PiP_i 镇。

你从 00 时刻开始在这两个城市之间移动。你可以选择你开始时所在的镇。在两个城镇之间移动所需的时间为 (D+K×j)(D+K\times j)，其中 jj 是你之前所参加的活动数。

请求出你最多能参加多少次活动。

输入格式

第一行输入三个整数 N,D,KN,D,K。

随后输入 NN 行，第二行输入两个整数 PiP_i 和 SiS_i。

输出格式

一行一个整数，最多可参加的活动数。

输入输出样例

  • 输入#1

    5 3 0
1 1
1 2
1 10
2 5
2 6

    输出#1

    4

  • 输入#2

    7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25

    输出#2

    6

  • 输入#3

    12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768

    输出#3

    8

  • 输入#4

    15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575

    输出#4

    11

说明/提示

样例解释请到 AtCoder 查看。

数据规模与约定

对于 100%100\% 的数据，满足：

  • 1≤N≤2000001\le N\le 200000；
  • 1≤D,Si≤10121\le D,S_i\le 10^{12}，当 1≤i<j≤N1\le i\lt j\le N 时 Si≠SjS_i\neq S_j；
  • 0≤K≤10120\le K\le 10^{12}；
  • Pi∈{1,2}P_i\in \{1,2\}；
  • 输入的所有值都为整数。

本题有部分分。 各子任务分值及特殊限制见下：

  • Subtask 0：为样例，00 分。
  • Subtask 1：K=0K=0，N≤20N\le 20，88 分。
  • Subtask 2：K=0K=0，N≤4000N\le 4000，1111 分。
  • Subtask 3：K=0K=0，2424 分。
  • Subtask 4：N≤160N\le 160，1212 分。
  • Subtask 5：N≤4000N\le 4000，2323 分。
  • Subtask 6：无特殊限制，2222 分。

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

首页