結果
問題 | No.1701 half price |
ユーザー |
|
提出日時 | 2021-10-08 22:57:53 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 101 ms / 3,000 ms |
コード長 | 2,219 bytes |
コンパイル時間 | 11,958 ms |
コンパイル使用メモリ | 402,980 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 06:11:42 |
合計ジャッジ時間 | 13,418 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr,) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}/// Generates an Iterator over subsets of univ, in the descending order./// Verified by: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3050308struct SubsetIter { bits: Option<usize>, univ: usize }impl Iterator for SubsetIter {type Item = usize;fn next(&mut self) -> Option<usize> {match self.bits {None => None,Some(bits) => {let ans = bits;self.bits =if bits == 0 { None }else { Some((bits - 1) & self.univ) };Some(ans)}}}}fn subsets(univ: usize) -> SubsetIter {SubsetIter { bits: Some(univ), univ: univ }}fn main() {input! {n: usize, w: i64,a: [i64; n],}let mut ans = 0;for bits in 1..1 << n {let mut ok = false;for sub in subsets(bits) {let mut s = 0;for i in 0..n {if (sub & 1 << i) != 0 {s += a[i] / 2;} else if (bits & 1 << i) != 0 {s += a[i];}}if s == w {ok = true;}}if ok {ans += 1;}}println!("{}", ans);}