結果

問題 No.3325 陰陽師
コンテスト
ユーザー The_Bouningeeeen
提出日時 2025-11-01 16:39:34
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,491 bytes
コンパイル時間 14,339 ms
コンパイル使用メモリ 400,144 KB
実行使用メモリ 24,996 KB
最終ジャッジ日時 2025-11-01 16:40:08
合計ジャッジ時間 30,635 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;
use std::collections::BTreeMap;

fn main() {
    input! {
        n: usize,
        m: usize,
        s: [usize; n],
        t: [usize; m],
    }

    let mut map = BTreeMap::new();
    for i in 0..n {
        map.count_up(s[i], 1);
    }

    let mut left = 0;
    let mut right = m;
    let mut ans = 0;
    while right - left > 1 {
        let mid = (left + right) / 2;
        let mut t: Vec<_> = t[..=mid].iter().cloned().collect();
        t.sort();
        let mut map = map.clone();

        let mut cost = 0;
        for t in t {
            let Some((&acrylic_stand, _)) = map.range(t..).next() else {
                right = mid;
                break;
            };
            map.count_down(acrylic_stand, 1);
            cost = cost.max(acrylic_stand - t);
        }
        left = mid;
        ans = cost;
    }
    println!("{}", ans);
}

trait MapCounter<K> {
    fn count_up(&mut self, key: K, value: usize);
    fn count_down(&mut self, key: K, value: usize);
}
impl<K> MapCounter<K> for BTreeMap<K, usize>
where
    K: Ord,
{
    fn count_up(&mut self, key: K, value: usize) {
        *self.entry(key).or_insert(0) += value;
    }
    fn count_down(&mut self, key: K, value: usize) {
        match self.get_mut(&key) {
            Some(v) => {
                if *v <= value {
                    self.remove(&key);
                } else {
                    *v -= value;
                }
            }
            None => (),
        }
    }
}
0