Shared code

#![allow(unused)]

use std::collections::VecDeque;

fn main() {
    // max_(a <= r - l + 1 <= b) sum(A[l..=r])
    // = max_(a <= r - l + 1 <= b) pref[r] - (pref[l - 1] if l >= 1 else 0)
    // = max_(a + l - 1 <= r <= b + l - 1) pref[r] - (pref[l - 1] if l >= 1 else 0)
    // l = 0 -> a - 1 <= r <= b - 1
    // l = 1 -> a + 0 <= r <= b + 0
    // l = 2 -> a + 1 <= r <= b + 1
    // => r forms sliding window of length b - a + 1
    // => finding maximum of pref[r] can be done using monotonic deque

    let inp = readv::<usize>();
    let (n, a, b) = (inp[0], inp[1], inp[2]);
    let arr = readv::<i64>();

    let mut pref = vec![arr[0]];
    for i in 1..n {
        pref.push(pref[i - 1] + arr[i]);
    }
    for _ in 0..b {
        pref.push(i64::MIN);
    }

    let rs = sliding_argmax(&pref, b - a + 1);
    let mut ans = i64::MIN;
    for l in (0..n).take_while(|l| l + a <= n) {
        let r = rs[b + l - 1];
        let v = pref[r] - if l == 0 { 0 } else { pref[l - 1] };
        ans = ans.max(v);
    }
    println!("{}", ans);
}

fn sliding_argmax<T>(arr: &[T], k: usize) -> Vec<usize>
where
    T: std::cmp::PartialOrd,
{
    let mut deq = VecDeque::new();
    let mut res = vec![usize::MAX; arr.len()];
    for i in 0..arr.len() {
        while let Some(x) = deq.back() {
            if arr[i] >= arr[*x] {
                deq.pop_back();
            } else {
                break;
            }
        }
        deq.push_back(i);
        res[i] = *deq.front().unwrap();
        if *deq.front().unwrap() + k - 1 == i {
            deq.pop_front();
        }
    }
    res
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn readv<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_ascii_whitespace()
        .map(|t| t.parse().ok().unwrap())
        .collect()
}

fn reads() -> Vec<char> {
    read::<String>().chars().collect()
}

fn mapv<T, S, F: Fn(&T) -> S>(arr: &Vec<T>, f: F) -> Vec<S> {
    arr.iter().map(f).collect()
}

fn join<T: ToString>(arr: &[T], sep: &str) -> String {
    arr.iter()
        .map(|x| x.to_string())
        .collect::<Vec<String>>()
        .join(sep)
}