AtCoder Beginner Contest 456 F

https://atcoder.jp/contests/abc456/tasks/abc456_f

1日飛ばしでもいいという問題です。これが毎日コストをかけるということなら、ウィンドウ幅を一定にしてスライドしていけばいいのですが、1日飛ばしだとうまくいきません。コストを払うときと払わないときでoとxで表すと、最初がoかxで分けてそれぞれでそこまでの和の最小を求めます。長さがKを超えてくると前を移動しなければなりませんが、そのときも最初がoかxの両方を求める必要があります。しかし、情報は最初がoかxかとそこまでの最小の和で次がoかxかの情報はないので、これは無理です。
最初が固定されていればこの問題は回避できます。なので、ある場所から両側に伸びればよいです。領域があったらそれを半分にして、半分の領域それぞれと、真ん中から両側に伸びて合わせてKかK+1の長さになるもので最小のものをその領域内の最小コストとします。
これは455Eとそっくりです。
https://inamori.hateblo.jp/entry/2026/04/28/212010

// Plan Holidays
#![allow(non_snake_case)]


//////////////////// 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_case() -> (usize, Vec<i64>) {
    let v: Vec<usize> = read_vec();
    let K = v[1];
    let A: Vec<i64> = read_vec();
    (K, A)
}

use std::cmp::min;

fn collect_min(A: &Vec<i64>, K: usize) -> (Vec<i64>, Vec<i64>) {
    let L = min(A.len()+1, K+2);
    let mut v1: Vec<i64> = vec![0; L];  // 最初がo
    let mut v2: Vec<i64> = vec![0; L];  // 最初がx
    v1[1] = A[0];
    v2[1] = i64::MAX/2;
    if L == 2 {
        return (v1, v2)
    }
    
    v1[2] = A[0] + A[1];
    v2[2] = A[1];
    for i in 3..L {
        v1[i] = min(v1[i-2], v1[i-1]) + A[i-1];
        v2[i] = min(v2[i-2], v2[i-1]) + A[i-1]
    }
    (v1, v2)
}

fn F_each(K: usize, A: Vec<i64>) -> i64 {
    if A.len() == 1 && K == 1 {
        return A[0]
    }
    else if A.len() < K {
        return i64::MAX
    }
    
    let L = A.len();
    let mid = L / 2;
    let A1 = A[..mid].iter().rev().cloned().collect::<Vec<_>>();
    let A2 = A[mid..].to_vec();
    let (v11, v12) = collect_min(&A1, K);
    let (v21, v22) = collect_min(&A2, K);
    let mut min_value = i64::MAX;
    for d in 0..2 {
        for i in 1..K+d {
            if i < v11.len() && K+d-i < v21.len() {
                min_value = min(min_value, v11[i] + v21[K+d-i])
            }
            if i < v11.len() && K+d-i < v22.len() {
                min_value = min(min_value, v11[i] + v22[K+d-i])
            }
            if i < v12.len() && K+d-i < v21.len() {
                min_value = min(min_value, v12[i] + v21[K+d-i])
            }
        }
    }
    min_value = min(min_value, F_each(K, A1));
    min_value = min(min_value, F_each(K, A2));
    min_value
}

fn F(T: usize) {
    for _ in 0..T {
        let (K, A) = read_case();
        println!("{}", F_each(K, A))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}