#1916. 差异

    ID: 1916 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>CTT赛事:contest1971来源:qoj.ac数据:公开样例枚举

差异

差异

题目描述

标题: 差异 - Problem - QOJ.ac

#10351. 差异

Statistics

The problem was used in the following contests:

对于一个集合 S, 我们可以把其中所有元素从小往大排序, 我们定义这个集合的差异值为排好序后, 相邻两个数的差的最大值

你有 Q 个差异值不超过 K 非负整数集合, 已知每个集合中最小元素为 0, 最大元素为 N+1

现在已知给出 1 到 N 每个元素在 Q 个集合中的出现次数对M取模的结果, 求在满足条件的情况下, Q 的最小值是多少, 无解请输出 -1

输入描述

第一行三个整数 N, K, M 接下来一行 N 个整数, 第 i 个整数表示第 i 个元素的出现次数对 M 取模的结果

输出描述

一行一个整数表示 Q 的最小值, 无解输出 -1

样例输入1

3 2 8
0 0 1

样例输出1

8

样例输入2

3 1 9
2 3 3

样例输出2

-1

数据范围

对于10%的数据, K=1

对于另外10%的数据, K=2 且 N=5

对于另外20%的数据, K=2 且 N≤50

对于另外15%的数据, 保证答案小于M, 且N≤50

对于另外25%的数据, N≤20

对于100%的数据, 1≤N≤500000,1≤K≤N,2≤M≤109

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2 8
0 0 1
8

样例 2

3 1 9
2 3 3
-1