Submission #18756488

---

Source Code Expand

N, M = map(int, input().split())

A = list(map(int, input().split()))
if M == 0:
    print(1)
    exit()
A.sort()
B = [0] * (M + 1)

mn = 10 ** 10
mx = 0
B[0] = A[0] - 1
if B[0] > 0:
    mn = min(B[0], mn)
    mx = max(mx, B[0])
for i in range(M - 1):
    B[i + 1] = A[i + 1] - A[i] - 1
    if  B[i + 1] > 0:
        mn = min(B[i + 1], mn)
        mx = max(mx, B[i + 1])
B[-1] = N - A[-1]
if B[-1] > 0:
    mn = min(B[-1], mn)
    mx = max(mx, B[-1])


def calc(K):
    res = 0
    for i in B:
        if i:
            if K > i:
                return -1
            res += (i + K - 1) // K
    return res


ans = N

if mn == 10 ** 10 and mx == 0:
    print(0)
    exit()

for i in range(mn, mx + 1):
    count = calc(i)
    if count >= 1:
        ans = min(ans, count)

print(ans)

Submission Info

Judge Result