結果

問題 No.3509 Get More Money
コンテスト
ユーザー ガルム
提出日時 2026-04-18 13:31:38
言語 Rust
(1.97.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 90 ms / 2,000 ms
+ 116µs
コード長 2,396 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,741 ms
コンパイル使用メモリ 194,100 KB
実行使用メモリ 21,408 KB
最終ジャッジ日時 2026-09-08 14:07:34
合計ジャッジ時間 17,428 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::BTreeMap;
use std::io::{self, Read};

fn add(mp: &mut BTreeMap<i64, i64>, price: i64, count: i64) {
    if count > 0 {
        *mp.entry(price).or_insert(0) += count;
    }
}

fn remove_some(mp: &mut BTreeMap<i64, i64>, price: i64, count: i64, current: i64) {
    if count == current {
        mp.remove(&price);
    } else {
        *mp.get_mut(&price).unwrap() -= count;
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace().map(|x| x.parse::<i64>().unwrap());

    let t = it.next().unwrap() as usize;
    let mut answers = Vec::with_capacity(t);

    for _ in 0..t {
        let n = it.next().unwrap() as usize;
        let k = it.next().unwrap();

        let mut a = vec![0_i64; n];
        let mut b = vec![0_i64; n];
        let mut c = vec![0_i64; n];
        let mut d = vec![0_i64; n];

        for x in &mut a {
            *x = it.next().unwrap();
        }
        for x in &mut b {
            *x = it.next().unwrap();
        }
        for x in &mut c {
            *x = it.next().unwrap();
        }
        for x in &mut d {
            *x = it.next().unwrap();
        }

        let mut candidates = BTreeMap::<i64, i64>::new();
        let mut kept = 0_i64;
        let mut profit = 0_i128;

        for i in 0..n {
            add(&mut candidates, a[i], b[i]);
            kept += b[i];

            let mut remain = d[i];
            while remain > 0 {
                let Some((price, count)) = candidates.first_key_value().map(|(&p, &cnt)| (p, cnt)) else {
                    break;
                };

                if price >= c[i] {
                    break;
                }

                let take = remain.min(count);
                profit += (c[i] - price) as i128 * take as i128;
                remove_some(&mut candidates, price, take, count);
                add(&mut candidates, c[i], take);
                remain -= take;
            }

            while kept > k {
                let (price, count) = candidates.last_key_value().map(|(&p, &cnt)| (p, cnt)).unwrap();
                let take = (kept - k).min(count);
                remove_some(&mut candidates, price, take, count);
                kept -= take;
            }
        }

        answers.push(profit.to_string());
    }

    println!("{}", answers.join("\n"));
}
0