結果

問題 No.989 N×Mマス計算（K以上）
コンテスト
ユーザー elphe
提出日時 2026-02-09 17:45:19
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,741 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,404 ms
コンパイル使用メモリ 209,616 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-02-09 17:45:24
合計ジャッジ時間 3,921 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin().lock()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    let n: usize = stdin.next().unwrap().parse().unwrap();
    let m: usize = stdin.next().unwrap().parse().unwrap();
    let k: u32 = stdin.next().unwrap().parse().unwrap();
    let op: char = stdin.next().unwrap().parse().unwrap();
    let b: Vec<u32> = (0..m)
        .map(|_| stdin.next().unwrap().parse().unwrap())
        .collect();
    let a: Vec<u32> = (0..n)
        .map(|_| stdin.next().unwrap().parse().unwrap())
        .collect();

    use std::io::Write;
    std::io::stdout()
        .lock()
        .write_all(output(solve(k, op, a, b)).as_bytes())
        .unwrap();
}

fn solve(k: u32, op: char, a: Vec<u32>, mut b: Vec<u32>) -> u64 {
    b.sort_unstable();
    let b = b;
    b.len() as u64 * a.len() as u64
        - match op {
            '+' => a
                .into_iter()
                .map(|a| mylib::lower_bound(&b, &(k.saturating_sub(a))) as u64)
                .sum::<u64>(),
            '*' => a
                .into_iter()
                .map(|a| mylib::lower_bound(&b, &((k + a - 1) / a)) as u64)
                .sum::<u64>(),
            _ => unreachable!(),
        }
}

fn output(ans: u64) -> String {
    ans.to_string() + "\n"
}

mod mylib {
    pub fn lower_bound<T: PartialOrd>(v: &[T], border: &T) -> usize {
        if v.is_empty() || v[0] >= *border {
            return 0;
        }
        let mut l: usize = 0;
        let mut r: usize = v.len();
        while l + 1 < r {
            let c = (l + r) / 2;
            if v[c] < *border {
                l = c;
            } else {
                r = c;
            }
        }
        r
    }
}
0