use proconio::input; const NUM_STATES: usize = 5; fn main() { input! { n: usize, aa: [usize; n], bb: [usize; n], cc: [usize; n], } let mut dp1 = vec![[0_usize; NUM_STATES]; n + 1]; for i in 0..n { let weights = [aa[i], bb[i], cc[i], bb[i], aa[i]]; for state in 0..NUM_STATES { for next_state in state..NUM_STATES { dp1[i + 1][next_state] = dp1[i + 1][next_state].max(dp1[i][state] + weights[next_state]); } } } let mut dp2 = vec![[0_usize; NUM_STATES]; n + 1]; for i in 0..n { let weights = [aa[i], bb[i], aa[i], bb[i], aa[i]]; for state in 0..NUM_STATES { for next_state in state..NUM_STATES { dp2[i + 1][next_state] = dp2[i + 1][next_state].max(dp2[i][state] + weights[next_state]); } } } let ans = dp1[n][2..].iter().chain(&dp2[n][3..]).max().unwrap(); println!("{}", ans); }