AT_abc159_f [ABC159F] Knapsack for All Segments

[problemUrl]: https://atcoder.jp/contests/abc159/tasks/abc159_f 長さ $ N $ の整数列 $ A_1 $, $ A_2 $, $ \ldots $, $ A_N $ と正の整数 $ S $ が与えられます。 $ 1\leq\ L\ \leq\ R\ \leq\ N $ をみたす整数 $ (L,\ R) $ の組について、$ f(L,\ R) $ を以下のように定めます。 - $ L\ \leq\ x_1\

N/A

N/A

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ N\ \leq\ 3000 $ - $ 1\ \leq\ S\ \leq\ 3000 $ - $ 1\ \leq\ A_i\ \leq\ 3000 $ ### Sample Explanation 1 それぞれ以下のように計算できて、その和は $ 5 $ です。 - $ f(1,1)\ =\ 0 $ - $ f(1,2)\ =\ 1 $ ($ (1,\ 2) $ の $ 1 $ つ) - $ f(1,3)\ =\ 2 $ ($ (1,\ 2) $ と $ (3) $ の $ 2 $ つ) - $ f(2,2)\ =\ 0 $ - $ f(2,3)\ =\ 1 $ ($ (3) $ の $ 1 $ つ) - $ f(3,3)\ =\ 1 $ ($ (3) $ の $ 1 $ つ)