Problem:


Score : 400 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i \leq 10^5

1 \leq B_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the maximum total reward that you can earn no later than M days from today.

Sample Input 1

3 4
4 3
4 1
2 2

Sample Output 1

5

You can earn the total reward of 5 by taking the jobs as follows:

Take and complete the first job today. You will earn the reward of 3 after four days from today.

Take and complete the third job tomorrow. You will earn the reward of 2 after two days from tomorrow, that is, after three days from today.

Sample Input 2

5 3
1 2
1 3
1 4
2 1
2 3

Sample Output 2

10

Sample Input 3

1 1
2 1

Sample Output 3

0



Sample input:
3 4
4 3
4 1
2 2


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict

N,M=map(int, sys.stdin.readline().split())

reward=defaultdict(lambda: []) 

hq=[]
for _ in range(N):
	a,b=map(int, sys.stdin.readline().split())
	reward[a].append(-1*b)


hq=[]
ans=0
for day in range(M-1,-1,-1):
	hq+=reward[M-day]
	heapify(hq)
	if hq:
		t=heappop(hq)
		ans+=t*-1

print ans

Submission status: Time Limit Exceeded

Solution code:
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, min(m, len(conf))):
  res = 0
  for i, c in enumerate(cc):
    if i + c[0] <= m:
      res = res + c[1]
  if res > maxres:
    maxres = res
print(maxres)

Submission status: Time Limit Exceeded

Solution code:
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = {}
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a in d1:
      d1[a].append(b)
    else:
      d1[a] = [b]
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 0
        d2[j] += 1
        if j > maxb:
          maxb = j
    else:
      if _len(d2) == 0:
        continue
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = 0
      else:
        maxb = _max(d2.keys())
    else:
      d2[maxb] -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from operator import itemgetter

n, m = map(int, input().split())

# A日後、報酬B
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

sum = 0
used = [False] * n
for i in range(1, m+1):
    # A <= iでBが最大となるjを探す(使用済み除く)
    max_b = 0
    use_j = None
    for j in range(n):
        # print('i:{}, j:{}'.format(i, j))
        if a[j] <= i:
            if not used[j]:
                if b[j] > max_b:
                    max_b = b[j]
                    use_j = j
    if not use_j == None:
        used[use_j] = True
        sum += max_b

print(sum)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
ct = [0] * (10 ** 4 + 1)
cc = 0
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      ct[j] += 1
      if j > maxb:
        maxb = j
    cc += len(d1[i])
  else:
    if cc == 0:
      continue
  result += maxb
  ct[maxb] -= 1
  cc -= 1
  if ct[maxb] == 0:
    if cc == 0:
      maxb = -1
    else:
      for j in range(maxb - 1, -1, -1):
        if ct[j] != 0:
          maxb = j
          break
print(result)

Submission status: Time Limit Exceeded

Solution code:
def work(l):
    l.sort(key=lambda x:x[1],reverse=True)
    salary = l.pop(0)
    return salary[1]

n,m = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(n)]

queue = []
ans = 0
i = 0
while i < m:
    i += 1
    for j in range(len(a)):
        if a[j][0] == i:
            queue.append(a[j])
    if len(queue)>0:
        ans += work(queue)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(N, M, AB):
    day2pay = {i: [0] for i in range(1, max([a for (a, b) in AB] + [M]) + 1)}
    for a, b in AB:
        for i in range(len(day2pay[a])):
            if (day2pay[a][i] <= b):
                day2pay[a].insert(i, b)
                break
    result = 0
    for m in range(1, M + 1):
        max_a = 1
        max_b = day2pay[max_a][0]
        for a in range(1, m + 1):
            if (day2pay[a][0] > max_b):
                max_a = a
                max_b = day2pay[a][0]
        result += max_b
        day2pay[max_a].pop(0)
        if (not (day2pay[max_a])):
            day2pay[max_a] += [0]
    return result


(N, M) = tuple([int(s) for s in input().split(' ')])
AB = [tuple([int(s) for s in input().split(' ')]) for _ in range(N)]
print(calc(N, M, AB))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
money = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x: x[1], reverse = True)

dic = {}
ans = 0
for s in money:
    if s[0] <= m:
        if s[0] not in dic:
            dic[s[0]] = s[1]
            ans += s[1]
        else:
            for i in range(1,m-s[0]+1):
                if s[0]+i not in dic:
                    dic[s[0]+i] = s[1]
                    ans += s[1]
                    break
    if len(dic) == m:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
money = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x: x[1], reverse = True)

dic = {}
ans = 0
for s in money:
    if s[0] <= m:
        if s[0] not in dic:
            dic[s[0]] = s[1]
            ans += s[1]
        else:
            for i in range(1,m-s[0]+1):
                if s[0]+i not in dic:
                    dic[s[0]+i] = s[1]
                    ans += s[1]
                    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
dic = {i:[] for i in range(1,M+1)}
for i in range(N):
  A, B = map(int, input().split())
  if A<=M:
    dic[A] += [B]
key = list(dic.keys())
key.sort()
ans = 0
ls = []
m = 0
for i in range(1,M+1):
  ls += dic[i]
  if ls:
    ans += max(ls)
    ls.remove(max(ls))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# initialize
n,m = list(map(int,input().split()))
hiyatoi = [list(map(int,input().split())) for index in range(n)]
hiyatoi = np.array(hiyatoi)
day = m
salary = 0

for index in range(day):
  # delete the job passed deadline
  date_judge_index = np.where(hiyatoi[:,0]==hiyatoi[:,0].max())[0]
  if hiyatoi[date_judge_index[0]][0] > day:
    hiyatoi[date_judge_index] = [0,0]
  #print("締切日"+str(day)+"後")
  #print(hiyatoi)
  # search max salary job
  max_salary_index = np.where(hiyatoi[:,1]==hiyatoi[:,1].max())[0]
  # the number of jobs > 1
  #print("給料が高い仕事"+str(max_salary_index))
  if len(max_salary_index) > 1:
    # select max salary & day job
    max_day_index = np.where(hiyatoi[max_salary_index,0]==hiyatoi[max_salary_index,0].max())[0]
    #print("給料が高い仕事"+str(max_salary_index[max_day_index]))
    #print("選んだ仕事"+str(hiyatoi[max_salary_index[max_day_index]][0]))
    # obtain the salary
    salary += hiyatoi[max_salary_index[max_day_index]][0][1]
    # delete the job
    hiyatoi[max_salary_index[max_day_index][0]] = [0,0]
  # the number of jobs == 1
  else:
    # obtain the salary
    salary += hiyatoi[max_salary_index][0][1]
    # delete the job
    hiyatoi[max_salary_index] = [0,0]
  day -= 1

print(salary)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(N):
  A, B = map(int, input().split())
  dic[A] += [B]
key = list(dic.keys())
key.sort()
ans = 0
for i in range(1,M+1):
  m = 0
  K = 0
  for k in key:
    if k>i:
      break
    if dic[k] and m<max(dic[k]):
      m = max(dic[k])
      K = k
      #print(m,K, i, k, ans)
  if m==0:
    continue
  ans += m
  dic[K].remove(m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
ans=0
A=[]
for i in range(N):
  a,b=map(int,input().split())
  if a<=M:
    d=[a,b]
    A.append(d)
ans=0
now=0
sortedA=sorted(A, key=lambda x: x[0])
#print("sortedA",sortedA)
after=[]
i=0
stop=0
while sortedA or i<M:
  i+=1
  #print("i",i)
  if len(sortedA)==0 and len(after)!=0:
    ans+=after[-1][1]
    after.pop(-1)
    #print("ans",ans,"after",after,"sortedA" ,sortedA)
  elif sortedA:
    while sortedA[0][0]==i:
      a=sortedA.pop(0)
      after.append(a)
      if len(sortedA)==0: break
    after.sort(key=lambda x:x[1])
    if after:
      ans+=after[-1][1]
      after.pop(-1)
    #print("ans",ans,"after",after,"sortedA" ,sortedA)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N_baito,M_days = map(int,input().split())
hosyuList = [[] for _ in range(M_days)]

for _ in range(N_baito):
    days,hosyu = map(int,input().split())
    if days <= M_days:
        hosyuList[days-1].append(hosyu)
        
workList = []
hosyu = 0
for day in range(M_days):
    workList.extend(hosyuList[day])
    workList.sort(reverse=True)
    if workList:
        hosyu += workList[0]
        del workList[0]
print(hosyu)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
w=[]
for i in range(n):
  w.append(list(map(int,input().split())))

w=sorted(w)
#print(w)

total=0
for i in range(m,-1,-1):
#  print("i:"+str(i))
  max=0
  max_j=0
  found=False
  for j in range(len(w)):
    if (m-i)<w[j][0]: #残り日数(m-i)よりも大きい
#      print("残り日数:"+str(m-i) + "　仕事日数:"+str(w[j][0]))
      break
    elif max < w[j][1]:
#      print("最大値:"+str(w[j][1]) + " 添え字:"+str(j))
      max=w[j][1]
      max_j=j
      found=True
#  print(str(max) + "の仕事をやる")
  total = total + max
  if found:
#    print(str(max_j)+"番目の仕事を削除")
    w.pop(max_j)
#    print(w)
      
      
print(total)

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    init_val = -1  # 問題によって変える

    def __init__(self, init_l):
        self.n = len(init_l)
        self.n0 = 2 ** (self.n - 1).bit_length()  # n以上で最小の2のべき乗
        self.l = [self.init_val] * 2 * self.n0  # 区間外の値を初期化
        for i in range(self.n):
            self.l[i + self.n0 - 1] = init_l[i]
        for i in range(self.n0 - 2, -1, -1):
            self.l[i] = self.func(self.l[2 * i + 1], self.l[2 * i + 2])

    # 問題によって変える
    def func(self, x, y):
        return max(x, y)

    def update(self, i, new):
        i += self.n0 - 1
        self.l[i] = new
        while i + 1:
            i = (i - 1) // 2
            self.l[i] = self.func(self.l[i * 2 + 1], self.l[i * 2 + 2])

    # Gets min between [a, b)
    def query(self, a, b):
        return self._query(a, b, 0, 0, self.n0)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.init_val
        if a <= l and r <= b:
            return self.l[k]
        vl = self._query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self._query(a, b, k * 2 + 2, (l + r) // 2, r)
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ba = []
for _ in range(n):
    a, b = map(int, input().split())
    ba.append([b, a])
ba.sort(reverse=True)
days = [x for x in range(m)]
ans = 0
s = SegTree(days)
for x in ba:
    a = x[1]
    b = x[0]
    lim = m - a
    if lim < 0:
        continue
    d = s.query(0, lim+1)
    if d >= 0:
        ans += b
        s.update(d, -1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
N_baito,M_days = map(int,input().split())
baitoList = np.array([list(map(int,input().split())) for i in range(N_baito)])
workList = []
hosyu = 0
for day in range(M_days+1):
    for baito in baitoList[baitoList[:,0]==day][:,1].tolist():
        heapq.heappush(workList,-1*baito)
    if workList:
        hosyu += heapq.heappop(workList)
print(-1*hosyu)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
_NM = input().split()

N = int(_NM[0])
M = int(_NM[1])

a = []
b = []

for _ in range(N):
  _ab = input().split()
  a.append(int(_ab[0]))
  b.append(int(_ab[1]))
  
#a = np.array(a)
#b = np.array(b)

_c = zip(a,b)
_c = sorted(_c, key=lambda x:(x[0],-x[1]))
a,b = zip(*_c)
a,b = np.array(list(a)), np.array(list(b))
#print(a,b)
ret = 0
for d in range(M+1):
  # dより小さいaを指定し，該当するようなbを抽出
  inds = np.where(a<=d)[0]
  if len(inds)<=0:
    continue
  b_extracted = b[inds]
  
  b_max = max(b_extracted)
  ret += b_max
  inds_max = np.where(b==b_max)[0] # <= npwhereの返す配列がおかしい．．．ので[0]が必要
  #print(inds_max[0],b_max)
  #print('before a and b:',a,b,)
  a = np.delete(a,inds_max[0])
  b = np.delete(b,inds_max[0])
  #print('after a and b:',a,b,)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  a, b = data[i]
  if a not in d1:
    d1[a] = []
  d1[a].append(b)
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
ans = 0
q = []

for i in range(m+1):
    tmp = reversed(jobs[:])
    for job in tmp:
        if job[0] <= i:
            heapq.heappush(q, -jobs.pop()[1])
        else:
            break
    if q:
        ans += -heapq.heappop(q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j in d2:
        d2[j] += 1
      else:
        d2[j] = 1
  if len(d2.keys()) == 0:
    continue
  maxb = max(d2.keys())
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
  else:
    d2[maxb] -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, m = map(int, input().split())
  d1 = {}
  for _ in range(n):
    a, b = map(int, input().split())
    if a not in d1:
      d1[a] = []
    d1[a].append(b)
  result = 0
  d2 = {}
  for i in range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 0
        d2[j] += 1
    else:
      if len(d2) == 0:
        continue
    maxb = max(d2.keys())
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(N)]
l.sort(reverse=True)
 
h=[]
ans=0
for i in range(1,M+1):
    while l and l[-1][0]==i:
        h.append(l.pop()[1])
    if h:
        ans+=max(h)
        h.pop(h.index(max(h)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
ans = 0
q = []
l = len(jobs)
for i in range(m+1):
    tmp = jobs[:]
    for j in range(1, l+1):
        job = tmp[-j]
        if job[0] <= i:
            heapq.heappush(q, -jobs.pop()[1])
            l -= 1
        else:
            break
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
ans = 0
q = []

for i in range(m+1):
    tmp = reversed(jobs[:])
    for job in tmp:
        if job[0] <= i:
            heapq.heappush(q, -jobs.pop()[1])
        else:
            break
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(x[0],x[1]))

b = []
for i in range(N):
  b.append([-a[i][1], a[i][0]])

from bisect import bisect_left, bisect_right
import heapq

ans = 0
h = []

for i in range(1,M+1):
  left = bisect_left(a,[i,0])
  right = bisect_right(a,[i,float('inf')])-1
  if right-left>=0:
    for i in range(left,right+1):
      heapq.heappush(h,b[i])
    x = heapq.heappop(h)
    ans += -x[0]
  else:
    if h:
      x = heapq.heappop(h)
      ans += -x[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from operator import itemgetter

args = input().split()

# バイトの件数
N = int(args[0])
# ゴールの日
M = int(args[1])

work_list = []
for i in range(N):
    work = input().split()
    key = int(work[0])
    value = int(work[1])
    if key <= M:
        work_list.append([key, value])

work_list = sorted(work_list)

current = M
money = 0
while current >= 0:
    lst = []
    for i in range(len(work_list)):
        if current + work_list[i][0] <= M:
            lst.append([work_list[i][0], work_list[i][1]])
        else:
            break

    if len(lst) > 0:
        lst = sorted(lst, key=itemgetter(1))
        lst.reverse()
        money += lst[0][1]
        work_list.remove([lst[0][0], lst[0][1]])
    current -= 1

print(money)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from operator import itemgetter

args = input().split()

# バイトの件数
N = int(args[0])
# ゴールの日
M = int(args[1])

work_list = {}
for i in range(N):
    work = input().split()
    key = int(work[0])
    value = int(work[1])
    if key in work_list:
        pass
    else:
        work_list[key] = []

    work_list[key].append(value)

current = M
money = 0
while current >= 0:
    lst = []
    for key in work_list.keys():
        if current + key <= M:
            work_list[key] = sorted(work_list[key])
            work_list[key].reverse()
            lst.append([work_list[key][0], key])

    lst = sorted(lst)
    lst.reverse()
    if len(lst) > 0:
        money += lst[0][0]
        del(work_list[lst[0][1]][0])
        if len(work_list[lst[0][1]]) == 0:
            del(work_list[lst[0][1]])
    current -= 1

print(money)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
l = []
for i in range(n):
    a,b=map(int,input().split())
    dic[a].append(b)
s = 0
t = [0]
for i in range(m):
    t += dic[i+1]
    if len(t) ==0 : M = 0
    else:
        M = max(t)
        s +=M
        t.remove(M)
print(s)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from operator import itemgetter

args = input().split()

# バイトの件数
N = int(args[0])
# ゴールの日
M = int(args[1])

work_list = []
for i in range(N):
    work = input().split()
    work_list.append(work)
#    if int(work[0]) > M:
#        pass
#    else:
#        work_list.append(work)

work_list = sorted(work_list, key=itemgetter(1))
work_list.reverse()

#print(work_list)
current = M
money = 0

while current >= 0:
    for i in range(len(work_list)):
        if current + int(work_list[i][0]) <= M:
            money += int(work_list[i][1])
            del(work_list[i])
            break

    current -= 1

print(money)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N_baito,M_days = map(int,input().split())
baitoList = np.array([list(map(int,input().split())) for i in range(N_baito)])
workList = []
hosyu = 0
for day in range(M_days+1):
    workList.extend(baitoList[baitoList[:,0]==day][:,1].tolist())
    workList.sort(reverse=True)
    if workList:
        hosyu += workList[0]
        del workList[0]
print(hosyu)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
 
 
 
n, m = map(int, input().split())
m_dict = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    m_dict[a] = m_dict[a] + [b]


job_que = []
    
    
total = 0
for j in range(1, m+1):
    for k in m_dict[j]:
        heapq.heappush(job_que, -k)
 
 
    if job_que:
        total -= heapq.heappop(job_que)
        
    
            
print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from queue import PriorityQueue
 
 

n, m = map(int, input().split())
m_dict = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    m_dict[a] = m_dict[a] + [b]
    

job_que = PriorityQueue()
    
    
total = 0
for j in range(1, m+1):
    for k in m_dict[j]:
        job_que.put(-k)
 
 
    if job_que:
        total -= job_que.get()
        
    
            
print(total)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, m = map(int, input().split())
  data = [[int(e) for e in input().split()] for _ in range(n)]
  d1 = {}
  for i in range(n):
    a, b = data[i]
    if a not in d1:
      d1[a] = []
    d1[a].append(b)
  result = 0
  d2 = {}
  for i in range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 0
        d2[j] += 1
    else:
      if len(d2) == 0:
        continue
    maxb = max(d2.keys())
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
    else:
      d2[maxb] -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  if data[i][0] in d1:
    d1[data[i][0]].append(data[i][1])
  else:
    d1[data[i][0]] = [data[i][1]]
result = 0
d2 = {}
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j in d2:
        d2[j] += 1
      else:
        d2[j] = 1
  else:
    if len(d2) == 0:
      continue
  maxb = max(d2.keys())
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
  else:
    d2[maxb] -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  a, b = data[i]
  if a not in d1:
    d1[a] = []
  d1[a].append(b)
result = 0
d2 = {}
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
  else:
    if len(d2) == 0:
      continue
  maxb = max(d2.keys())
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, m = map(int, input().split())
  data = [[int(e) for e in input().split()] for _ in range(n)]
  d1 = {}
  for i in range(n):
    a, b = data[i]
    if a not in d1:
      d1[a] = []
    d1[a].append(b)
  result = 0
  d2 = {}
  for i in range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 0
        d2[j] += 1
    else:
      if len(d2) == 0:
        continue
    maxb = max(d2.keys())
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, m = map(int, input().split())
  data = [[int(e) for e in input().split()] for _ in range(n)]
  d1 = {}
  for i in range(n):
    if data[i][0] in d1:
      d1[data[i][0]].append(data[i][1])
    else:
      d1[data[i][0]] = [data[i][1]]
  result = 0
  d2 = {}
  for i in range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j in d2:
          d2[j] += 1
        else:
          d2[j] = 1
    if len(d2.keys()) == 0:
      continue
    maxb = max(d2.keys())
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
data = [[int(e) for e in input().split()] for _ in range(n)]
d1 = {}
for i in range(n):
  if data[i][0] in d1:
    d1[data[i][0]].append(data[i][1])
  else:
    d1[data[i][0]] = [data[i][1]]
result = 0
d2 = {}
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j in d2:
        d2[j] += 1
      else:
        d2[j] = 1
  if len(d2.keys()) == 0:
    continue
  maxb = max(d2.keys())
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
  else:
    d2[maxb] -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(n)]
	unti = sorted(ab, key = lambda x:x[0])
	ab_sorted = sorted(unti, key =  lambda x:x[1])
	ans = 0
	for i  in range(1,m+1):
		for j in reversed(ab_sorted):
			if(j[0] <= i):
				ans += j[1]
				ab_sorted.remove(j)
				break
	print(ans)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
from collections import defaultdict
hist = defaultdict(int)
AB = [[0,0]]*N
for n in range(N):
    temp = list(map(int,input().split()))
    if temp[0] <= M:
        AB[n] = temp
        hist[temp[0]] = temp[0]-1
work_schedule = [0]*M
sorted_AB = sorted(AB,key=lambda x:(-x[1],x[0]))
for work in sorted_AB:
    while True:
        if hist[work[0]] >= M:
            break
        elif work_schedule[hist[work[0]]] == 0:
            work_schedule[hist[work[0]]]  = work[1]
            break
        elif  work_schedule[hist[work[0]]] != 0:
            hist[work[0]] += 1
print(sum(work_schedule))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
date = []
salary = []
for _ in range(N):
  a, b = map(int, input().split())
  date.append(a)
  salary.append(b)
sum_salary = 0
for i in range(1, M+1):
  max_salary = 0
  index = -1
  for j in range(len(date)):
      if date[j] <= i:
        if max_salary < salary[j]:
          max_salary = salary[j]
          index = j
  sum_salary += max_salary
  if index >= 0:
    date.pop(index)
    salary.pop(index)
print(sum_salary)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
l=[[0,0] for _ in range(n)]
for i in range(n):
        l[i][1],l[i][0]=map(int,input().split())
l.sort()
l=l[::-1]
ans=0
for k in range(1,m+1):
        for j in range(len(l)):
                if l[j][1]<=k:
                        ans+=l[j][0]
                        del l[j]
                        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as ddict
from heapq import merge
from sys import stdin


def main():
    input = stdin.readline

    n, m = map(int, input().split())

    jobs = ddict(list)
    for _ in range(n):
        a, b = map(int, input().split())
        jobs[a-1].append(b)

    s_jobs = list()
    result = 0
    for d in range(m):
        s_jobs = list(merge(s_jobs, sorted(jobs[d])))
        try:
            result += s_jobs.pop()
        except IndexError:
            pass

    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m = map(int,input().split())
dic = {}

for i in range(n):
  a,b = map(int,input().split())
  if a in dic:
    pass
  else:
    dic[a] = []
  
  dic[a].append(b)
  
dic = dict(sorted(dic.items(),key=lambda x: -x[0]))

count = 0

lst = []
for i in range(1,m+1):
  if i in dic.keys():
    lst.extend(dic[i])
    lst = sorted(lst, reverse=True)

  if len(lst) != 0:
    count += lst.pop(0)
  

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m = [int(s) for s in input().split()]
j = []
for i in range(n):
    ai,bi = [int(s) for s in input().split()]
    j.append([ai,bi])

j = sorted(j, key=lambda x: (-x[1], x[0]))

r = 0
fl = []

for i in range(m):
    for x in range(n):
        if j[x][0] <= i+1 and x not in fl:
            r += j[x][1]
            fl.append(x)
            break

print(r)