AtCoder Beginner Contest 281 D

https://atcoder.jp/contests/abc281/tasks/abc281_d

キーが個数と和のDの剰余、値を和の最大値とするDPですね。

// All Assign Point Add
#![allow(non_snake_case)]

use std::collections::HashMap;

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

fn f(K: usize, D: usize, A: Vec<usize>) -> i64 {
    let mut dic = HashMap::<(usize, usize), usize>::new();
    dic.insert((0, 0), 0);
    for a in A.into_iter() {
        let mut new_dic = dic.iter().map(|((r, n), &m)| ((*r, *n), m)).
                            collect::<HashMap<(usize, usize), usize>>();
        for ((n, r), &max_value) in dic.iter() {
            let key = (n + 1, (r + a) % D);
            match new_dic.get(&key) {
                Some(&v) => if max_value + a > v {
                                    new_dic.insert(key, max_value + a); },
                None     => { new_dic.insert(key, max_value + a); }
            }
        }
        dic = new_dic
    }
    
    match dic.get(&(K, 0)) {
        Some(&v) => v as i64,
        None     => -1
    }
}

fn main() {
    let v = read_input();
    println!("{}", f(v.0, v.1, v.2))
}