macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; ( iter = $ iter : ident , $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut $ iter = s . split_whitespace ( ) ; input_inner ! { $ iter , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let s = { use std :: io :: Read ; let mut s = String :: new ( ) ; std :: io :: stdin ( ) . read_to_string ( & mut s ) . unwrap ( ) ; s } ; let mut iter = s . split_whitespace ( ) ; input_inner ! { iter , $ ( $ r ) * } } ; }
macro_rules ! input_inner { ( $ iter : expr ) => { } ; ( $ iter : expr , ) => { } ; ( $ iter : expr , mut $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let mut $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , mut $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , mut $ var : usize $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ iter , $ t ) ; input_inner ! { $ iter $ ( $ r ) * } } ; ( $ iter : expr , $ var : ident $ ( $ r : tt ) * ) => { input_inner ! { $ iter , $ var : usize $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ iter : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ iter , $ t ) ) ,* ) } ; ( $ iter : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ iter , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ iter : expr , { chars : $ base : expr } ) => { read_value ! ( $ iter , String ) . chars ( ) . map ( | c | ( c as u8 - $ base as u8 ) as usize ) . collect ::< Vec < usize >> ( ) } ; ( $ iter : expr , { char : $ base : expr } ) => { read_value ! ( $ iter , { chars : $ base } ) [ 0 ] } ; ( $ iter : expr , chars ) => { read_value ! ( $ iter , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ iter : expr , char ) => { read_value ! ( $ iter , chars ) [ 0 ] } ; ( $ iter : expr , usize1 ) => { read_value ! ( $ iter , usize ) - 1 } ; ( $ iter : expr , $ t : ty ) => { $ iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) } ; }
#[derive(Clone, Debug, Default)]
pub struct BitSet {
    size: usize,
    bits: Vec<u64>,
}
impl BitSet {
    pub fn new(size: usize) -> Self {
        BitSet {
            size: size,
            bits: vec![0; (size + 63) / 64],
        }
    }
    pub fn get(&self, i: usize) -> bool {
        self.bits[i >> 6] & 1 << i != 0
    }
    pub fn set(&mut self, i: usize, b: bool) {
        if b {
            self.bits[i >> 6] |= 1 << (i & 63);
        } else {
            self.bits[i >> 6] &= !(1 << (i & 63));
        }
    }
    pub fn count_ones(&self) -> u64 {
        self.bits.iter().map(|x| x.count_ones() as u64).sum()
    }
    pub fn trim(&mut self) {
        if self.size & 63 != 0 {
            if let Some(x) = self.bits.last_mut() {
                *x &= 0xffffffffffffffff >> 64 - (self.size & 63);
            }
        }
    }
}
impl std::ops::ShlAssign<usize> for BitSet {
    fn shl_assign(&mut self, rhs: usize) {
        let k = rhs >> 6;
        let d = rhs & 63;
        if k >= self.bits.len() {
            for x in self.bits.iter_mut() {
                *x = 0;
            }
        } else {
            if d == 0 {
                for i in (k..self.bits.len()).rev() {
                    self.bits[i] = self.bits[i - k];
                }
            } else {
                for i in (k + 1..self.bits.len()).rev() {
                    self.bits[i] = self.bits[i - k] << d | self.bits[i - k - 1] >> 64 - d;
                }
                self.bits[k] = self.bits[0] << d;
            }
            for x in self.bits[..k].iter_mut() {
                *x = 0;
            }
            self.trim();
        }
    }
}
impl std::ops::Shl<usize> for BitSet {
    type Output = Self;
    fn shl(mut self, rhs: usize) -> Self::Output {
        self <<= rhs;
        self
    }
}
impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet {
    fn bitor_assign(&mut self, rhs: &'a Self) {
        for (l, r) in self.bits.iter_mut().zip(rhs.bits.iter()) {
            *l |= *r;
        }
        self.trim();
    }
}
impl<'a> std::ops::BitOr<&'a BitSet> for BitSet {
    type Output = Self;
    fn bitor(mut self, rhs: &'a Self) -> Self::Output {
        self |= rhs;
        self
    }
}
fn main() {
    input! { n, a: [usize; n] };
    let s = a.iter().sum::<usize>();
    let mut bits = BitSet::new(s + 1);
    bits.set(0, true);
    for i in 0..n {
        let tmp = bits.clone() << a[i];
        bits |= &tmp;
    }
    for i in (s + 1) / 2..s + 1 {
        if bits.get(i) {
            println!("{}", i);
            return;
        }
    }
}


Measured memory_bytes: 6396