DP に帰着する

接頭辞 \(A _ 1, \dots, A _ i\) に対する答えを \(\mathtt{dp}[i]\) とし、これを DP で計算します。

公式解説同様、\(A\) の \(\bmod K\) 累積和を \(S _ 0, S _ 1, \dots, S _ N\) と置きましょう。また、各 \(i \in [0, N]\) に対して、\(b_i = \# \left \{ j \in [0, i) \mid S _ j = S _ i \right \}\) とおきます。これは前計算してもよいですし、逐次計算もできます。これらを用いると、\(\mathtt{dp}\) の漸化式が次のように書けます。

\[ \mathtt{dp}[j + 1] = \max \left ( \mathtt{dp}[j], \max \left \{ \mathtt{dp}[i] - b_i + b_j \ \middle | \ 0 \le i \lt j, \ S _ i = S _ j \right \} \right) \]

DP を効率的に計算する

これの計算のためには、各 \(x \in [0, K]\) に対して \(\max\left\{ \mathtt{dp}[i] - f(i) \ \middle | \ S_i = x\right\}\) (実装例の Value::max) を追加で管理すればよいです。またこれさえ管理すればもう \(\mathtt{dp}\) 本体は明示的に管理せず、現在の値 \(\mathtt{dp}[i]\) (実装例の ans) だけを管理すればよくなります。

実装例:

短いですね。

Rust 19 ms

use proconio::input;
use std::collections::HashMap;

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
    }
    let mut hist = HashMap::new();
    hist.insert(0, Value { count: 1, max: 0 });
    let mut sum = 0;
    let mut ans = 0;
    for &a in &a {
        sum = (sum + a) % k;
        let e = hist.entry(sum).or_insert_with(Value::default);
        ans = ans.max(e.count + e.max);
        e.max = e.max.max(ans - e.count);
        e.count += 1;
    }
    println!("{ans}");
}

#[derive(Default)]
struct Value {
    count: usize,
    max: usize,
}