B - カラフルパ研
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : {200} 点
問題文
パ研には N 人の部員がいます。それぞれの部員には 0 以上 2 \times 10^5 以下の整数で表される色がついており、i 番目の部員の色は A_i です。
カラフルなものが大好きな魔法少女の oliverx3 は、以下の呪文を唱えることができます:
- 部員を 1 人選び、その部員の色を 0 \leq x \leq 2 \times 10^5 を満たす整数 x に変える。ここで、呪文を唱える前と後では選ばれた部員の色は異なっている必要がある。
oliverx3 は今からちょうど M 回呪文を唱えます。
M 回の呪文を唱え終わったあとの、最終的な N 人の色の種類数として考えられる最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq A_i \leq 2\times 10^5\ (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N
出力
答えを 1 行に出力せよ。
入力例 1
6 2 1 1 1 2 4 4
出力例 1
5
たとえば、以下のように呪文を唱えることで 6 人の色の種類数を 5 にできます。
- 3 番目の部員の色を 1 から 3 に変える。
- 5 番目の部員の色を 4 から 10^5 に変える。
6 人の色の種類数を 5 より大きくすることはできないので、5 を出力します。
入力例 2
7 0 0 1 2 3 4 5 6
出力例 2
7
oliverx3 は呪文を一度も唱えることができませんが、パ研はもともとカラフルだったようです。
原案: oliverx3