結果
問題 | No.1701 half price |
ユーザー |
|
提出日時 | 2021-10-09 01:11:39 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 62 ms / 3,000 ms |
コード長 | 2,473 bytes |
コンパイル時間 | 14,266 ms |
コンパイル使用メモリ | 383,540 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 10:12:15 |
合計ジャッジ時間 | 14,112 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
use std::collections::HashSet;fn main() {let (n, w) : (usize,usize) = input_t();let a : Vec<usize> = input_vec();let mut ans = 0;for i in 1..1<<n {let v = (0..n).filter(|&j| i>>j&1 == 1).map(|i| a[i]).collect::<Vec<_>>();let mut s = HashSet::new(); s.insert(0);for v in v.into_iter() {let mut ss = HashSet::new();for si in s.into_iter() { ss.insert(si + v); ss.insert(si + v/2); }s = ss;}if s.contains(&w) { ans += 1; }}println!("{}", ans);}#[allow(dead_code)]fn input<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}#[allow(dead_code)]fn input_t<T: std::str::FromStr, U: std::str::FromStr>() -> (T, U) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap())}#[allow(dead_code)]fn input_t3<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr>() -> (T1, T2, T3) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap())}#[allow(dead_code)]fn input_t4<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr>() -> (T1, T2, T3, T4) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap())}#[allow(dead_code)]fn input_t5<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr, T5: std::str::FromStr>() -> (T1, T2, T3, T4,T5) {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();let s = s.trim().split_whitespace().collect::<Vec<&str>>();(s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap(), s[4].parse().ok().unwrap())}#[allow(dead_code)]fn input_vec<T: std::str::FromStr>() -> Vec<T> {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect()}