No.1104 オンライン点呼
タグ : / 解いたユーザー数 21
作問者 :
blu3mo
/ テスター :
ngtkana
管理者より
申し訳ないです。 現在この問題の想定解に誤りがある可能性が高い状態です。飛ばしてください...テストケースも公開しました。
問題文
あるオンライン会議に、$N$人の社員が家から参加しています。
社員にはそれぞれ社員番号$1,2,...,N$が割り振られています。
社員$i$の家のインターネット回線は、送信（上り）に$A_i$秒、受信（下り）に$B_i$秒かかります。
このオンライン会議で、社員$1$から点呼をとります。
社員$j$ ($2 \leq j \leq N$)は、以下の条件の一つが満たされた瞬間に「$j$」と叫びます。
・$j-1$の数字が聞こえた
・$j-2$の数字が聞こえてから$K$秒経っても、$j-1$の数字が聞こえない
ただし、j=2の場合は、一つ目の条件が満たされたときに叫びます。
社員$1$が「$1$」と叫んでから、社員全員が自分の番号を叫ぶまで何秒かかるでしょうか。
入力
$N\ K$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$
・入力は全て整数
・$1 \leq N \leq 10^5$
・$0 \leq K \leq 10^8$
・$0 \leq A_i, B_i \leq 10^8$
出力
社員$1$が「$1$」と叫んでから、社員全員が自分の番号を叫ぶまでにかかる秒数を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 3 3 2 4 5 1 7 1 3 4 2
出力
18
・社員 $4$ は、社員 $2$ の声を聞いた$7$ 秒後に社員 $3$ の声を聞きます。
・社員 $5$ は、社員 $3$ の声を聞いた$9$ 秒後に社員 $4$ の声を聞きます。
・その他の社員 $i$ は、社員 $i-2$ の声を聞いてから社員 $i-1$ の声を聞くまでに $K$ 秒以上かかることはありません。
よって、合計 $18$ 秒かかります。
サンプル2
入力
8 2 1 3 2 0 1 2 1 4 1 0 3 1 3 2 0 1
出力
15
サンプル3
入力
1 3 10000 10000
出力
0
参加者が1人しかいないため、点呼は0秒で終了します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。