AtCoder Beginner Contest 438 D

https://atcoder.jp/contests/abc438/tasks/abc438_d

AとBだけで考えると、途中まででよりBよりAが上回っていればよいので、AからBを引いて足してより大きくなっていればいいことに気が付きます。入力例1では、それぞれの項を引き算すると、

-1 1 -2 2 1

累積和は、

-1 0 -2 0 1

この中で最大を取ればいいのですが、最後の1を取るとBが一つも取れなくなってしまうので、最初と最後を除いて、0ですね。これにBの和を足せばよいです。
Cも考慮に入れると、C-Bも同じことを右からやります。そうすると、累積和は、

1 3 3 2 3

順番を逆にしています。A-BもC-Bもそれまでの最大値を得ると、

-1 0 0 0 1
 1 3 3 3 3

となります。これで尺取り法的に最大値を得ればよいです。

// Tail of Snake
#![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 ////////////////////

fn read_input() -> (Vec<i64>, Vec<i64>, Vec<i64>) {
    let _N: usize = read();
    let A: Vec<i64> = read_vec();
    let B: Vec<i64> = read_vec();
    let C: Vec<i64> = read_vec();
    (A, B, C)
}

fn sub(u: &Vec<i64>, v: &Vec<i64>) -> Vec<i64> {
    u.iter().zip(v.iter()).map(|(&a, &b)| a - b).collect::<Vec<i64>>()
}

fn accumulate(v: &Vec<i64>) -> Vec<i64> {
    let N = v.len();
    let mut w: Vec<i64> = vec![0; N+1];
    for i in 0..N {
        w[i+1] = w[i] + v[i]
    }
    w
}

fn collect_max(v: &Vec<i64>) -> Vec<i64> {
    let N = v.len();
    let mut w: Vec<i64> = vec![v[1]; N-1];
    for i in 2..N {
        w[i-1] = max(w[i-2], v[i])
    }
    w
}

fn reverse(v: &Vec<i64>) -> Vec<i64> {
    v.iter().rev().cloned().collect::<Vec<i64>>()
}

fn F(A: Vec<i64>, B: Vec<i64>, C: Vec<i64>) -> i64 {
    let N = A.len();
    let v = collect_max(&accumulate(&sub(&A, &B)));
    let w = collect_max(&accumulate(&reverse(&sub(&C, &B))));
    
    let s = B.iter().sum::<i64>();
    let mut max_value = 0;
    for i in 0..N-2 {
        let value = v[i] + w[N-3-i] + s;
        max_value = max(max_value, value)
    }
    max_value
}

fn main() {
    let (A, B, C) = read_input();
    println!("{}", F(A, B, C))
}