Submission #1191164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191164		jacobdoesntcode	Job Scheduling (CEOI12_jobs)	Pypy 3	0 / 100	222 ms	131072 KiB

jobs

import math
import bisect
n, d, m = map(int, input().split())
requests = list(map(int, input().split()))
requests_dict = {}
requests_sum = [0] * n
for i in range(m):
    if requests[i] in requests_dict.keys():
        requests_dict[requests[i]].append(str(i + 1))
    else:
        requests_dict[requests[i]].append(str(i + 1))
    requests_sum[requests[i] - 1] += 1
min_machine = 1
extra = 0
for i in range(n):
    if i < d - 1:
        if requests_sum[0] > 0:
            requests_sum[0] -= min_machine
        else:
            extra += min_machine
    else:
        if extra > requests_sum[i - d]:
            extra -= requests_sum[i - d]
            requests_sum[i - d] = 0
        else:
            temp = requests_sum[i - d]
            requests_sum[i - d] -= extra
            extra = 0
        
        if requests_sum[i - d] > min_machine:
            orig = requests[i - d] + min_machine * d
            min_machine = math.ceil(orig / d)
            requests[i - d] = 0
            extra += min_machine * d - orig
        else:
            extra += min_machine - requests_sum[i - d]
            requests_sum[i - d] = 0

print(min_machine)

#to_print = []
#for i in range(1, n + 1):
#    if i in requests_dict.keys():
#        to_print.extend(requests_dict[i])
#    
#    if i in requests_dict.keys():
#        if len(requests_dict[i]) > (2 * d - 1):
#            print(requests_dict[i][: 2 * d - 1] + ' 0')
#            leftover += requests_dict[i][2 * d + 1:]
#        elif len(requests_dict[i]) == (2 * d - 1):
#            print(requests_dict[i] + ' 0')
#        else:
#            print(requests_dict[i] + leftover[: 2 * d - 1 - len(requests_dict[i])] + ' 0')
#            leftover = leftover[2 * d + 1:]
#    else:
#        if len(leftover) > 0:
#            print(leftover[: 2 * d - 1] + ' 0')
#            leftover = leftover[2 * d + 1:]
#        else:
#            print('0')

Compilation message (stdout)

Compiling 'jobs.py'...

=======
  adding: __main__.pyc (deflated 36%)

=======

• Subtask 1: 0 / 100