結果

問題 No.3459 Defeat Slimes
コンテスト
ユーザー NakLon131
提出日時 2026-02-28 16:05:46
言語 Rust
(1.93.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 132 ms / 3,000 ms
コード長 1,984 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,285 ms
コンパイル使用メモリ 203,740 KB
実行使用メモリ 22,796 KB
最終ジャッジ日時 2026-02-28 16:06:02
合計ジャッジ時間 11,143 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::BinaryHeap;
use std::cmp::min;
use proconio::input;

fn main() {
    input! {
        n: usize, // スライムの種類
        mut y: u128, // 現在のレベル
        z: u128, // 目標レベル
        clx: [(u128, u128, u128); n], // 各スライム(匹,必要レベル,獲得レベル)
    }
    
    // スライムの情報を必要レベルが大きい順に並べる
    // dummyを入れる
    let mut slime_info = Vec::new();
    slime_info.push((z, 0, 0)); // (必要レベル, 獲得レベル, 匹)
    for (c, l, x) in clx {
        slime_info.push((l, x, c));
    }
    slime_info.sort_by(|i, j| j.cmp(i));

    // 倒す匹
    let mut ans = 0;

    // 今のレベル以下のものを追加(獲得レベル, 匹)
    let mut hp = BinaryHeap::new();
    loop {
        let (l, x, c) = *slime_info.last().unwrap();
        if y >= l {
            hp.push((x, c));
            slime_info.pop();
        }
        else {
            break;
        }
    }


    // 獲得レベルが高い順に調べる
    while let Some((x, c)) = hp.pop() {
        
// {
//     println!("{}", y);
//     println!("heap:");
//     for (_i, &item) in hp.iter().enumerate() {
//         println!("{} {}", item.0, item.1);
//     }
// }          
        
        // 目標レベルを取得
        let (next, nx, nc) = *slime_info.last().unwrap();
        
        // 必要数だけ倒してレベルを上げる
        let mut cnt = (next - y + x-1) / x;
        cnt = min(cnt, c);
        y += cnt * x;
        ans += cnt;

        // 過剰に取り出した分は戻す
        if c > cnt {
            hp.push((x, c - cnt));
        }

        // 最終レベルに到達
        if y >= z {
            println!("{}", ans);
            return;
        }

        // 次の目標レベルを超えたら、キューを追加
        if y >= next {
            hp.push((nx, nc));
            slime_info.pop();
        }
    }
    
    println!("-1");
}
0