← 返回题目列表

AtCoder · arc043_d

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 第th个家庭的人数 P_i(1 ≦ P_i ≦ 100) 给出。

部分点

针对此问题设置了部分分数。 如果正确答案是满足

  • 2 ≦ N ≦ 10 的数据集 给出 10 点。 如果正确答案是满足
  • 2 ≦ N ≦ 10^6的数据集,则进一步 给出 90 点。总共 100 点。

出力

将“驻留距离”的最大值设置为 在 1 行上输出。 在输出末尾插入换行符。


入力例1

4 3
1
1
2

出力例1

11

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 变为。这是“居民之间的距离”的最大值。


入力例2

10 10
3
1
4
1
5
9
2
6
5
3

出力例2

2998

入力例3

20 10
2
7
1
8
2
8
1
8
2
8

出力例2

9852