No.3808 Welcome to Mid Difficulty Problems
レベル :
/ AI推定難易度 : 1300
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 :
dyktr_06
/ テスター :
sepa38
tyawanmusi
タグ : / 解いたユーザー数 19
作問者 :
sepa38
問題文最終更新日: 2026-11-20 21:13:29
yukicoder contest 524
(順位表)
の他の問題:
問題文
あなたは、$N$ 問の問題が出題されるクイズ大会に出場します。
$i$ 問目のジャンルは $A_i$ であり、この問題を解くには $B_i$ 秒かかります。
あなたは好きな問題をいくつか選んで解くことができます。選んだ問題を解くのにかかる時間の合計は、$T$ 秒以下でなければなりません。
クイズ大会の得点は、解いた問題のジャンルの種類数と、解いた問題数の和です。
制限時間内に得られる得点の最大値を求めてください。
制約
- $1 \leq N \leq 5 \times 10^5$
- $1 \leq T \leq 10^9$
- $1 \leq A_i \leq N$
- $60 \leq B_i \leq 10^9$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N$ $T$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
出力
得られる得点の最大値を $1$ 行に出力してください。
サンプル
サンプル1
入力
5 180 1 60 1 100 2 120 2 70 3 200
出力
4
問題 $1$ と問題 $4$ を解くと、解いた問題数は $2$ であり、ジャンルの種類数は $2$ となるため、$4$ 点を得られます。
サンプル2
入力
7 9000 1 1800 2 2700 3 2700 4 2700 2 3600 1 3600 3 3600
出力
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。