https://atcoder.jp/contests/abc306/tasks/abc306_d
単なるDPです。
AtCoderでは定数を関数とかで定義するのはダメみたいです。
// Poisonous Full-Course #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } //////////////////// process //////////////////// type Dish = (i32, i64); //const INF: i64 = 10i64.pow(16); const INF: i64 = 10000000000000000; fn read_input() -> Vec<Dish> { let N: usize = read(); let dishes: Vec<Dish> = (0..N).map(|_| read_vec()). map(|v| (v[0] as i32, v[1])).collect(); dishes } fn update_score(score: (i64, i64), dish: Dish) -> (i64, i64) { match dish { (0, s) => (max(score.0, max(score.0, score.1) + s), score.1), (_, s) => (score.0, max(score.0 + s, score.1)) } } fn f(dishes: Vec<Dish>) -> i64 { let N = dishes.len(); let mut score: (i64, i64) = (0, -INF); for i in 0..N { score = update_score(score, dishes[i]) } max(score.0, score.1) } //////////////////// main //////////////////// fn main() { let dishes = read_input(); println!("{}", f(dishes)) }