E - 放課後
Editorial
/
きたむーそれぞれの日の放課後に「デート」「競プロ」のうちいずれか片方の行動をとる。
きたむーは A 日以上デートできないと、愛が足りずに動けなくなってしまうので、 A 日に一度は必ずデートする。
このカップルには明日から N 日以内に B 回の記念日があり、それぞれ D_1,D_2,\cdots,D_B 日後である。この日には必ずデートを行う。 D_i は互いに異なる。
なお、きたむーは今日デートしており、彼の高校に休日はないものとする。


Time Limit: 1 sec / Memory Limit: 256 MB
配点: 300 点
この問題の解説はこちら。
問題文
※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。
きたむーは高校の競技プログラミング部に所属し、放課後も熱心にプログラミングに取り組んでいた。しかし最近、きたむーには彼女ができたようだ。
デートがしたい! デートがしたい! デートがしたい!
デートに着実に蝕まれていくプログラミング学習の時間。このままではきたむーのレートが落ちてしまうことに危機感を覚えたあなたは、彼の放課後のスケジュールを管理してあげることにした。
あなたは以下の点に配慮して明日以降の N 日分のスケジュールを立てることにした。
あなたはきたむーが競プロに取り組む日数を最大化したい。
制約
- 入力される値はすべて整数である
- 1 \leq N \leq 10^{18}
- 1 \leq A \leq N
- 0 \leq B \leq min(N,2 \times 10^5)
- 1 \leq D_i \leq N (1 \leq i \leq B)
- D_i \neq D_j (1 \leq i,j \leq B かつ i \neq j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A B D_1 D_2 \cdots D_B
出力
きたむーにプログラミング学習をさせることができる日数の最大値を1行で出力せよ。
入力例 1
10 4 2 4 6
出力例 1
7
明日から10日間のスケジュールを考えるが、4日以上競プロが連続してはならず、4日後、6日後の2日の記念日がある。競プロをP
、デートをD
と表記するなら、例えば、PPPDPDPPPD
とスケジュールを組むことで7日競プロに取り組ませることができる。
入力例 2
10 1 0
出力例 2
0
寂しがりすぎ。
入力例 3
5 2 5 1 2 3 4 5
出力例 3
0
記念日多すぎ。
入力例 4
10 5 3 4 3 7
出力例 4
7
入力例 5
100 16 11 90 98 88 82 40 16 32 45 87 67 48
出力例 5
88