AT_abc370_f [ABC370F] Cake Division

[problemUrl]: https://atcoder.jp/contests/abc370/tasks/abc370_f 円形のケーキがあり、ケーキは切り目によって $ N $ 個のピースに分けられています。各切り目は円の中心と円弧上の点を結ぶ線分です。 ピースおよび切り目には時計回りに $ 1,\ 2,\ \ldots,\ N $ の番号が付けられており、ピース $ i $ の質量は $ A_i $ です。ピース $ 1 $ をピース $ N\ +\ 1 $ とも呼ぶこととします。 切り目 $ i $ は ピース $ i $ とピース $ i\ +\ 1 $ の間にあり、ピース $ 1 $, 切り目 $ 1 $, ピース $ 2 $, 切り目 $ 2 $, $ \ldots $, ピース $ N $, 切り目 $ N $ の順に時計回りに並んでいます。 このケーキを以下の条件を満たすように $ K $ 人に分けようとしています。ただし、$ i $ 番目の人が受け取るピースの質量の合計を $ w_i $ とします。 - すべての人が $ 1 $ つ以上の**連続する**ピースを受け取る - 誰も受け取らないピースは存在しない - 上の $ 2 $ つの条件を満たすという条件下で $ \min(w_1,\ w_2,\ \ldots,\ w_K) $ が最大になるようにする 条件を満たす分け方における $ \min(w_1,\ w_2,\ \ldots,\ w_K) $ の値および条件を満たすすべての分け方で切られることのない切り目の個数を求めてください。ただし、切り目 $ i $ が切られるとは、ピース $ i $ とピース $ i\ +\ 1 $ が異なる人に分けられることを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

条件を満たす分け方における $ \min(w_1,\ w_2,\ \ldots,\ w_K) $ の値を $ x $、 切られることのない切り目の個数を $ y $ として、$ x $ と $ y $ をこの順に空白区切りで出力せよ。

### 制約 - $ 2\ \leq\ K\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^4 $ - 入力される値はすべて整数 ### Sample Explanation 1 以下の分け方が条件を満たします。 - 一方の人にピース $ 2,\ 3 $ を渡し、もう一方の人にピース $ 4,\ 5,\ 1 $ を渡す。ピース $ 2,\ 3 $ の質量の合計は $ 14 $、ピース $ 4,\ 5,\ 1 $ の質量の合計は $ 13 $ である。 - 一方の人にピース $ 3,\ 4 $ を渡し、もう一方の人にピース $ 5,\ 1,\ 2 $ を渡す。ピース $ 3,\ 4 $ の質量の合計は $ 14 $、ピース $ 5,\ 1,\ 2 $ の質量の合計は $ 13 $ である。 条件を満たす分け方における $ \min(w_1,\ w_2) $ の値は $ 13 $ であり、どちらの分け方でも切られない切り目は切り目 $ 5 $ の $ 1 $ つです。