AtCoder Beginner Contest 286 D

https://atcoder.jp/contests/abc286/tasks/abc286_d

和を状態としたDPですね。

// Money in Hand
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<(usize, usize)>) {
    let v = read_vec();
    let N: usize = v[0];
    let X: usize = v[1];
    let AB: Vec<(usize, usize)> = (0..N).map(|_| read_vec()).
                                            map(|w| (w[0], w[1])).collect();
    (X, AB)
}

fn update(v: Vec<bool>, a: usize, b: usize) -> Vec<bool> {
    let mut w = (0..(v.len()+a*b)).map(|_| false).collect::<Vec<bool>>();
    for (i, c) in v.into_iter().enumerate() {
        if c {
            for d in (0..a*b+1).step_by(a) {
                w[i+d] = true
            }
        }
    }
    w
}

fn f(X: usize, AB: Vec<(usize, usize)>) -> bool {
    let M = AB.iter().map(|(a, b)| a * b).sum::<usize>();
    if X > M {
        return false
    }
    let mut v = (0..(M+1)).map(|i| i == 0).collect::<Vec<bool>>();
    for (a, b) in AB.into_iter() {
        v = update(v, a, b)
    }
    v[X]
}

fn main() {
    let (X, AB) = read_input();
    println!("{}", YesNo(f(X, AB)))
}