Submission #1233344

---

Source Code Expand

use std::io;
use std::io::{Read, BufReader};
use std::cmp;

fn next_token<R: Read>(reader: &mut R) -> Vec<u8> {
    let mut buf: [u8; 1] = [0];
    let mut read_chars = false;
    let mut ret: Vec<u8> = vec![];

    loop {
        if reader.read(&mut buf).unwrap() == 0 {
            break;
        } else {
            if buf[0] == '\r' as u8 || buf[0] == '\n' as u8 || buf[0] == ' ' as u8 {
                if read_chars {
                    break;
                }
            } else {
                read_chars = true;
                ret.push(buf[0]);
            }
        }
    };
    ret
}
fn next_i64<R: Read>(reader: &mut R) -> i64 {
    let token = next_token(reader);
    let mut ret: i64 = 0;
    let mut sgn = false;

    for c in token {
        if '0' as u8 <= c && c <= '9' as u8 {
            ret = ret * 10 + (c - ('0' as u8)) as i64;
        } else if '-' as u8 == c {
            sgn = true;
        }
    };
    ret * if sgn { -1 } else { 1 }
}
fn next_i32<R: Read>(reader: &mut R) -> i32 {
    next_i64(reader) as i32
}
fn update(dp: &mut [bool], v: i32) {
    let mut i = dp.len() as i32 - 1 - v;
    while i >= 0 {
        if dp[i as usize] {
            dp[(i + v) as usize] = true
        }
        i -= 1;
    }
}
fn solve(k: i32, cards: &[i32], dp: [bool; 5050]) -> i32 {
    if cards.len() == 1 {
        for i in cmp::max(0, k - cards[0])..k {
            if dp[i as usize] {
                return 0
            }
        }
        1
    } else {
        let thresh = cards.len() / 2;
        let mut ret = 0;
        {
            let mut dp2 = dp;
            for i in thresh..cards.len() {
                update(&mut dp2, cards[i as usize]);
            }
            ret += solve(k, &cards[0..thresh], dp2);
        }
        {
            let mut dp2 = dp;
            for i in 0..thresh {
                update(&mut dp2, cards[i as usize]);
            }
            ret += solve(k, &cards[thresh..cards.len()], dp2);
        }
        ret
    }
}
fn main() {
    let buf = &mut BufReader::new(io::stdin());

    let n = next_i32(buf);
    let k = next_i32(buf);

    let mut cards: [i32; 5050] = [-1; 5050];
    for i in 0..n {
        cards[i as usize] = next_i32(buf);
    }
    let mut dp = [false; 5050];
    dp[0] = true;
    println!("{}", solve(k, &cards[0..(n as usize)], dp));
}

Submission Info

Judge Result