Submission #446921

#	Time	Username	Problem	Language	Result	Execution time	Memory
446921		ntarsis	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	368 ms	65540 KiB

jobs

n,d,m = map(int,input().split())
nums = [int(x) for x in input().split()]
nums.sort()
def check(x):
    thing = [0]*m
    count = 1
    curr = 0
    right = 0
    while right < m:
        while right < min(m,curr+x):
            if nums[right]<=count:
                thing[right]=count
                right+=1
            else:
                curr = right
                count+=1
        count+=1
        curr+=x
    final = 0
    for i in range(m):
        final = max(final,thing[i]-nums[i])
    return final <= d

lo = 0
hi = m
while lo < hi:
    mid = (lo+hi)//2
    if check(mid):
        hi = mid
    else:
        lo = mid+1
print(lo)

• Subtask 1: 0 / 100