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:
# 2019-11-16 14:51:41(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    # 10**5連勤とか超人すぎる
    n, m = [int(x) for x in sys.stdin.readline().split()]

    job_list = dict((i, collections.deque()) for i in range(1, m+1))
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list[a].append(b)

    # 同じ日にできる仕事が二つ以上あったとして、
    # 第一に報酬が最も高い仕事をその日のシフトに入れる
    # それよりも前の日に空きがあれば残りの仕事を報酬の高い順に入れる
    # 空きがなかった場合、前日以前にやる仕事の中で最も報酬の低いものよりも、残りの仕事のなかで
    # 最も報酬の高いものの方が良ければ、その日の予定をを更新する。

    day_rewards = [0 for _ in range(m+1)] # 期限当日は報酬ゼロとして

    for i in range(m, 0, -1):
        latest = i
        while job_list[i]:
            mi = min(day_rewards[latest:])
            if mi < max(job_list[i]):
                latest = day_rewards.index(mi, latest)
                day_rewards[latest] = max(job_list[i])
                job_list[i].remove(max(job_list[i]))
            else:
                break
                
    print(sum(day_rewards))
    # 間に合うかな?


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[1],reverse=True)
used=[False]*n
ans=0
for i in range(m,-1,-1):
  left=m-i
  for j in range(len(tasks)):
    if used[j]==False and tasks[j][0]<=left:
      ans+=tasks[j][1]
      used[j]=True
      break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[1],reverse=True)
ans=0
for i in range(m,-1,-1):
  left=m-i
  for j in range(len(tasks)):
    if tasks[j][0]<=left:
      ans+=tasks.pop(j)[1]
      break

print(ans)

Submission status: Time Limit Exceeded

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


def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))
    AB.sort(key=lambda x: x[0])

    H = []
    I = 0
    ans = 0
    for m in range(M):
        for i in range(I, N):
            if AB[i][0] <= m+1:
                heapq.heappush(H, -AB[i][1])
                I += 1
        if H:
            ans += -heapq.heappop(H)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[0]*(M+1)
for i in range(M+1):
    A[i]=[]
for i in range(N):
    b,a=map(int,input().split())
    if b <= M:
        A[b].append(a)
for i in range(M):
     A[i]=sorted(A[i],reverse=True)
salary=0
for i in range(1,M+1):
    maxi = 0
    index = i
    for k in range(1,i+1):
        if A[k]!=[]:
            if maxi < A[k][0]:
                maxi = A[k][0]
                index = k
                A[k].pop(0)
    salary += maxi
print(salary)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n ,m = map(int,input().split())
li = []
for i in range(n):
    x, y= map(int,input().split())
    li.append([x,y])
li.sort()
heap = []

ans = 0
for i in range(m):
    bar = True
    while bar:
        if len(li) == 0:
            break
        if i >= li[0][0] - 1:
            price = li.pop(0)
            heapq.heappush(heap,-price[1])
        else:
            bar = False
    try:
        ans += -heapq.heappop(heap)
    except IndexError:
        ans += 0
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
def solve():
    N, M = list(map(int, input().split()))
    plan = []
    for _ in range(N):
        plan.append(list(map(int, input().split())))
    task = {}
    for p in plan:
      if p[0] in task.keys():
        task[p[0]].append(-p[1])
      else:
        task[p[0]] = [-p[1]]
    choices = []
    res = 0
    d = task.keys()
    for day in range(1, M+1):
        if day in d:
            choices.extend(task[day])
            hq.heapify(choices)
        if len(choices) > 0:
            res += - hq.heappop(choices)
    print(res)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N,M = input().split()
N,M = int(N),int(M)
f_start = [0 for i in range(N)]
A,B = [],[]
import heapq
for i in range(N):
    a,b = input().split()
    a,b = int(a),int(b)
    A.append(a)
    B.append(-b)
    
def add(q_,add_):
    for i in range(len(add_)):
        heapq.heappush(q_,add_[i])

def kouho(A,B,m):
    kouho_list = []
    for i in range(len(B)):
        if(A[i]==m):
            kouho_list.append(B[i])
    return kouho_list

q = []
heapq.heapify(q)
sum_money = 0

for m in range(1,M+1):
    kouho_list = kouho(A,B,m)
    add(q,kouho_list)
    #print(q)
    if(len(q)>0):
        sum_money += -heapq.heappop(q)
print(sum_money)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [list(map(int,input().split())) for i in range(N)]
ab = sorted(ab, key = lambda x:x[0])
tgt = []
count = 0
profit = 0
for m in range(M-1,-1,-1):
    for i in range(count, len(ab)):
        if ab[i][0] == M-m:
            tgt.append(ab[i][1])
            count += 1
        else:
            break
    if tgt != []:
        profit += max(tgt)
        tgt.remove(max(tgt))
print(profit)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m=map(int,input().split())
l=[[] for _ in range(m)]
for _ in range(n):
  a,b=map(int,input().split())
  if a<=m:
    l[a-1].append(b)
ans=0
w=[]
for i in range(m):
  for j in l[i]:
    bisect.insort_right(w,j)
  if w!=[]:
    ans+=w.pop(-1)
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],reverse=True)
AB = sorted(AB,key=lambda x:x[1],reverse=True)
dp = [0 for _ in range(M)]
rest = M
for a,b in AB:
    aa = a-1
    if aa >= rest:
        continue
    if dp[aa] == 0:
        dp[aa] = b
    else:
        flag = False
        for i in range(aa,rest):
            if dp[i] == 0:
                dp[i] = b
                flag = True
                break
        if flag is False:
            rest = aa
print(sum(dp))

Submission status: Time Limit Exceeded

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

for i in range(n):
    d, r = map(int, input().split())
    try:
        day[d - 1].append(r)
    except:
        pass

sum = 0
l = list()
for i in range(m):
    l.extend(day[i])
    l.sort(reverse=True)
    sum += l.pop(0)

print(sum)

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(1, M+1):
    AB[i] += AB[i-1]
    if len(AB[i]) == 0:
        continue
    AB[i].sort()
    ans += AB[i].pop()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
a.sort(key=lambda x: x[1],reverse=True)
x=[1 for i in range(m)]
ans=0
count=0
q=[]

for i in range(1,m+1):
    for j in range(n):
        if a[j][0]==i: 
            heapq.heappush(q,-a[j][1])
    
    if len(q)!=0:
        ans+=-heapq.heappop(q)
        
            

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
a.sort(key=lambda x: x[1],reverse=True)
x=[1 for i in range(m)]
ans=0
count=0
for i in range(n):
    if a[i][0]<=m:
        for j in range(a[i][0]-1,m):
            if x[j]==1:
                ans+=a[i][1]
                x[j]=-1
                break
            

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = [int(x) for x in input().split()]
# 各要素がintで、indexが1からの場合
A = [None] * (N + 1)
B = [0] * (N + 1)
for i in range(1, N + 1):
    A[i], B[i] = [int(x) for x in input().split()]


total = sum(B)

S = [[] for i in range(M + 1)]  # S[j]はj日目までに実施しなければならないアルバイトの報酬のmin heap
for i in range(1, N + 1): # for each job i  --- O(Nlog(N))
    if A[i] > M:
        total -= B[i]
    else:
        heapq.heappush(S[M - A[i]], B[i]) # O(log(N))


for j in range(0, M): # for each day j = 0, 1, ..., M - 1
    while len(S[j]) > j + 1: # O(N)
        minus = heapq.heappop(S[j]) # O(logN)
        total -= minus
    for k in range(0, len(S[j])):
        s = heapq.heappop(S[j])
        heapq.heappush(S[j + 1], s)

print(total)

Submission status: Time Limit Exceeded

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

tasks = sorted(tasks, key=lambda x: x[0])
count = 0

for i in range(m):
    max_list = [0,0]
    max_j = 0
    for j,task in enumerate(tasks):
        if task[0] > i+1:
            break
        if task[1] > max_list[1]:
            max_list = task
            max_j = j
    if max_list != [0,0]:
        del tasks[max_j]
        count += max_list[1]

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

Sum = 0

for i in range(M):
    
    max = 0
    max_j = -1
    
    for j in range(N):
        
        if A[j] <= i+1 and B[j] > max:
            max = B[j]
            max_j = j
    
    if max_j != -1:
        
        Sum += max
        B[max_j] = 0
        
print(Sum)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m = map(int,input().split())
lb = []
for _ in range(n):
    lb.append(list(map(int,input().split())))
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb:
        if b[0] == i:
            heapq.heappush(q,b[1] * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab = sorted(ab, key=lambda x:(x[0], x[1])) + [[0,0]]
lst = []
now = 0
ans = 0
heapq.heapify(lst)
for i in range(1,m+1):
  while ab[now][0] == i:
    heapq.heappush(lst,-ab[now][1])
    now += 1
  heapq.heapify(lst)
  if lst:
    ans -= heapq.heappop(lst)
print(ans)

Submission status: Time Limit Exceeded

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

AB_dict = {}
for i in range(M):
    AB_dict[i + 1] = []
for i in range(N):
    if AB[i][0] > M:
        continue
    AB_dict[AB[i][0]].append(AB[i][1])

Job = []
ans = 0
for i in range(M):
    Job = Job + AB_dict[i + 1]
    if len(Job) != 0:
        ans += max(Job)
        Job.remove(max(Job))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
for rest_days in range(1, M+1):
    tmp += income[rest_days]
    heapq.heapify(tmp)
    if tmp:
        ans += heapq.heappop(tmp)

print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
for rest_days in range(1, M+1):
    tmp = list(heapq.merge(tmp, income[rest_days]))
    heapq.heapify(tmp)
    if tmp:
        ans += heapq.heappop(tmp)

print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, M = map(int, input().split())
income = [[] for _ in range(M+1)] # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        bisect.insort_left(income[a], b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
for rest_days in range(1, M+1):
    if income[rest_days]:
        ans += income[rest_days].pop(-1)
        if rest_days < M:
            income[rest_days+1] = sorted(income[rest_days+1] + income[rest_days])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
income = [[] for _ in range(M+1)] # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
for rest_days in range(1, M+1):
    if income[rest_days]:
        m = max(income[rest_days])
        ans += m
        if rest_days < M:
            income[rest_days].remove(m)
            income[rest_days+1] += income[rest_days]
            income[rest_days+1].sort()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M =  list(map(int,input().split()))

A = []
B = []
for i in range(N):
    s, t = list(map(int,input().split()))
    A.append(s)
    B.append(t)

st = list(np.argsort(B))
st.reverse()

day = [0]*(M+1)
cnt = 0

for i in range(N):
    if A[st[i]] > M:
        continue
    for j in range(M-A[st[i]]+1):
        if day[M-A[st[i]]-j] == 0:
            day[M-A[st[i]]-j] = 1
            cnt += B[st[i]]
            break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M =  list(map(int,input().split()))

A = []
B = []
for i in range(N):
    s, t = list(map(int,input().split()))
    A.append(s)
    B.append(t)

st = list(np.argsort(B))
st.reverse()

day = [0]*(M+1)
cnt = 0

for i in range(N):
    tmpday=day[:]
    if A[st[i]] > M:
        continue
    for j in range(M-A[st[i]],M+1):
        tmpday[j] += 1
    flag = True
    for j in range(M+1):
        if tmpday[j] > j+1:
            flag = False
    if flag:
        cnt += B[st[i]]
        day = tmpday

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

N, M =  list(map(int,input().split()))

A = []
B = []
for i in range(N):
    s, t = list(map(int,input().split()))
    A.append(s)
    B.append(t)

st = list(np.argsort(B))
st.reverse()

day = [0]*(M+1)
cnt = 0

for i in range(N):
    if A[st[i]] > M:
        continue
    tmpday= day[:]
    tmpday[M-A[st[i]]] += 1
    flag = True
    for j in range(M+1):
        if sum(tmpday[:j+1]) > j+1:
            flag = False
    if flag:
        cnt += B[st[i]]
        day[M-A[st[i]]] += 1

print(cnt)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
sum = 0
# Aiが最小のものから順に選ぶ
# 重複するときは最大金額を選び残りはAiを+1する

# Ai>Mのものは最初から除外
# 受け取りにA日かかるということはM-A+1日目までに受けなければならない
# index = M-A(day)
# element = B(reword)

schedule = [[] for _ in range(m+1)]
for _ in range(n):
    day, reword = map(int, input().split())
    if day > m:
        continue
    schedule[m-day+1].append(reword)

for i in range(m, 0, -1):
    if not schedule[i]:
        del schedule[i]
        continue
    max_reword = heapq.nlargest(1, schedule[i])
    sum += max_reword[0]
    schedule[i].remove(max_reword[0])
    if schedule[i]:
        schedule[i-1].extend(schedule[i])
    del schedule[i]

print(sum)

Submission status: Time Limit Exceeded

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

def solve():
    N, M = map(int, input().split())
    abl = [0] * N
    for i in range(N):
        abl[i] = list(map(int, input().split()))
        abl[i][1] *= -1
    
    ans = 0
    hq = []
    hq_hash = []
    for i in range(1, M+1):
        for j in range(N):
            if abl[j][0] <= i and j not in hq_hash:
                heapq.heappush(hq, abl[j][1])
                hq_hash.append(j)
        if len(hq) > 0:
            ans += -heapq.heappop(hq)
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import  heapq
N,M = map(int,input().split())
heap = [(0,0)]
for i in range(N):
    a,b = map(int,input().split())
    heapq.heappush(heap,(-b,a))
memo = [0 for i in range(M+1)]
ans = 0
for i in range(N):
    p,q = heapq.heappop(heap)
    for i in range(M-q,-1,-1):
        if memo[i] == 0 :
            ans -= p
            memo[i] = 1
            break
        else :
            pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort(reverse = True)
    q = []
    ans = 0
    j = N-1
    for i in range(M-1, -1, -1):
        while j >=0 and AB[j][0] <= M-i:
            a, b = AB[j]
            heapq.heappush(q, -b)
            j -= 1
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort(reverse = True)
    q = []
    ans = 0
    j = N-1
    for i in range(M-1, -1, -1):
        while j >=0 and AB[j][0] <= M-i:
            a, b = AB.pop()
            heapq.heappush(q, -b)
            j -= 1
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort(reverse = True)
    q = []
    ans = 0
    for i in range(M-1, -1, -1):
        while AB and AB[-1][0] <= M-i:
            a, b = AB.pop()
            heapq.heappush(q, -b)
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():

    N, M = map(int, input().split())
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        AB.append([a, b])
        AB.sort()
    q = []
    ans = 0
    for i in range(M-1, -1, -1):
        while AB and AB[0][0] <= M-i:
            a, b = AB.pop(0)
            heapq.heappush(q, -b)
        if q:
            v = -heapq.heappop(q)
            ans += v
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
data=[[] for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m:
        data[a].append(b)
for i in range(1,m+1):
    data[i].sort()
s=0
for i in range(1,m+1):
    a=0
    count=0
    for j in range(1,i+1):
        if data[j]:
            if a<data[j][-1]:
                a=data[j][-1]
                count=j
    if count!=0:
        s+=a
        data[count].pop()
print(s)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

baitos = sorted(baitos)
# print(sorted(baitos))
# print(baitos)

money = 0
avail = []
heapq.heapify(avail)
for day in range(m):
    while baitos:
        if baitos[0][0] > day + 1:
            break
        else:
            heapq.heappush(avail, -baitos[0][1])
            baitos.remove(baitos[0])
    # for baito in baitos:
    #     print(baito)
    #     if baito[0] > day + 1:
    #         print("break")
    #         break
    #     else:
    #         heapq.heappush(avail, -baito[1])
    #         baitos.remove(baito)
    # print("baitos", baitos)
    # print("avail", avail)
    if avail:

        money += -heapq.heappop(avail)
        # print(day, money)
    # money += max[1]
    # baitos.remove(max)

print(money)

Submission status: Time Limit Exceeded

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

baitos = sorted(baitos)
# print(sorted(baitos))
# print(baitos)

money = 0
for i in range(m):
    max = [0, 0]
    for baito in baitos:
        if baito[0] > i + 1:
            break
        elif max[1] < baito[1]:
            max = baito
    if max != [0, 0]:
        # print(max[1])
        money += max[1]
        baitos.remove(max)

print(money)

Submission status: Time Limit Exceeded

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N, M = map(int, input().split())
L1 = [[] for _ in range(10001)]  # 仕事リスト（インデックス：単価、要素：最終受注可能日）
L2 = [0] * M  # 受注する仕事リスト（インデックス：日、要素：単価）
flag = 1
for _ in range(N):
    a, b = map(int, input().split())  # a:日 b:単価
    L1[b].append(M - a)
for i in range(10000, 0, -1):  # i:単価
    if L1[i] == []:
        continue
    for j in sorted(L1[i], reverse=True):  # j:日
        while j >= 0 and flag:
            if L2[j] == 0:
                L2[j] = i
                flag = 0
            else:
                j -= 1
        flag = 1
print(str(sum(L2)))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
ans = 0
a = []
heapq.heapify(a)
for i in range(1,m+1):
  for j in range(len(ab)):
    if ab[j][0] == i:
      heapq.heappush(a,(-1)*ab[j][1])
  if a == []:
    continue
  else:
    x = heapq.heappop(a)
  ans += x
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    if a <= m:
        ab.append([a,b])
ab.sort()

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop

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

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int,input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int,input().split())
ptj = {}
for i in range(N):
    if A[i] in ptj:
        ptj[A[i]].append(-B[i])
    else:
        ptj[A[i]] = [-B[i]]
count = 0
s = []
for i in range(1,M+1):
    if i in ptj:
        s.extend(ptj[i])
        heapq.heapify(s)
    if s != []:
        count -= heapq.heappop(s)
print(count)

Submission status: Time Limit Exceeded

Solution code:
#AtCoder

import sys
import math
import itertools
input = sys.stdin.readline

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

reward = 0
for m in range(M+1):
	BMAX = -1
	index = -1
	for i in range(len(A)):
		if A[i] <= m and BMAX < B[i]:
			BMAX = B[i]
			index = i
	if BMAX != -1:
		reward += BMAX
		A.pop(index)
		B.pop(index)

print(reward)



"""

"""

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
ans = 0
a = []
for i in range(1,m+1):
  for j in range(len(ab)):
    if ab[j][0] <= i:
      a.append(ab[j])
  a.sort(key=lambda x:x[1])
  if a == []:
    continue
  else:
    x = a.pop()
  ab.remove(x)
  ans += x[1]
  a = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(n):
    ab.append(list(map(int,input().split())))
    ab[i].append(ab[i][0])
    del ab[i][0]
day=[]
for i in range(m):
    day.append(1)
ans=0
cou=0
ab.sort()
for i in range(n):
    if ab[n-1-i][1]<=m:
        for j in range(1+m-ab[n-1-i][1]):
            if day[ab[n-1-i][1]-1+j]==1:
                ans+=ab[n-1-i][0]
                day[ab[n-1-i][1]-1+j]=0
                cou+=1
                break
        if cou==m:
            break
print(ans)

Submission status: Time Limit Exceeded

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

ab=[]
for _ in range(N):
  ab.append(list(map(int,input().split())))

sal=0
poss=[]
for i in range(1,M+1):
  for j in range(N):
    if ab[j][0]==i:
      heapq.heappush(poss,-ab[j][1])
  if len(poss)>0:
    sal+=-heapq.heappop(poss)
    
print(sal)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m=map(int,input().split())
c=[]
for i in range(n):
    a,b=map(int,input().split())
    c.append([a,-b])
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(n):
        if c[j][0]==i:
            heapq.heappush(d,c[j][1])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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


d_AB = {a:[] for a,b in AB}
for a,b in AB:
    d_AB[a].append(-b)

H = []
money = 0
for i in range(1,M+1):
    if i in d_AB.keys():
        H += d_AB[i]
    else:
        H += [0]
    #print(H)
    heapq.heapify(H)
    money += heapq.heappop(H)

print(-money)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict

N,M = map(int, input().split())


work = defaultdict(list)

for i in range(N):
    a,b = map(int, input().split())
    work[a-1].append(-b)



# 終了日から１日前、２日前、...の順で仕事を選ぶ
current_work = []
ans = 0
for i in range(M):
    if i in work.keys():
        current_work.extend(work[i])

    if current_work:
        heapq.heapify(current_work)
        money = heapq.heappop(current_work)
        ans += -1 * money

print(ans)

Submission status: Time Limit Exceeded

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

AB_list =[]
for i in range(N):
    AB_list.append(tuple(map(int,input().split())))

AB_list.sort()
#print(AB_list)
ans = 0

for i in range(M):
    hoshu = 0
    t = 0
    flag = False
    for j in range(N):
        if (AB_list[j][0] <= i+1):
            if hoshu <= AB_list[j][1]:
                hoshu = AB_list[j][1]
                t = j
                flag = True

        else:
            break

    if flag:
        del AB_list[t]
        N -= 1
    #print(hoshu, t)
    ans += hoshu
    #print(AB_list)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
#import heapq as hq

n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
D = defaultdict(list)

for a, b in L:
    D[a].append(b)

money =0
tmp = []
for l in range(1, limit+1):
    tmp +=D[l]
    if tmp:
        money+=max(tmp)
        tmp.remove(max(tmp))

print(money)

Submission status: Time Limit Exceeded

Solution code:
def main():
     import sys
     input=sys.stdin.readline

     ans=0
     N,M=map(int,input().split())
     Ar=[]
     for _ in range(M):
           Ar.append([])
     for _ in range(N):
          A,B=map(int,input().split())
          if A <= M:
              Ar[A-1].append(B)
     An=[]
     for i in range(M):
          An += Ar[i]
          if len(An)>0:
              An.sort()
              ans+=An.pop(len(An)-1) 
     print(ans)

if __name__ =='__main__':
    main()

Submission status: Time Limit Exceeded

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

ans=0
N,M=map(int,input().split())
Ar=[]
for _ in range(M):
     Ar.append([])
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An.sort()
          ans+=An.pop(len(An)-1) 
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
N,M=map(int,input().split())
Ar=[[] for _ in range(M)]
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An.sort()
          ans+=An.pop(len(An)-1) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    [N, M] = [int(number) for number in input().split()]
    part_times = []
    for i in range(N):
        job= [int(number) for number in input().split()]
        part_times.append(job)
    part_times = [part_time for part_time in sorted(part_times, key = lambda x: (x[1], x[0]), reverse=True)] #if part_time[0] <= M]
    money = 0
    #day = 0
    #earns = []
    for day in range(M):
        for part_time in part_times:
            if part_time[0] <= day + 1:
                money += part_time[1]
                part_times.remove(part_time)
                break
        """
        try:
            todays_part = next(itertools.ifilter(lambda x: x[0] <= day+1, part_times), None)
            money += todays_part[1]
            part_times.remove(todays_part)
        except:
            continue
        """

    """
    for [income_day, earn] in part_times:
        remain_day = M - day
        if remain_day >= income_day:
            money += earn
        else:
            min_earn = min(earns)
            if earn > min_earn:
                money += earn
                money -= min_earn
                earns.remove(min_earn)
        earns.append(earn)
        day += 1
    """
    print(money)

if __name__ == '__main__':
    main()