提出 #15521499

ソースコード 拡げる

use proconio::input;

fn main() {
    input! {
        n: usize,
        x: i64,
        w: [i64; n]
    };
    let mut map1 = std::collections::BTreeMap::new();
    for bits in 0..1 << n / 2 {
        let mut sum = 0_i64;
        for i in 0..n {
            if (bits >> i) & 1 == 1 {
                sum += w[i];
            }
        }
        *map1.entry(sum).or_insert(0) += 1;
    }
    let mut map2 = std::collections::BTreeMap::new();
    for bits in 0..1 << (n - n / 2) {
        let mut sum = 0_i64;
        for i in 0..n {
            if (bits >> i) & 1 == 1 {
                sum += w[n / 2 + i];
            }
        }
        *map2.entry(sum).or_insert(0) += 1_i64;
    }
    let mut ans = 0_i64;
    for (k, v) in map1.iter() {
        ans += v * map2.get(&(x - k)).unwrap_or(&0);
    }
    println!("{}", ans);
}

提出情報

提出日時
問題 C - 無駄なものが嫌いな人
ユーザ bouzuya
言語 Rust (1.42.0)
得点 100
コード長 829 Byte
結果 AC
実行時間 43 ms
メモリ 5924 KiB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 28
セット名 テストケース
All max_1.txt, max_2.txt, max_3.txt, max_4.txt, pair_1.txt, pair_2.txt, power2_1.txt, power2_2.txt, power2_3.txt, power2_4.txt, power2_5.txt, random_1.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt
ケース名 結果 実行時間 メモリ
max_1.txt AC 21 ms 2044 KiB
max_2.txt AC 19 ms 2208 KiB
max_3.txt AC 17 ms 2072 KiB
max_4.txt AC 26 ms 2044 KiB
pair_1.txt AC 33 ms 3492 KiB
pair_2.txt AC 22 ms 2168 KiB
power2_1.txt AC 33 ms 3040 KiB
power2_2.txt AC 27 ms 2136 KiB
power2_3.txt AC 20 ms 2100 KiB
power2_4.txt AC 16 ms 1984 KiB
power2_5.txt AC 10 ms 2480 KiB
random_1.txt AC 35 ms 4960 KiB
random_2.txt AC 31 ms 5048 KiB
random_3.txt AC 43 ms 5924 KiB
random_4.txt AC 37 ms 5844 KiB
random_5.txt AC 21 ms 2128 KiB
random_6.txt AC 18 ms 2176 KiB
random_7.txt AC 27 ms 2252 KiB
random_8.txt AC 34 ms 3296 KiB
random_9.txt AC 27 ms 4908 KiB
sample_1.txt AC 6 ms 2092 KiB
sample_2.txt AC 2 ms 2096 KiB
sample_3.txt AC 2 ms 2120 KiB
sample_4.txt AC 1 ms 1980 KiB
small_1.txt AC 1 ms 2068 KiB
small_2.txt AC 1 ms 2068 KiB
small_3.txt AC 1 ms 2076 KiB
small_4.txt AC 1 ms 1964 KiB