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:
N, M = map(int, input().split())
jobs = [list(map(int, input().split())) for _ in range(N)]

ans = 0
for day in range(M, 0, -1):
    best_job = [0, 0]
    for job in jobs:
        if day + job[0] - 1 <= M:
            if best_job[1] <= job[1]:
                best_job = job
    if best_job != [0, 0]:
        jobs.remove(best_job)
        ans += best_job[1]

print(ans)

Submission status: Time Limit Exceeded

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

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

done = [0 for _ in range(n)]
gain = 0

for i in reversed(range(1,m+1)): #i:残り日数
    for j in range(n): #j:候補から優先度順で探索
        if lst[j][0] <= i and done[j] == 0: #必要な日数>残り日数 かつ undone
            gain += lst[j][1]
            done[j] = 1 #undone:0,done:1として分類
            break #働いたら次の日へ

print(gain)

Submission status: Time Limit Exceeded

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

def schedule(reward, day, jobs):
    if day > M or not jobs:
        return reward
    else:
        results = []
        for job in jobs:
            if day + job[0] - 1 > M:
                jobs.remove(job)

        if not jobs:
            return reward

        best_jobs = {}
        for job in jobs:
            if job[0] in best_jobs:
                if best_jobs[job[0]][1] < job[1]:
                    best_jobs[job[0]] = job
            else:
                best_jobs[job[0]] = job

        for job in best_jobs.values():
            copied_jobs = list(jobs)
            copied_jobs.remove(job)
            result = schedule(reward + job[1], day + 1, copied_jobs)
            results.append(result)
        return max(results)

print(schedule(0, 1, jobs))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
#dab={}
lab=[]
for i in range(N):
    a,b=map(int,input().split())
    #dab[a]=b
    lab.append([a,b])
#dab.sort(key=lambda )
lab.sort(key=lambda x:-x[1])
#print("lab",lab)
#lsch=[-1]*M#ミスしてた#やっぱおk_どうせM番目には入らない
#lsch=[M-1-i for i in range(M)]
dsch={i:0 for i in range(M)}
ans=0
for ab in lab:
    if ab[0]<=M:
        d=M-ab[0]
        #while d>=0:
        #for i in range(d,-1,-1):
        #    if lsch[i]==-1:#whileから書き直したときiではなくdのままにしていた
        #        lsch[i]=1
        #        ans+=ab[1]
        #        #print("ab",ab)
        #        break
            #d-=1
        #while d>=0:
        for i in range(d,-1,-1):
            if i in dsch:
                ans+=ab[1]
                #print("ab",ab)
                del dsch[i]
                break
#print("lsch",lsch)
#print("dsch",dsch)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000*10000)

def dfs(res, depth, path, A, B, time, M):
    res.append(path)
    for i in range(depth, len(A)):
        if time + A[i] <= M:
            dfs(res, i+1, path + [B[i]], A, B, time + 1, M)

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

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

C, D = [], []
for c, d in sorted(zip(A,B), key=lambda x: x[0], reverse=True):
    C.append(c)
    D.append(d)
    
del A, B
    
dfs(res, 0, [], C, D, 0, M)
print(sum(sorted(res, key=lambda x: sum(x))[-1])) if res else print(0)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

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

day_value_dict = {}
for _ in range(n):
    a, b = map(int, input().split())
    day_value_dict[a] = day_value_dict.get(a, [])
    heappush(day_value_dict[a], -b)


res = 0
for m_i in range(1, m + 1):
    temp = 0
    selected_x = 0
    for x in range(1, m_i + 1):
        if x not in day_value_dict or not day_value_dict[x]:
            continue
        if day_value_dict[x][0] < temp:
            temp = day_value_dict[x][0]
            selected_x = x
    if selected_x:
        res += temp
        heappop(day_value_dict[selected_x])

print(-res)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b, 0))


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

res = 0
for m_i in range(1, m + 1):
    for x in range(len(arr)):
        a, b, deleted = arr[x]
        if deleted:
            continue
        if a <= m_i:
            res += b
            arr[x] = a, b, 1
            break
print(res)

Submission status: Time Limit Exceeded

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


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

res = 0
for m_i in range(1, m + 1):
    for x in range(len(arr)):
        a, b = arr[x]
        if a <= m_i:
            res += b
            del arr[x]
            break
print(res)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
works = []
for i in range(N):
  a, b = map(int, input().split())
  works.append((a, b))
sorted_works = sorted(works, key=lambda x: x)
all_benefit = 0
for i in range(M):
    day = i + 1
    benefit = 0
    temp = ()
    for work in sorted_works:
        if day < work[0]:
            break
        if benefit <= work[1]:
            temp = work
            benefit = work[1]
    if temp:
        sorted_works.remove(temp)
    all_benefit += benefit

print(all_benefit)

Submission status: Time Limit Exceeded

Solution code:


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

allhiyatoi = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    allhiyatoi[temp[0]].append(temp[1])

temp = []
for i in allhiyatoi:
    temp.append(collections.deque(sorted(i)))

allhiyatoi = temp
 
reward = 0
for i in range(M+1):
    D = -1
    maxrw = -1
    for j,day in enumerate(allhiyatoi):
        if j > i:
            break
        if len(day) == 0:
            continue
        rw = max(day)
        if maxrw < rw:
            D = j
            maxrw = rw
    if D == -1:
        continue
    reward += allhiyatoi[D].pop()

print(reward)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        results = [None] * M
        for i in range(N):
            A, B = map(int, input().split())
            if A > M:
                continue
            for dayidx, job in enumerate(results):
                if A > dayidx+1:
                    continue
                if job is None or B > job:
                    results[dayidx] = B
                    if job is None:
                        break
                    for j in range(dayidx + 1, M):
                        if results[j] is None or job > results[j]:
                            n = results[j]
                            results[j] = job
                            job = n
                            if job is None:
                                break
                    break
        print(sum(filter(lambda x: x is not None, results)))
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
n,m = map(int,input().split())
k = m

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    salary.append(t)

    if s - k > 0:
        salary.remove(min(salary))
    else:
        k -= 1

print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
n,m = map(int,input().split())
k = m

for i in range(n):
    job.append(tuple(map(int,input().split())))

job.sort(reverse = True)

for x in job:
    a,b = x
    salary.append(b)

    if a > k:
        salary.remove(min(salary))
    else:
        k -= 1

print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
k = 0
n,m = map(int,input().split())

for i in range(n):
    job.append(tuple(map(int,input().split())))

job.sort(reverse = True)

for x in job:
    a,b = x
    salary.append(b)

    if a + k > m:
        salary.remove(min(salary))
    else:
        k += 1

print(sum(salary))

Submission status: Time Limit Exceeded

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

allhiyatoi.sort()

reward = 0
for i in range(M+1):
    today_hiya_idx = -1
    today_reward = 0
    for j,hiya in enumerate(allhiyatoi):
        if hiya[0]>i:
            break
        if today_reward <= hiya[1]:
            today_hiya_idx = j
            today_reward = hiya[1]
    
    reward += today_reward
    if today_hiya_idx != -1:
        allhiyatoi[today_hiya_idx][1] = -1

print(reward)

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
k = 0
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    a,b = x
    salary.append(b)

    if a + k > m:
        salary.remove(min(salary))
    else:
        k += 1

print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
k = 0
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for j in range(n):
    a,b = job[j]
    salary.append(b)

    if a + k > m :
        salary.remove(min(salary))
        continue

    k += 1

print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
work_list = [list(map(int, input().split())) for _ in range(n)]
work_cand = []
salary = 0
for j in range(1, m + 1):
    for i in range(n):
        if work_list[i][0] == j:
            work_cand.append(work_list[i])
        else:
            pass
    if work_cand != []:
         work_cand.sort(key = lambda x: x[1], reverse = True)
         salary += work_cand[0][1]
         del work_cand[0]
    else:
        pass
print(salary)

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
j = 0
n,m = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))
job.sort(reverse = True)
for i in range(n):
    a,b = job[i]
    salary.append(b)
    if a + j > m :
        salary.remove(min(salary))
        continue
    j += 1
print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
m_total = 0
j = 0
n,m = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))
    job.sort(reverse = True)
for i in range(n):
    a,b = job[i]
    salary.append(b)
    if a + j > m :
        salary.remove(min(salary))
        continue
    j += 1
print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
job = list()
salary = list()
m_total = 0
count = 0
n,m = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))
job.sort()
job.reverse()
for i in range(n):
    a,b = job[i]
    salary.append(b)
    if a + i - count > m :
        count += 1
        salary.remove(min(salary))
k = n - count

print(sum(salary))

Submission status: Time Limit Exceeded

Solution code:
job = list()
day = list()
salary = list()
m_total = 0
count = 0
n,m = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))
job.sort()
job.reverse()
for i in range(n):
    a,b = job[i]
    day.append(a)
    salary.append(b)
    if a + i - count > m :
        count += 1
        salary.remove(min(salary))
k = n - count
for l in range(k):
    m_total += salary[l]
print(m_total)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
#dab={}
lab=[]
for i in range(N):
    a,b=map(int,input().split())
    #dab[a]=b
    lab.append([a,b])
#dab.sort(key=lambda )
lab.sort(key=lambda x:-x[1])
#print("lab",lab)
#lsch=[-1]*M#ミスしてた#やっぱおk_どうせM番目には入らない
#lsch=[M-1-i for i in range(M)]
dsch={i:0 for i in range(M)}
ans=0
for ab in lab:
    if ab[0]<=M:
        d=M-ab[0]
        #while d>=0:
        #for i in range(d,-1,-1):
        #    if lsch[i]==-1:#whileから書き直したときiではなくdのままにしていた
        #        lsch[i]=1
        #        ans+=ab[1]
        #        #print("ab",ab)
        #        break
            #d-=1
        #while d>=0:
        for i in range(d,-1,-1):
            if i in dsch:
                ans+=ab[1]
                #print("ab",ab)
                del dsch[i]
                break
#print("lsch",lsch)
#print("dsch",dsch)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
#dab={}
lab=[]
for i in range(N):
    a,b=map(int,input().split())
    #dab[a]=b
    lab.append([a,b])
#dab.sort(key=lambda )
lab.sort(key=lambda x:-x[1])
#print("lab",lab)
lsch=[-1]*M#ミスしてた#やっぱおk_どうせM番目には入らない
ans=0
for ab in lab:
    if ab[0]<=M:
        d=M-ab[0]
        #while d>=0:
        for i in range(d,-1,-1):
            if lsch[i]==-1:#whileから書き直したときiではなくdのままにしていた
                lsch[i]=1
                ans+=ab[1]
                #print("ab",ab)
                break
            #d-=1
#print("lsch",lsch)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
N, M = map(int, input().split())
work = [list(map(int, input().split())) for _ in range(N)]
work.sort(key = lambda x: x[1], reverse=True)
#print(work)
inf = 10 ** 5 + 1
money = 0
able = [i for i in range(M + 1)] + [inf]
added = 0
for i in range(N):
  if added == M:
    break
  ind = bl(able, work[i][0])
  if able[ind] != inf:
    able = able[: ind] + able[ind + 1: ]
    money += work[i][1]
    added += 1
print(money)

Submission status: Time Limit Exceeded

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

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

reward = [0] * (M+1)
finish = set([])
remain = set(range(M+1))
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    now = remain - finish
    if max(now)<hiya[0]:
        continue
    for i in remain:
        if i<hiya[0]:
            continue
        if reward[i] == 0:
            reward[i] = hiya[1]
            finish.add(i)
            break

print(sum(reward))

Submission status: Time Limit Exceeded

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

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

reward = [0] * (M+1)
finish = set([])
remain = set(range(M+1))
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    if max(remain)<hiya[0]:
        continue
    now = remain - finish
    for i in remain:
        if i<hiya[0]:
            continue
        if reward[i] == 0:
            reward[i] = hiya[1]
            finish.add(i)
            break

print(sum(reward))

Submission status: Time Limit Exceeded

Solution code:
x1 = input()
N = int(x1.split()[0])
M = int(x1.split()[1])

data = []
result = 0

for i in range(N):
    x2 = input()
    data.append([int(x2.split()[0]),int(x2.split()[1])])
    
for t in range(M-1,-1,-1):
    max_work = [-1,-1]
    for work in data:
        if t + work[0] <= M and work[1] > max_work[1]:
            max_work = work
    
    if max_work == [-1,-1]:
        continue
    else:
        result += max_work[1]
        data.remove(max_work)
        
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M = map(int, input().strip().split(' '))
work_dict = { i:[] for i in range(1,M+1)}
for _ in range(N):
  a,b = map(int, input().strip().split(' '))
  if 0 < a <= M:
    work_dict[a].append(b)

def argmax(list_):
  max_v = -float('inf')
  max_i = None
  for i,l in enumerate(list_):
    if l > max_v:
      max_v = l
      max_i = i
  return max_i, max_v

result = 0
works = []
for i in range(1,M+1):  # 残り日数
  works += work_dict[i]
  if len(works) > 0:
    max_i,max_v = argmax(works)
    works.pop(max_i)
    result += max_v

print(result)

Submission status: Time Limit Exceeded

Solution code:
#おら間違えてんぞはよ直せや

import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
n,m = ips()
a = []
maxdays = -1
sublist = []
for i in range(n):
    a.append(iprow())
    maxdays = max(maxdays,a[i][0])
    sublist.append([a[i][1],i])
a.sort()
sublist.sort(reverse=True)
days = m
l = len(a)-1
while a[l][0] > days:
    a.pop(-1)
    if len(a)==0:
        print(0)
        exit(0)
    l-=1
s = 0
while days:
    #print("days",days)
    #printrow(a)
    while a[len(a)-1][0] > days:
        a.pop(-1)
        l-=1
        if len(a) == 0:
            break
    if len(a)==0:break
    biggest = a[len(a)-1][1]
    place = len(a)-1
    for i in range(len(a)-1,-1,-1):
        if biggest < a[i][1]:place = i
        biggest = max(biggest,a[i][1])
        if a[i][0] == 1 and a[i][1] != 0:break
    #print(biggest)
    s+=max(biggest,0)
    #print("s",s)
    a[place][1] = 0
    days-=1
print(s)

Submission status: Time Limit Exceeded

Solution code:
#おら間違えてんぞはよ直せや

import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
n,m = ips()
a = []
maxdays = -1
sublist = []
for i in range(n):
    a.append(iprow())
    maxdays = max(maxdays,a[i][0])
    sublist.append([a[i][1],i])
a.sort()
sublist.sort(reverse=True)
days = m
l = len(a)-1
while a[l][0] > days:
    a.pop(-1)
    if len(a)==0:
        print(0)
        exit(0)
    l-=1
s = 0
while days:
    #print("days",days)
    #printrow(a)
    while a[len(a)-1][0] > days:
        a.pop(-1)
        l-=1
        if len(a) == 0:
            break
    if len(a)==0:break
    biggest = a[len(a)-1][1]
    place = len(a)-1
    for i in range(len(a)-1,-1,-1):
        if biggest < a[i][1]:place = i
        biggest = max(biggest,a[i][1])
    #print(biggest)
    s+=max(biggest,0)
    #print("s",s)
    a[place][1] = 0
    days-=1
print(s)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
num_dict={}
for i in range(N):
    A, B = map(int, input().split())
    if A in num_dict:
        num_dict[A].append(B)
    else:
        num_dict.setdefault(A, []).append(B)
ans = 0
for i in range(1, M+1):
    possive_dict = {0:0}
    for x in num_dict:
        if x <= i:
            possive_dict.setdefault(max(num_dict[x]), x)
    a = max(possive_dict.keys())
    ans += a
    if possive_dict[a] in num_dict:
        num_dict[possive_dict[a]].remove(a)
        if not num_dict[possive_dict[a]]:
            del num_dict[possive_dict[a]]
    possive_dict.clear()

print(ans)

Submission status: Time Limit Exceeded

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

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

reward = [0] * (M+1)
remain = list(range(M+1))
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    for i in remain:
        if i<hiya[0]:
            continue
        if reward[i] == 0:
            reward[i] = hiya[1]
            remain[i] = -1
            break

print(sum(reward))

Submission status: Time Limit Exceeded

Solution code:
import numpy
# TLE

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

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

reward = [0] * (M+1)
remain = numpy.arange(M+1)
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    for i in (remain[ remain>=hiya[0] ]):
        if reward[i] == 0:
            reward[i] = hiya[1]
            numpy.delete(remain,i)
            break

print(sum(reward))

Submission status: Time Limit Exceeded

Solution code:
import numpy
# TLE

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

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

reward = [0] * (M+1)
remain = numpy.arange(M+1)
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    for i in (remain[ remain>=hiya[0] ]):
        if reward[i] == 0:
            reward[i] = hiya[1]
            remain[i] = -1
            break

print(sum(reward))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import numpy as np

def solve(N, M, A, B):
    # print('A', A)
    # print('B', B)
    ans = 0
    # 日付順にソートする
    dtype = [('a', np.uint32), ('b', np.uint32)]
    ab = np.array(list(zip(A, B)), dtype=dtype)
    ab = np.sort(ab, order='a')

    works = np.empty(ab.size, dtype=dtype)
    # print('ab=', ab)
    ans = 0
    ab_idx = 0
    works_n = 0
    for d in range(1, M+1):
        # print('d=', d)
        if ab_idx < ab.size and ab[ab_idx]['a'] == d:
            while ab_idx < ab.size and ab[ab_idx]['a'] == d:
                works[works_n] = ab[ab_idx]
                works_n += 1
                ab_idx += 1
            works[0:works_n] = np.sort(works[0:works_n], order='b')
        if works_n > 0:
            ans += works[works_n-1]['b']
            works_n -= 1

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import numpy as np

def solve(N, M, A, B):
    # print('A', A)
    # print('B', B)
    ans = 0
    # 日付順にソートする
    dtype = [('a', np.int), ('b', np.int)]
    ab = np.array(list(zip(A, B)), dtype=dtype)
    ab = np.sort(ab, order='a')

    works = np.zeros(ab.size, dtype=dtype)
    # print('ab=', ab)
    ans = 0
    ab_idx = 0
    works_n = 0
    for d in range(1, M+1):
        # print('d=', d)
        if ab_idx < ab.size and ab[ab_idx]['a'] == d:
            while ab_idx < ab.size and ab[ab_idx]['a'] == d:
                works[works_n] = ab[ab_idx]
                works_n += 1
                ab_idx += 1
            works[0:works_n] = np.sort(works[0:works_n], order='b')
        if works_n > 0:
            ans += works[works_n-1]['b']
            works_n -= 1

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import deque
from bisect import insort_left


# 仕事を仕事リストに追加する
# 仕事リストはポイントが大きい順、同じ仕事なら日付が多い順に並んでいる
# これを実現するため -b, -a としている
def add_work(works, ab):
    ba = (-ab[1], -ab[0])
    insort_left(works, ba)


def solve(N, M, A, B):
    ans = 0
    # 下準備 A,B をまとめ、日付順にソートする
    ab_que = deque(list(sorted(zip(A, B))))
    # 仕事リスト
    works = []
    for i in range(1, M+1):
        # 丁度間に合う仕事があれば追加する
        while ab_que and ab_que[0][0] == i:
            ab = ab_que.popleft()
            add_work(works, ab)
        # 仕事を一つする
        if works:
            ans -= works[0][0]
            works = works[1:]

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
 
 
def solve(N, M, A, B):
    ab = dict()
    for a, b in zip(A, B):
        if a in ab:
            ab[a].append(b)
        else:
            ab[a] = [b]
 
    keys = []
    for a in ab:
        ab[a] = sorted(ab[a], reverse=True)
        keys.append(a)
    keys = sorted(keys)
 
    # print('ab=', ab)
    # print('keys=', keys)
 
    total = 0
    for i in range(1, M+1):
        if i < keys[0]:
            continue
        # print('i=', i)
        mx = 0
        pos = -1
        for j in range(bisect_right(keys, i)):
            # print('  j=', j)
            key = keys[j]
            if ab[key][0] > mx:
                mx = ab[key][0]
                pos = j
        if pos >= 0:
            total += mx
            key = keys[pos]
            ab[key] = ab[key][1:]
            if len(ab[key]) == 0:
                keys = keys[0:pos] + keys[pos+1:]
                if len(keys) == 0:
                    break
            # print(' ab=', ab)
            # print(' keys=', keys)
 
    return total
 
 
if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())
 
    ans = solve(N, M, A, B)
 
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()
AB = [read_int() for _ in range(N)]
Done = [False] * N


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

    ans = 0
    for i in range(M):
        for j in range(N):
            if AB[j][0] <= M - i and not Done[j]:
                ans += AB[j][1]
                Done[j] = True
                break
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
cond = []
for i in range(n):
  a,b = map(int, input().split())
  cond.append([a,b])
cond.sort()
a = [cond[i][0] for i in range(n)] #日数
b = [cond[i][1] for i in range(n)] #賃金
money = 0
a_new = [] #日数とインデックスが一致するリスト
b_new = [] #それに対応する賃金リスト
idx_list = [] #indexのリスト
for i in range(0,max(a)+1):
  if a.count(i)==0:
    a_new.append(i)
    b_new.append(0)
    idx_list.append(0)
  else:
    idx_list.append(a.count(i))
    idx = sum(idx_list)-1
    a_new.append(i)
    b_new.append(b[idx])
    
for t in reversed(range(0,m+1)):
  b_cut = b_new[:m-t+1]
  b_max = max(b_cut)
  money += max(b_cut)
  max_idx = b_new.index(b_max)
  if a.count(max_idx)<=1:
    b_new[max_idx]=0
    idx_list[max_idx] = max(0, idx_list[max_idx]-1)
  else:
    idx_list[max_idx] -= 1
    idx_cut = idx_list[:max_idx+1]
    b_new[max_idx]=b[sum(idx_cut)-1]
    
print(money)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
cond = []
for i in range(n):
  a,b = map(int, input().split())
  cond.append([a,b])
cond.sort()
a = [cond[i][0] for i in range(n)] #日数
b = [cond[i][1] for i in range(n)] #賃金
money = 0

a_new = [] #日数条件を満たすもののみ取り出した日数リスト
start = 0
for t in reversed(range(0,m+1)):
  for i in range(start,len(a)):
    if a[i]<=m-t:
      a_new.append(a[i])
    else:
      break
  start = len(a_new)
  b_new = b[:start]
  if len(a_new)>0:
    b_max = max(b_new)
    b_max_idx = b_new.index(b_max)
    money += max(b_new)
    a.remove(a[b_max_idx])
    a_new.remove(a_new[b_max_idx])
    b.remove(b[b_max_idx])  
    start = len(a_new)

print(money)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

d = [0] * (m+1)

ab.sort(key=itemgetter(1), reverse=True)

for a, b in ab:
    x = m - a
    while x >= 0:
        if d[x] == 0:
            d[x] = b
            break
        x -= 1

print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = [int(_) for _ in input().split()]
ABs = [[] for _ in range(M + 1)]
r = 0

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

for m in range(1, M + 1):
    B_max = -1
    A_max = -1

    heapq.heapify(ABs[m])

    # print("{0}".format(m))

    for a in range(1, m + 1):
        # print("\t{0}".format(a))
        if len(ABs[a]) == 0:
            continue

        b = - ABs[a][0]
        if B_max < b:
            A_max = a
            B_max = b

    if A_max != -1:
        r -= heapq.heappop(ABs[A_max])

print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
all_work = [list(map(int, line.strip().split(' '))) for line in sys.stdin]
N,M = all_work.pop(0)
work_dict = { i:[] for i in range(1,M+1)}
for a,b in all_work:
  if a in work_dict:
    work_dict[a] += [b]

def argmax(list_):
  max_v = -float('inf')
  max_i = None
  for i,l in enumerate(list_):
    if l > max_v:
      max_v = l
      max_i = i
  return max_i, max_v

result = 0
works = []
for i in range(1,M+1):  # 残り日数
  works += work_dict[i]
  if len(works) > 0:
    max_i,max_v = argmax(works)
    works.pop(max_i)
    result += max_v

print(result)