20981번 - イベント巡り (Event Hopping) 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB63332749.091%

문제

IOI 国には 2 個の町があり，それぞれ 1, 2 と番号がついている．

これらの町では合計 N 個のイベントが行われる．これらのイベントには 1 から N までの番号がついている．イベント i (1 ≦ i ≦ N) は町 Pi で開催され，開催時刻は時刻 Si + 0.1 から時刻 Si + 0.9 までである．ここで Si は整数である．JOI 君がイベント i に参加するためには，時刻 Si + 0.1 から時刻 Si + 0.9 までの間，ずっと町 Pi にいる必要がある．

JOI 君はイベント巡りを行うことにした．イベント巡りではいくつかのイベントに参加し，必要ならば町と町の間を移動することもできる．JOI 君は時刻 0 からイベント巡りを開始する．このとき，好きな町から始めることができる．

JOI 君は町 1 と町 2 の間を双方向に移動することができる．2 つの町の間を移動するのにかかる時間は，JOI 君がその移動を開始する時刻までに参加したイベントの数を j として，D + K × j となる．

イベントと町の間の移動に関する情報が与えられるので，JOI 君が参加できるイベントの数の最大値を求めるプログラムを作成せよ．

입력

入力は以下の形式で標準入力から与えられる．

N D K
P1 S1
P2 S2
:
PN SN

출력

標準出力に，JOI 君が参加することのできるイベントの数の最大値を 1 行で出力せよ．

제한

  • 1 ≦ N ≦ 200 000．
  • 1 ≦ D ≦ 1012．
  • 0 ≦ K ≦ 1012．
  • 1 ≦ Pi ≦ 2 (1 ≦ i ≦ N)．
  • 1 ≦ Si ≦ 1012 (1 ≦ i ≦ N)．
  • Si ≠ Sj (1 ≦ i < j ≦ N)．
  • 入力される値はすべて整数である．

예제 입력 1 

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

예제 출력 1 

4

例えば，以下のように行動することで，JOI 君は 4 個のイベントに参加することができる．

  1. 時刻 0 において JOI 君は町 1 にいる．
  2. 時刻 1.1 から時刻 1.9 まで町 1 でイベント 1 に参加する．
  3. 時刻 2.1 から時刻 2.9 まで町 1 でイベント 2 に参加する．
  4. 時刻 3 から時刻 6 まで時間 3 (= D + K × 2) をかけて町 1 から町 2 に移動する．
  5. 時刻 6.1 から時刻 6.9 まで町 2 でイベント 5 に参加する．
  6. 時刻 7 から時刻 10 まで時間 3 (= D + K × 3) をかけて町 2 から町 1 に移動する．
  7. 時刻 10.1 から時刻 10.9 まで町 1 でイベント 3 に参加する．

どのように行動しても 5 個以上のイベントに参加することはできないため，4 を出力する．

この入力例はすべての小課題の制約を満たす．

예제 입력 2 

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

예제 출력 2 

6

例えば，以下のように行動することで，JOI 君は 6 個のイベントに参加することができる．

  1. 時刻 0 において JOI 君は町 2 にいる．
  2. 時刻 2.1 から時刻 2.9 まで町 2 でイベント 1 に参加する．
  3. 時刻 3 から時刻 8 まで時間 5 (= D + K × 1) をかけて町 2 から町 1 に移動する．
  4. 時刻 8.1 から時刻 8.9 まで町 1 でイベント 2 に参加する．
  5. 時刻 11.1 から時刻 11.9 まで町 1 でイベント 4 に参加する．
  6. 時刻 12 から時刻 23 まで時間 11 (= D + K × 3) をかけて町 1 から町 2 に移動する．
  7. 時刻 23.1 から時刻 23.9 まで町 2 でイベント 5 に参加する．
  8. 時刻 24.1 から時刻 24.9 まで町 2 でイベント 6 に参加する．
  9. 時刻 25.1 から時刻 25.9 まで町 2 でイベント 7 に参加する．

どのように行動しても 7 個以上のイベントに参加することはできないため，6 を出力する．

この入力例は小課題 4, 5, 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

この入力例は小課題 4, 5, 6 の制約を満たす．

출처

Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2020/2021 예선 2 3번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)