use std::collections::{HashMap, HashSet}; use proconio::marker::Chars; fn main() { proconio::input! { n: u64, w: [u64; n], } let sum = w.iter().sum::(); if sum % 2 == 1 { println!("impossible"); return; } let half = sum / 2; let mut memo = vec![false; half as usize + 1]; memo[0] = true; for w in w { for i in (0..half + 1).rev() { if memo[i as usize] == false || i + w > half { continue; } memo[(i + w) as usize] = true; } } if memo[half as usize] { println!("possible"); } else { println!("impossible"); } } #[cfg(test)] mod test { use super::*; #[test] fn test() {} }