AtCoder Beginner Contest 461 D

https://atcoder.jp/contests/abc461/tasks/abc461_d

何行目から何行目かを固定して、何列目から何列目まででKになるパターンを数えます。全部0以上なので、尺取り法的に数えられて、計算量はでなんとか間に合います。
ただし、K=0のときうまくいかないので、単にその幅で全部0になる列の並びを見つければよいです。

// Count Subgrid Sum = K
#![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_input() -> (i32, Vec<String>) {
    let v: Vec<usize> = read_vec();
    let (H, K) = (v[0], v[2] as i32);
    let S: Vec<String> = (0..H).map(|_| read()).collect();
    (K, S)
}

fn create_table(S: Vec<String>) -> Vec<Vec<i32>> {
    S.into_iter().map(|s| s.chars().
                            map(|c| (c == '1') as i32).collect()).
                    collect::<Vec<Vec<i32>>>()
}

fn accumulate_2D(table: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let H = table.len();
    let W = table[0].len();
    let mut acc: Vec<Vec<i32>> = vec![vec![0; W+1]; H+1];
    for i in 1..H+1 {
        for j in 1..W+1 {
            acc[i][j] = acc[i][j-1] + acc[i-1][j] - acc[i-1][j-1]
                                                 + table[i-1][j-1]
        }
    }
    acc
}

fn groupby(v: &Vec<i32>) -> Vec<(i32, usize)> {
    let mut w: Vec<(i32, usize)> = vec![];
    let mut n: usize = 0;
    let mut prev: i32 = -1;
    for &e in v.iter() {
        if e != prev && n != 0 {
            w.push((prev, n));
            n = 0
        }
        prev = e;
        n += 1
    }
    w.push((prev, n));
    w
}

fn F_each(i1: usize, i2: usize, K: i32, table: &Vec<Vec<i32>>) -> usize {
    let L = table[0].len();
    let acc: Vec<i32> = (0..L).map(|j| table[i2][j] - table[i1][j]).collect();
    let g = groupby(&acc);
    let mut counter: usize = 0;
    let mut j: usize = 0;
    let mut k: usize = 1;
    while k < g.len() {
        let (e1, n1) = g[j];
        let (e2, n2) = g[k];
        if e2 - e1 == K {
            if j == k {
                counter += n1 * (n1 + 1) / 2
            }
            else {
                counter += n1 * n2
            }
            j += 1;
            k += 1
        }
        else if e2 - e1 > K {
            j += 1
        }
        else {
            k += 1
        }
    }
    counter
}

fn F_each0(acc: &Vec<i32>) -> usize {
    let g = groupby(&acc);
    g.into_iter().filter(|&(e, _)| e == 0).
                    map(|(_, n)| n*(n+1)/2).sum::<usize>()
}

fn F0(table: Vec<Vec<i32>>) -> usize {
    let mut counter: usize = 0;
    let H = table.len();
    let W = table[0].len();
    for i1 in 0..H {
        let mut acc: Vec<i32> = vec![0; W];
        for i2 in i1..H {
            for j in 0..W {
                acc[j] |= table[i2][j]
            }
            counter += F_each0(&acc)
        }
    }
    counter
}

fn F(K: i32, S: Vec<String>) -> usize {
    let H = S.len();
    let table = create_table(S);
    if K == 0 {
        return F0(table)
    }
    
    let acc_table = accumulate_2D(table);
    let mut counter: usize = 0;
    for i1 in 0..H {
        for i2 in i1+1..H+1 {
            counter += F_each(i1, i2, K, &acc_table)
        }
    }
    counter
}

fn main() {
    let (K, S) = read_input();
    println!("{}", F(K, S))
}