DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

肥料の納品

問題に戻る

解説

ttt 回の合成でアンモニアを 2t2t2t 缶得るので、必要な最小回数は t=⌈K/2⌉t=\lceil K/2\rceilt=⌈K/2⌉ である。合成回数を増やすと必要な原料が増えるため、費用は小さくならない。窒素 ttt 缶と水素 3t3t3t 缶の購入を別々に最適化すればよい。

どちらの原料も、缶価格が低い供給元から順に購入する。高い供給元から購入した缶があり、より安い供給元に未使用の在庫があれば、その缶を安い方から購入するように変更できる。総購入量は変わらず、費用は減る。同じ価格の供給元の順序は費用に影響しない。よって、供給元を価格の昇順に並べ、在庫と残り必要量の小さい方だけ購入すればよい。どちらかの原料が不足する場合は -1 を出力する。

M=kn+khM=k_n+k_hM=kn​+kh​ とすると、時間計算量は O(Mlog⁡M)O(M\log M)O(、空間計算量は である。購入量は合計 缶で、缶価格は高々 なので、購入可能な場合の答えは最大 である。

Solution written by GPT

M
log
M
)
O(M)O(M)O(M)
4t≤2⋅1094t\leq 2\cdot 10^94t≤2⋅109
10610^6106
2⋅10152\cdot 10^{15}2⋅1015