AtCoder Beginner Contest 265 D

https://atcoder.jp/contests/abc265/tasks/abc265_d

各解はしゃくとり法で求められるので、その解をたどっていきます。

// Iroha and Haiku (New ABC Edition)
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// 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()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


//////////////////// process ////////////////////

fn read_input() -> (Vec<i64>, Vec<i64>) {
    let v = read_vec();
    let P: i64 = v[1];
    let Q: i64 = v[2];
    let R: i64 = v[3];
    let A: Vec<i64> = read_vec();
    (vec![P, Q, R], A)
}

fn accumulate(A: Vec<i64>) -> Vec<i64> {
    let mut B: Vec<i64> = Vec::new();
    B.push(0);
    let mut acc = 0;
    for a in A.into_iter() {
        acc += a;
        B.push(acc)
    }
    B
}

fn solve_each(S: i64, B: &Vec<i64>) -> Vec<(usize, usize)> {
    let mut kls: Vec<(usize, usize)> = Vec::new();
    let N = B.len();
    let mut k: usize = 0;
    let mut l: usize = 1;
    while l < N {
        if S == B[l] - B[k] {
            kls.push((k, l));
            k += 1;
            l += 1
        }
        else if S > B[l] - B[k] {
            l += 1
        }
        else {
            k += 1
        }
    }
    kls
}

fn walk(vs0: Vec<usize>, i: usize, v: Vec<i64>, B: Vec<i64>) -> bool {
    if i == v.len() {
        return !vs0.is_empty()
    }
    
    let mut vs : Vec<usize> = Vec::new();
    let range = solve_each(v[i], &B);
    let dic: HashMap<usize, usize> = range.iter().map(|&v| v).collect();
    for v0 in vs0.iter() {
        match dic.get(v0) {
            Some(v1) => vs.push(*v1),
            None     => ()
        }
    }
    walk(vs, i + 1, v, B)
}

fn f(v: Vec<i64>, A: Vec<i64>) -> bool {
    let B = accumulate(A);
    let vs0: Vec<usize> = (0..B.len()).collect();
    walk(vs0, 0, v, B)
}

fn main() {
    let (v, A) = read_input();
    println!("{}", YesNo(f(v, A)))
}