use std::cmp; use std::io::{self, Read}; #[derive(Debug)] struct Input { n: i32, vs: Vec, } fn next_token(cin_lock: &mut io::StdinLock) -> String { cin_lock .by_ref() .bytes() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::() } fn read_input(cin_lock: &mut io::StdinLock) -> Input { let n = next_token(cin_lock).parse().unwrap(); let vs = (0..n) .map(|_| next_token(cin_lock).parse::().unwrap()) .collect(); Input { n, vs } } struct State { dp: [u32; 1000], } impl State { fn new() -> State { State { dp: [0; 1000] } } fn get(&self, i: i32) -> Option { self.as_index(i).map(|i| self.dp[i]) } fn get_or(&self, i: i32, default: u32) -> u32 { self.get(i).unwrap_or(default) } fn set(&mut self, i: i32, value: u32) { if let Some(i) = self.as_index(i) { self.dp[i] = value; } } fn as_index(&self, i: i32) -> Option { if i >= 0 && (i as usize) < self.dp.len() { Some(i as usize) } else { None } } } fn solve(input: Input, _cin_lock: &mut io::StdinLock) { let mut state = State::new(); for i in 0..input.n { let take = state.get_or(i - 2, 0) + input.vs[i as usize] as u32; let skip = state.get_or(i - 1, 0); state.set(i, cmp::max(take, skip)); } let answer = cmp::max(state.get_or(input.n - 1, 0), state.get_or(input.n, 0)); println!("{}", answer) } fn main() { let cin = io::stdin(); let mut cin_lock = cin.lock(); let input = read_input(&mut cin_lock); solve(input, &mut cin_lock); }