問題一覧 > 通常問題

No.3800 Screw manufacturing

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : 👑 ssmbc2929_bartok / テスター : yuki4869. / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 13754 / 自分の提出
問題文最終更新日: 2026-11-13 22:51:10
yukicoder contest 523 オムニバス (順位表) の他の問題:

問題文

とある小さな町工場では建設用のネジを生産しています。
この工場では現在 $N$ 種類のネジを作っており、種類 $i$ のネジの注文が $R_i$ 本入っています。

ネジを $1$ 本完成させるには、次の $2$ つの作業をこの順に行う必要があります。

  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もしくは右上の雲マークをクリックしてアカウントを作成してください。