https://atcoder.jp/contests/arc169/tasks/arc169_b

問題

解法1: double counting

$f(x)$ を計算する際には、左から貪欲に分解していくとする。

$g(l, r) = A_l, \ldots A_r$ を「どの連続部分列についても要素の総和が $S$ 以下になる」ように左から貪欲に連続部分列を分解し、$(A_l = A_{k_1}, \ldots, A_{k_2}),\ldots, (A_{k_p}, \ldots, A_{k_{p+1}} = A_r)$ と分解できたときの $(k_1, \ldots, k_p)$ とする（分解した連続部分列の左端の添字の列）。

$f(A_l, A_r) = |g(l,r)|$ である。

$k$ を1つ固定したとき、$g(l,r)$ に $k$ が現れるような $(l, r)$ の数が答えになる。(double counting)

($g(l, r)$ に $k$ が現れるというのは、貪欲に連続部分列を分解したときに、$k$ 番目から始まる分解があるということ）

• $l$ を 固定したとき、$r$ は $n-k$ 通り ($l$ に依存しない)

• r を固定したとき、$l$ は何通り取れる？

  • 木 DP みたいなことをすると求められる
  • $g(l, 0)$ を各 $l$ で求めて、$k$ を使うのがいくつあるかを求める感じ。愚直にやると時間が掛かるので、DAG 上の DP みたいなことをする。

• 古いメモ

解法2: DP

$r$ の DP はあまりうまくいかなそう（区切りを左から貪欲に入れる場合）