AT_arc043_d [ARC043D] 引っ越し

[problemUrl]: https://atcoder.jp/contests/arc043/tasks/arc043_d 高橋国には $ N $ 個の空き家がある。空き家は $ 1 $ から $ N $ の整数で番号付けされており、順に東西に一直線に $ 1 $ キロメートル間隔で並んでいる。 つまり $ i $ 番目の空き家は ある基準点から真東に $ i $ キロメートル進んだところにある。 この国に $ M $ 世帯の家族が引っ越してきた。 $ i $ 番目の家族は $ P_i $ 人家族である。 この $ M $ 世帯の家族に $ 1 $ 軒ずつ空き家を振り分けていく。このとき複数の家族に同じ家を振り分けてはならない。 あなたの目標は「住民の距離」を最大化するように空き家を振り分けることである。 「住民の距離」とは引っ越してきた人々の中の全ての $ 2 $ 人組について、その住んでいる家の距離の総和を取った値である。 最適な振り分け方をしたときの「住民の距離」の最大値を求めよ。

入力は以下の形式で標準入力から与えられる > $ N $ $ M $ $ P_1 $ $ P_2 $ : $ P_M $ - $ 1 $ 行目には高橋国にある空き家の個数を表す整数 $ N(2\ ≦\ N\ ≦\ 10^6) $ と 高橋国に引っ越してくる家族の世帯数 $ M(2\ ≦\ M\ ≦\ min(N,\ 1,000)) $ が空白区切りで与えられる。 - $ 2 $ 行目からの $ M $ 行のうち $ i $ 行目には $ i $ 番目の家族を構成する人数 $ P_i(1\ ≦\ P_i\ ≦\ 100) $ が与えられる。

「住民の距離」の最大値を $ 1 $ 行に出力せよ。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 2\ ≦\ N\ ≦\ 10 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - $ 2\ ≦\ N\ ≦\ 10^6 $を満たすデータセットに正解した場合はさらに $ 90 $ 点が与えられる。合計で $ 100 $ 点となる。 ### Sample Explanation 1 $ 1 $ つめの家族の構成をAさん。$ 2 $ つめの家族の構成をBさん。$ 3 $ つめの家族の構成をCさん、Dさんとする。 $ 1 $ つめの家族を $ 1 $ 番目の空き家、 $ 2 $ つめの家族を $ 2 $ 番目の空き家、$ 3 $ つめの家族を $ 4 $ 番目の空き家に振り分けると、各二人組の距離は以下のようになる。 - AさんとBさんの距離： $ 1 $ - AさんとCさんの距離： $ 3 $ - AさんとDさんの距離： $ 3 $ - BさんとCさんの距離： $ 2 $ - BさんとDさんの距離： $ 2 $ - CさんとDさんの距離： $ 0 $ よって合計は $ 11 $ となる。これが「住民の距離」の最大値である。