Submission #15521499


Source Code Expand

Copy
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);
}

Submission Info

Submission Time
Task C - 無駄なものが嫌いな人
User bouzuya
Language Rust (1.42.0)
Score 100
Code Size 829 Byte
Status
Exec Time 43 ms
Memory 5924 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 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
Case Name Status Exec Time Memory
max_1.txt 21 ms 2044 KB
max_2.txt 19 ms 2208 KB
max_3.txt 17 ms 2072 KB
max_4.txt 26 ms 2044 KB
pair_1.txt 33 ms 3492 KB
pair_2.txt 22 ms 2168 KB
power2_1.txt 33 ms 3040 KB
power2_2.txt 27 ms 2136 KB
power2_3.txt 20 ms 2100 KB
power2_4.txt 16 ms 1984 KB
power2_5.txt 10 ms 2480 KB
random_1.txt 35 ms 4960 KB
random_2.txt 31 ms 5048 KB
random_3.txt 43 ms 5924 KB
random_4.txt 37 ms 5844 KB
random_5.txt 21 ms 2128 KB
random_6.txt 18 ms 2176 KB
random_7.txt 27 ms 2252 KB
random_8.txt 34 ms 3296 KB
random_9.txt 27 ms 4908 KB
sample_1.txt 6 ms 2092 KB
sample_2.txt 2 ms 2096 KB
sample_3.txt 2 ms 2120 KB
sample_4.txt 1 ms 1980 KB
small_1.txt 1 ms 2068 KB
small_2.txt 1 ms 2068 KB
small_3.txt 1 ms 2076 KB
small_4.txt 1 ms 1964 KB