No.3800 Screw manufacturing
タグ : / 解いたユーザー数 8
作問者 : 👑
yuki4869.
/ テストしたAI :
問題文
とある小さな町工場では建設用のネジを生産しています。
この工場では現在 $N$ 種類のネジを作っており、種類 $i$ のネジの注文が $R_i$ 本入っています。
ネジを $1$ 本完成させるには、次の $2$ つの作業をこの順に行う必要があります。
- 成形:鉄の棒を必要な太さと長さに成形し、ネジの頭を作る。この作業を終えたものをブランクと呼ぶ。
- ねじ山加工:ブランクにねじ山(螺旋)をつける。
成形には機械 $1$ を、ねじ山加工には機械 $2$ を使用します。種類 $i$ のネジ $1$ 本について、成形には $A_i$ 分、ねじ山加工には $B_i$ 分かかります。
それぞれの機械は $1$ 台ずつあり、各機械は同時に $1$ 本のネジだけを加工できます。
ネジのねじ山加工を開始するには、そのネジの成形が完了している必要があります。
成形が完了したネジは、本数の制限なく保管しておけます。
生産を始める前に、種類ごとの生産順序を自由に決められます。
両機械はともにこの順序に従い、それぞれの機械はある種類のネジを必要な本数すべて加工してから次の種類へ進みます。
各機械で加工するネジの種類を変えるには、アタッチメントの交換に $T$ 分かかります。
各機械は、自身が担当する現在の種類の加工をすべて終えた時点で、次の種類への交換を開始できます。交換中の機械では加工できません。
アタッチメントの交換は機械ごとに独立して行います。 一方の機械で加工や交換を行っている間も、もう一方の機械は加工や交換を行えます。
また、$2$ 台の機械が異なる種類のネジを同時に加工することもできます。
最初に生産する種類のアタッチメントは、両機械とも時刻 $0$ に取り付けられており、最初の準備には時間がかかりません。
最後の種類の加工を終えた後に交換する必要はありません。各加工および交換は途中で中断できません。
時刻 $0$ から生産を始めます。生産順序を適切に選んだとき、工場に入っているすべての注文品について、ねじ山加工が完了するまでにかかる時間の最小値を、日・時間・分 に換算して求めてください。
ただし、$1$ 日は $24$ 時間、$1$ 時間は $60$ 分とします。
制約
- $3 \le N \le 3 \times 10^5$
- $1 \le R_i \le 1000 (1 \le i \le N)$
- $1 \le A_i, B_i \le 1000$
- $1 \le T \le 10^9$
- 入力はすべて整数
入力
$N$ $T$ $R_1 \ R_2 \ \cdots R_N$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_N \ B_N$
出力
$D$ $H$ $M$
「$D$ 日 $H$ 時間 $M$ 分」のフォーマットに従って、スペース区切りで出力せよ。
※ $0 \le D, \ 0 \le H < 24,\ 0 \le M < 60$ を満たすようにせよ。
最後に改行すること。
サンプル
サンプル1
入力
3 3 2 2 2 4 6 3 1 2 5
出力
0 0 32
ネジ $3\to 1 \to 2$ の順で作ることで、最短生産が可能です。
このとき、$32$ 分かかります。
よって、出力例のように出力します。
日・時間・分のどこかが $0$ となる場合も出力を忘れないようにしてください。
サンプル2
入力
4 5 2 3 1 2 14 21 11 16 13 31 15 12
出力
0 2 51
サンプル3
入力
10 100000 100 200 150 300 200 100 500 600 777 999 100 300 400 250 200 200 100 500 900 390 450 450 600 900 100 100 872 198 231 333
出力
1766 7 51
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。