Problem: There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.  You can take and complete at most one of these jobs in a day.  However, you cannot retake a job that you have already done.  Find the maximum total reward that you can earn no later than M days from today.  You can already start working today.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10 ** 6)

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i in range(cand_len):
    if candidates[i][0] > maxval:
      maxval = candidates[i][0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
print(ans)


import itertools

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conf = [[int(x) for x in input().split()] for _ in range(n)]
# conf = sorted([[int(x) for x in input().split()] for _ in range(n)], reverse=True)

maxres = 0
for cc in itertools.permutations(conf, m):
  res = 0
  for i, c in enumerate(cc):
    if i + c[0] <= m:
      res = res + c[1]
  if res > maxres:
    maxres = res
print(maxres)

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

print(conditions)

ans = 0
candidates = []
for reversed_day in range(1, m+1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i in range(cand_len):
    if candidates[i][0] > maxval:
      maxval = candidates[i][0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
print(ans)

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m+1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i in range(cand_len):
    if candidates[i][0] > maxval:
      maxval = candidates[i][0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
print(ans)



import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  for i, cond in enumerate(conditions):
    if cond[0] > reversed_day:
      break
    tmp = conditions.pop(i)
    heapq.heappush(candidates, -tmp[1])

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

print(ans)



import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

print(ans)

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted