AtCoder Beginner Contest 424 D

https://atcoder.jp/contests/abc424/tasks/abc424_d

1行ごとのDPにします。2進法で白に塗ったマスを1にします。それを状態として、値を白に塗った箇所の個数で、これを最小化します。

// Sum of Subarrays
#![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 ////////////////////

type Range = (usize, usize);

fn read_range() -> Range {
    let v: Vec<usize> = read_vec();
    (v[0]-1, v[1])
}

fn read_input() -> (Vec<i64>, usize) {
    let v: Vec<usize> = read_vec();
    let Q = v[1];
    let A: Vec<i64> = read_vec();
    (A, Q)
}

fn accumulate(A: &Vec<i64>, e: u32) -> Vec<i64> {
    let N = A.len();
    let mut acc: Vec<i64> = vec![0; N+1];
    for i in 0..N {
        acc[i+1] = acc[i] + A[i] * (i as i64).pow(e)
    }
    acc
}

fn F_each((L, R): Range, acc: &Vec<Vec<i64>>) -> i64 {
    -(acc[2][R] - acc[2][L])
    + ((L+R-1) as i64) * (acc[1][R] - acc[1][L])
    - (R as i64)*((L as i64)-1) * (acc[0][R] - acc[0][L])
}

fn F(A: Vec<i64>, Q: usize) {
    let acc: Vec<Vec<i64>> = (0..3).map(|e| accumulate(&A, e)).collect();
    for _ in 0..Q {
        let range = read_range();
        println!("{}", F_each(range, &acc))
    }
}

fn main() {
    let (A, Q) = read_input();
    F(A, Q)
}