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:
from collections import defaultdict as dd
from collections import deque

n,m=map(int,input().split())
dic=dd(list)
for i in range(n):
    a,b=map(int,input().split())
    dic[m-a].append(b)

for k,v in dic.items():
    dic[k]=deque(sorted(dic[k],reverse=True))

#print(dic)

ans=0
for i in range(m):
    tv=0
    j=i
    tk=-1
    while i<=j<=m:
        if len(dic[j])==0: j+=1; continue;
        if tv<dic[j][0]:
            tv=dic[j][0]
            tk=j
        j+=1
    if tk!=-1:
        dic[tk].popleft()
        ans+=tv

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    ans = 0
    d = defaultdict(list)
    for _ in range(N):
        A, B = map(int, input().split())
        d[A].append(-B)
    cand = []
    heapq.heapify(cand)
    for day in range(M-1,-1,-1):
        diff = M - day
        if d[diff]:
            cand += d[diff]
            heapq.heapify(cand)
        if cand:
            ans -= heapq.heappop(cand)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    ans = 0
    d = defaultdict(list)
    for _ in range(N):
        A, B = map(int, input().split())
        d[A].append(-B)
    cand = []
    heapq.heapify(cand)
    for day in range(M-1,-1,-1):
        diff = M - day
        if d[diff]:
            cand += d[diff]
        heapq.heapify(cand)
        if cand:
            ans -= heapq.heappop(cand)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])[::-1]
plan = [0] * (M+1)
ans = 0
for a, b in AB:
    i = a
    while i < (M+1) and plan[i] == 1:
        i += 1
    if i < (M+1):
        plan[i] = 1
        ans += b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n, m = map(int, input().split( ))
arr = {}
for _ in range(n):
  a, b = map(int, input().split( ))
  if a > m:
    continue
  if a in arr:
    arr[a].append(b)
  else:
    arr[a] = [b]
#arr_sorted = sorted(arr.items(), key=lambda x:x[0])
#print(arr_sorted)
ans = 0
am = []
mam = -1
for i in range(1, m+1):
  if i in arr:
    am.extend(arr[i])
  if am != []:
    ans += max(am)
    am.remove(max(am))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, ABs):
    ans = 0
    schedule = [0] * M
    max_start_day = [M - i for i in range(M + 1)]
    ABs.sort(key=lambda x: x[1], reverse=True)
    for A, B in ABs:
        if A > M:
            continue
        work_day = max_start_day[A]
        if work_day < 0:
            continue
        flg = False
        while schedule[work_day] != 0:
            work_day -= 1
            if work_day < 0:
                flg = True
                break
        if flg:
            max_start_day[A] = work_day
            continue
        ans += B
        schedule[work_day] = B
        max_start_day[A] = work_day - 1
    print(ans)


if __name__ == '__main__':
    N, M = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]

    # from random import randint
    # N, M = 10 ** 5, 10 ** 5
    # ABs = [[randint(1, 10 ** 5), randint(1, 10 ** 4)] for _ in range(10 ** 5)]

    solve(N, M, ABs)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
ABlist = []
for i in range(10**5+1):
    ABlist.append([])
for i in range(N):
    A,B = map(int,input().split())
    ABlist[A].append(-B)
Bite = []
heapq.heapify(Bite)
Answer = 0
for j in range(1,M+1):
    Bite = Bite + ABlist[j]
    heapq.heapify(Bite)
    if Bite != []:
        Answer += heapq.heappop(Bite)
print(-Answer)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
ABlist = []
for i in range(10**5+1):
    ABlist.append([0])
for i in range(N):
    A,B = map(int,input().split())
    ABlist[A].append(-B)
Bite = []
heapq.heapify(Bite)
Answer = 0
for j in range(1,M+1):
    Bite = Bite + ABlist[j] 
    heapq.heapify(Bite)
    Answer += heapq.heappop(Bite)
print(-Answer)

Submission status: Time Limit Exceeded

Solution code:
#解説の方法
N,M = map(int,input().split())
AB = [[] for _ in range(10**5+1)]#報酬振り込み日数ごとに報酬を格納
for _ in range(N):
    a,b = map(int,input().split())
    AB[a].append(b)
q = []
ans =0
for i in range(1,M+1):
    q += AB[i]#後ろから見るイメージ　残りi日で請けれる仕事をリストに追加する
    if len(q)>0:
        q.sort()
        ans += q.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

max_SumA = (M*(M+1))//2
AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の数
noMore = float('inf') #これ以上の日数が振り込みにかかる仕事は受けれない
ans = 0
for a,b in AB:
    if a< noMore:
        flag = 1
        for idx in range(M-a,-1,-1):
            if memo[idx] == 0:#仕事が請けられる
                ans += b
                memo[idx]=1
                flag = 0
                break
        if flag ==1:
            noMore = a
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

max_SumA = (M*(M+1))//2
AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の数
ans = 0
for a,b in AB:
    for idx in range(M-a,-1,-1):
        if memo[idx] == 0:#仕事が請けられる
            ans += b
            memo[idx]=1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
q, z = [], 0
v = [q for _ in [None] * 10**5]
for a, b in t:
    v[a - 1] += b,
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    if q:
        z += -heappop(q)
print(z)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
q, z = [], 0
v = [q for _ in [0] * 10**5]
for a, b in t:
    v[a - 1] += b,
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    z += -heappop(q)
print(z)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
S = [[0] for _ in range(M)]
for _ in range(N):
    a, b = map(int, input().split())
    if M < a:
        continue
    heapq.heappush(S[M-a], -b)

ans = heapq.heappop(S[M-1])
for i in range(M-2, -1, -1):
    for num in S[i+1]:
        heapq.heappush(S[i], num)
    ans += heapq.heappop(S[i])
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

# import numpy as np
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now.append(b)
    #print(nouki, now)
    if now==[]:continue
    m=max(now)
    ans+= m
    now.remove(m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

import numpy as np
ans=0
now=np.array([], dtype="int64")
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now=np.append(now,b)
    #print(nouki, now)
    if now.size==0:continue
    m=np.max(now)
    ans+= m
    now= np.delete(now,np.argmax(now))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

import numpy as np
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now.append(b)
    #print(nouki, now)
    if now==[]:continue
    m=np.max(now)
    ans+= m
    now[np.argmax(now)]=0
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)


ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now.append(b)
    #print(nouki, now)
    if now==[]:continue
    m=max(now)
    ans+= m
    now.remove(m)
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())

works = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    heapq.heappush(works[A-1], -B)

total = 0
for i in range(1, M+1):
    max_m = 0
    for j in range(i):
        if len(works[j]) == 0:
            continue
        else:
            x = heapq.heappop(works[j])
            if -x > max_m:
                max_m = -x
            else:
                heapq.heappush(works[j], x)

    total += max_m

print(total)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

works = []
for _ in range(N):
    A, B = map(int, input().split())
    works.append((A, B))

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

total = 0
for m in range(1, M+1):
    for i in range(len(works)):
        if works[i][0] <= m:
            total += works.pop(i)[1]
            break

print(total)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

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

day = [[] for _ in range(10 ** 5)]
for a, b in ab:
    day[a - 1].append(-b)

work, ans = [], 0
for i in range(m):
    if day[i]:
        work+=day[i]
        heapify(work)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

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

day = [[] for _ in range(10 ** 5)]
for a, b in ab:
    day[a - 1].append(-b)

work, ans = [], 0
for i in range(m):
    work+=day[i]
    heapify(work)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d=[[] for _ in range(n)]
e=[1]*m
for i in range(n):
  a,b=map(int,input().split())
  d[i]=(b,a)
d=sorted(d)[::-1]
ans=0
for i,j in d:
  for k in range(j-1,m):
    if e[k]:
      e[k]=0
      break
  else:continue 
  ans+=i
print(ans)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    if a in d:
      d[a].append(b)
    else:
      d[a] = [b]
res = 0
ok = []
if len(d)>0:
  sta = min(d)
  for i in range(sta,M+1):
    if i in d:
      ok.extend(d[i])
    if len(ok)>0:
      ad = max(ok)
      res += ad
      ok.remove(ad)
  print(res)
else:
  print(0)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    if a in d:
      d[a].append(b)
    else:
      d[a] = [b]
res = 0
ok = []
if len(d)>0:
  sta = min(d)
else:
  sta = 0
for i in range(sta,M+1):
  if i in d:
    ok.extend(d[i])
  if len(ok)>0:
    ad = max(ok)
    res += ad
    ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {x:[0] for x in range(M+1)}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    d[a].append(b)
res = 0
ok = []
for i in range(M+1):
  ok.extend(d[i])
  ad = max(ok)
  res += ad
  ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    if a in d:
      d[a].append(b)
    else:
      d[a] = [b]
res = 0
ok = []
for i in range(M+1):
  if i in d:
    ok.extend(d[i])
  if len(ok)>0:
    ad = max(ok)
    res += ad
    ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {x:[0] for x in range(1,M+1)}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    d[a].append(b)
res = 0
ok = []
for i in range(1,M+1):
  ok.extend(d[i])
  ad = max(ok)
  res += ad
  ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = [[0] for i in range(M)]
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    d[a-1].append(b)
res = 0
ok = []
for i in d:
  ok.extend(i)
  ad = max(ok)
  res += ad
  ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    if a in d:
      d[a].append(b)
    else:
      d[a] = [b]
res = 0
ok = []
for i in range(M+1):
  if i in d:
    ok.extend(d[i])
  if len(ok)>0:
    ad = max(ok)
    res += ad
    ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

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

N,M = (int(x) for x in input().rstrip('\n').split())
d = {}
for _ in range(N):
  a,b = (int(x) for x in input().rstrip('\n').split())
  if a <= M:
    if a in d:
      d[a].append(b)
    else:
      d[a] = [b]
res = 0
ok = []
for i in range(1,M+1):
  if i in d:
    ok.extend(d[i])
  if len(ok)>0:  
    ad = max(ok)
    res += ad
    ok.remove(ad)
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB = []

for _ in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

AB.sort()
AB.sort(key = lambda x:x[1], reverse = True)

ans = [0]*(M+1)

for a, b in AB:
  while a <= M:
    if ans[a] < b:
      ans[a] = b
      break
    a += 1

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB = []
for i in range(N):
  tmp = list(map(int, input().split()))
  AB.append(tmp)
AB.sort()
#print(AB)

r = 0
for i in range(1,M+1):
  val_max, idx_max = 0, 0
  for j in range(N):
    if val_max < AB[j][1] and AB[j][0] <= i:
      val_max = AB[j][1]
      idx_max = j
  if val_max != 0:
    r += val_max
    AB[idx_max][0] = M+1
print(r)

Submission status: Time Limit Exceeded

Solution code:
import heapq


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n)]

    AB.sort(key=lambda x: x[0])
    H = []
    ans = 0
    mi = 1
    for a, b in AB:
        while a > mi:
            if len(H) > 0:
                heapq.heapify(H)
                ans += -heapq.heappop(H)

            mi += 1
            if mi > m:
                break

        if a > m:
            break

        H.append(-b)

    while mi <= m and len(H) > 0:
        heapq.heapify(H)
        ans += -heapq.heappop(H)
        mi += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n)]

    AB.sort(key=lambda x: x[0])

    H = []
    abi = 0
    ans = 0
    for mi in range(1, m + 1):
        while abi < n:
            a, b = AB[abi]
            if a == mi:
                abi += 1
                H.append(-b)
            else:
                break

        if len(H) > 0:
            heapq.heapify(H)
            ans += -heapq.heappop(H)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
for i in range(N):
  a, b = map(int, input().split())
  l.append([a, b])
l.sort()

ans = 0
for i in range(1, M+1):
  mx = 0
  index = 0
  for j in range(len(l)):
    if l[j][0]<=i:
      if mx<l[j][1]:
        mx = l[j][1]
        index = j
    else:
      break
  if mx != 0:
    ans += mx
    l.pop(index)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
for i in range(N):
  a, b = map(int, input().split())
  l.append([a, b])
l.sort()

ans = 0
for i in range(1, M+1):
  mx = 0
  index = 0
  for j in range(len(l)):
    if (l[j][0]<=i) and (mx<l[j][1]):
      mx = l[j][1]
      index = j
    elif l[j][0] > i:
      break
  if mx != 0:
    ans += mx
    l.pop(index)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
for i in range(N):
  a, b = map(int, input().split())
  l.append([a, b])
l.sort()

ans = 0
for i in range(1, M+1):
  mx = 0
  index = 0
  j = 0
  while l[j][0]<=i:
    if mx < l[j][1]:
      mx = l[j][1]
      index = j
    j += 1
    if j >= len(l):
      break;
  if mx != 0:
    ans += mx
    l.pop(index)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
l = []
for i in range(N):
  a, b = map(int, input().split())
  l.append([a, b])

ans = 0
for i in range(1, M+1):
  mx = 0
  index = 0
  for j in range(len(l)):
    if (l[j][0]<=i) and (mx<l[j][1]):
      mx = l[j][1]
      index = j
  if mx != 0:
    ans += mx
    l.pop(index)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()
AB = []
for _ in range(N):
    a, b = mapint()
    AB.append((a, -b))
AB.sort()

days = [0]*M
for a, b in AB:
    a -= 1
    if a>=M:
        continue
    if days[a]==0:
        days[a] = b
    else:
        idx = bisect_right(days[a:], b)
        if a+idx>=M:
            continue
        days[a+idx:] = [b]+days[a+idx:-1]

print(-sum(days[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7
import heapq

N,M = I()
L = [l() for _ in range(N)]
A = []
B = []
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
q = []
heapq.heapify(q)
for i in range(1,M+1):
    for j in range(len(A)):
        if A[0] > i:
            break
        else:
            A.pop(0)
            heapq.heappush(q,B.pop(0)*-1)
    if q:
        ans += heapq.heappop(q)*-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N,M = I()
L = [l() for _ in range(N)]
A = []
B = []
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
for i in range(1,M+1):
    i = bisect.bisect_right(A,i)
    if i == 0:
        continue
    v = max(B[:i])
    i2 = B.index(v)
    A.pop(i2)
    B.pop(i2)
    ans += v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB = sorted(AB, key=lambda x: x[0])
AB = sorted(AB, key=lambda x: x[1])
AB.reverse()

res = 0

f = [True]*M
for a, b in AB:
    if a > M:
        continue
    for i in range(a-1, M):
        if f[i]:
            f[i] = False
            res += b
            break

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

cnt = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a].append(b)

t = []
ans = 0
for i in range(1, m+1):
    t += cnt[i]
    t.sort()
    if t: ans += t.pop()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from operator import itemgetter
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort(key=itemgetter(1), reverse=True)
    
    schedule = [0] * M
    now = 0
    for a, b in AB:
        if a > M:
            continue

        tmp = M - a
        while tmp >= 0:
            if schedule[tmp] == 0:
                schedule[tmp] = b
                now += 1
                break
            tmp -= 1

        if now >= M:
            break

    print(sum(schedule))

main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(n):
  t = [int(inp) for inp in input().split()]
  if t[0] <= m:
    ab.append(t)

ab.sort(key = lambda x: x[0])
ans = 0
for i in range(1, m+1):
  ma = [0,0]
  for t in ab:
    if t[0] > i:
      break
    if t[1] > ma[1]:
      ma = t
  if ma != [0, 0]:
    ans += ma[1]
    ab.remove(ma)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(n):
  t = [int(inp) for inp in input().split()]
  if t[0] <= m:
    ab.append(t)

ab.sort(key = lambda x: -x[1])
ans = 0
slot = [False for i in range(m+1)]
for t in ab:
  b = t[0]
  a = t[1]
  if b > m:
    continue
  if False not in slot[b:m+1]:
    m = b-1
    continue
  ans += a
  ind = slot[b:m+1].index(False)
  slot[b+ind] = True
  if b+ind == m:
    m = m-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    a_t = list(zip(*a))
    a_s = set(a_t[0])
    cnt = 0
    h = [(l[1]*-1) for l in a if l[0] == 1]
    heapq.heapify(h)
    if 1 in a_s:
        cnt += heapq.heappop(h)
    for i in range(2, m+1):
        if i in a_s:
            p = [(l[1]*-1) for l in a if l[0] == i]
            for j in p:
                heapq.heappush(h, j)
        if h !=[]:
            cnt += heapq.heappop(h)
    print(-1*cnt)   
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
answer_list = [0]*M

part_times = []
for _ in range(N):
    A, B = map(int, input().split())
    part_times.append([A, B])
part_times = np.array(part_times)
part_times = sorted(part_times, key=lambda x: (x[1], x[0]), reverse=False)

for _ in range(N):
    temp = part_times.pop()
    day = temp[0]
    fee = temp[1]

    for i in range(M):

        if day + i > M:
            break
        
        if answer_list[-day - i] == 0:
            answer_list[-day - i] = fee
            break

print(sum(answer_list))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def __len__(self):
        return len(self.hq)

def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    ans = 0
    dhq = Descending_HeapQueue()
    pointer = 0
    for m in range(1, M+1):
        for a, b in AB[pointer:]:
            if a > m:
                break
            dhq.push(b)
            pointer += 1
        if len(dhq) > 0:
            ans += dhq.pop()
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
    ans = 0
    choice = []
    pointer = 0
    for m in range(1, M+1):
        for a, b in AB[pointer:]:
            if a > m:
                break
            choice.append([a, b])
            pointer += 1
        if len(choice) > 0:
            a, b = sorted(choice, key=lambda x: x[1], reverse=True)[0]
            ans += b
            choice.remove([a, b])
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

li = [[] for j in range(10**5+1)]

for _ in range(n):
  a, b = map(int, input().split())
  li[a].append(b)

ans = 0
jobs = []
for i in range(1, m+1):
  jobs.extend(li[i])
  if jobs == []:
    continue
  jobs.sort(reverse = True)
  ans += jobs.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
jobs = [[] for i in range(M)]

for i in range(N):
    A, B = map(int, input().split())
    if A - 1 < M:
        jobs[A-1].append(B)

q = []
ans = 0
for i in range(M):
    for j in jobs[i]:
        q.append(-j)
    heapq.heapify(q)
    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())

L = []
for i in range(n):
    a,b = map(int,input().split())
    if a > m:
        continue
    L.append([a,b])

L.sort(reverse = True)

ans = 0
li = []
for i in range(1,m+1):
    while L and L[-1][0] <= i:
        (a,b) = L.pop()
        heapq.heappush(li,b*(-1))

    if li:
        heapq.heapify(li)
        h = heapq.heappop(li)
        ans +=(-1)*h

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
a.append([np.inf, np.inf])
ans = 0
ind = 0
check = -1
for i in range(1, M+1):
    while a[ind][0] <= i:
        ind += 1
    if a[:ind]:
        m = max(a[:ind], key = lambda x:x[1])
        ans += m[1]
        a.remove(m)
        a.insert(0, [0, 0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
a.append([np.inf, np.inf])
job = []
ans = 0
ind = 0
for i in range(1, M+1):
    while a[ind][0] <= i:
        job.append(a[ind][1])
        ind += 1
        if ind == N:
            break
    if job:
        m = max(job)
        ans += m
        job.remove(m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
a.append([np.inf, np.inf])
job = []
ans = 0
ind = 0
for i in range(1, M+1):
    while a[ind][0] <= i:
        job.append(a[ind][1])
        ind += 1
        if ind == N:
            break
    if job:
        job.sort()
        ans += job.pop(-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
job = []
ans = 0
ind = 0
for i in range(1, M+1):
    if ind != N:
        while a[ind][0] <= i:
            job.append(a[ind][1])
            ind += 1
            if ind == N:
                break
    if job:
        job.sort()
        ans += job.pop(-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort(key = lambda x:x[1], reverse = True)
day = {i+1 for i in range(M)}
ans = 0
for i in range(N):
    check = {a[i][0] + j for j in range(N)}
    if check & day:
        ans += a[i][1]
        day -= {min(check & day)}
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*99*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=b,
for i in v[:M]:
 for j in i:heappush(q,-j)
 z-=heappop(q)
print(z)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
ans = 0
jobs = []
to_do = []
heapq.heapify(to_do)
for i in range(n):
    array = list(map(int, input().split()))
    array[1] *= -1
    jobs.append(array)

for i in range(1, m+1):
    addition = [j for j in jobs if j[0] == i]
    if len(addition) > 0:
        for x, y in addition:
            heapq.heappush(to_do, y)
    if len(to_do) > 0:
        ans += -1 * heapq.heappop(to_do)

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(1, m+1):
    x = [k for k in jobs if k[0] <= i]
    x.sort(key=lambda t:t[1], reverse=True)
    if len(x) > 0:
        job = x.pop(0)
        jobs.remove(job)
        ans += job[1]

print(ans)

Submission status: Time Limit Exceeded

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

spotwork.sort(key=lambda x: x[1], reverse=True)
#print(spotwork)

shift = [0] * m
for i in range(n):
    delay, payment = spotwork[i]
    for day in range(m - delay, -1, -1):
        if shift[day] == 0:
            shift[day] = payment
            break
print(sum(shift))