安全点検 (Safety Inspection)
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 1024 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
JOI 市には \(1\) 本の十分に長い道路がある．この道路は数直線とみなすことができ，各地点は \(1\) 個の実数による座標で表される．また JOI 市にはこの道路に沿って \(N\) 個の施設が設置されており，座標の小さい順に \(1\) から \(N\) までの番号がつけられている．施設 \(i\) (\(1 \leqq i \leqq N\)) の位置は座標 \(A_i\) である．
JOI 市ではこれから施設の安全点検が行われる．施設 \(i\) には点検しなければならない項目が \(B_i\) 個ある．今，点検を行うことができる \(K\) 人の大工が集められた．安全点検の開始のとき，大工は全員が座標 \(0\) にいる．点検が始まると，各大工は \(1\) 分間で，次の \(2\) つの行動のどちらかをとることができる．
- 距離 \(1\) だけ座標を移動する．
- 今いる座標にある施設の点検項目のうち，\(1\) 個の項目を選んで点検する．
安全点検を終えるとき，すべての建物のすべての点検項目が，\(1\) 人以上の大工によって点検されていなければならない．
大工の人数と施設の情報が与えられるので，安全点検を終えるのに最短で何分かかるかを求めるプログラムを作成せよ．
Constraints
- \(1 \leqq N \leqq 100\,000\)．
- \(1 \leqq K \leqq 10^{9}\)．
- \(1 \leqq A_i \leqq 10^{9}\) (\(1 \leqq i \leqq N\))．
- \(A_i < A_{i+1}\) (\(1 \leqq i \leqq N-1\))．
- \(1 \leqq B_i \leqq 10^{9}\) (\(1 \leqq i \leqq N\))．
- 入力される値はすべて整数である．
Subtasks
- (\(3\) 点) \(K = 1\)．
- (\(15\) 点) \(K = 2\)．
- (\(82\) 点) 追加の制約はない．
Input
入力は以下の形式で標準入力から与えられる．
\(N\) \(K\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_N\)
Output
標準出力に，安全点検を終えるのに最短で何分かかるかを \(1\) 行で出力せよ．
Examples
3 3 1 3 4 4 2 4
7
例えば，以下のように行動することで，\(7\) 分間で点検を終えることができる．ただし \(3\) 人の大工に番号をつけて，それぞれ大工 \(1,2,3\) と表す．
- 大工 \(1,2,3\) が座標 \(1\) に移動する．
- 大工 \(1,2,3\) がそれぞれ施設 \(1\) の点検を \(1\) 項目ずつ行う．
- 大工 \(1,2\) が座標 \(2\) に移動し，大工 \(3\) が施設 \(1\) の点検を \(1\) 項目行う．
- 大工 \(1,2\) が座標 \(3\) に移動し，大工 \(3\) が座標 \(2\) に移動する．
- 大工 \(1,2\) が座標 \(4\) に移動し，大工 \(3\) が座標 \(3\) に移動する．
- 大工 \(1,2\) がそれぞれ施設 \(3\) の点検を \(1\) 項目ずつ行い，大工 \(3\) が施設 \(2\) の点検を \(1\) 項目行う．
- 大工 \(1,2\) がそれぞれ施設 \(3\) の点検を \(1\) 項目ずつ行い，大工 \(3\) が施設 \(2\) の点検を \(1\) 項目行う．
どのように行動しても \(7\) 分未満で点検を終えることはできないので \(7\) を出力する．
6 1 1 4 5 6 11 15 12 5 9 8 10 4
63
この入力例は小課題 \(1,3\) の制約を満たす.
6 2 1 4 5 6 11 15 12 5 9 8 10 4
35
この入力例は小課題 \(2,3\) の制約を満たす.
6 5 1 4 5 6 11 15 12 5 9 8 10 4
19
Notes
JOI 2021 · JCIOI · CC BY-SA 4.0
Tags
No tags yet