Problem:


Score : 400 points

Problem Statement

There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.

You can take and complete at most one of these jobs in a day.

However, you cannot retake a job that you have already done.

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

You can already start working today.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i \leq 10^5

1 \leq B_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

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

Sample Input 1

3 4
4 3
4 1
2 2

Sample Output 1

5

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

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

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

Sample Input 2

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

Sample Output 2

10

Sample Input 3

1 1
2 1

Sample Output 3

0



Sample input:
3 4
4 3
4 1
2 2


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    # print(d)
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                if d[bi] and d[bi][-1] <= m-i:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)

    return ans

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ans = 0

    for i in range(1, m + 1):
        H = []
        for j, e in enumerate(ab):
            if e[0] <= i:
                heappush(H, (-e[1], j))

        if H:
            e = heappop(H)
            ans -= e[0]
            ab.pop(e[1])

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Time Limit Exceeded

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from queue import PriorityQueue
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        # convert horizontal to vertical
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    # if return value has one and only one element(list),
    if wint == 1:
        # then add an empty list.
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    # destructive.
    for i in range(len(lst)):
        lst[i] = value


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    # read here
    (n, m) = hints()[0]
    ab_s = hints(n)

    # solve here

    # delay asc, prize desc
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = PriorityQueue()
    for t in range(m + 1):
        # from (m days after) to today
        while ab_s and ab_s[0][0] == t:
            a, b = ab_s.pop(0)
            tasks.put(-b)
        if not tasks.empty():
            # do task
            ans -= tasks.get()

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in [0]*n]
l.sort(key=lambda x:x[0])
ans = 0
tmpl = []
flag = True
i = 0
for d in range(1,m+1):
  while i<=n-1 and l[i][0] <= d:
    tmpl.append(l[i][1])
    i += 1
  if len(tmpl) > 0:
    maxindex = tmpl.index(max(tmpl))
    ans += tmpl[maxindex]
    del tmpl[maxindex]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ab = sorted(ab)
    ans = 0

    for i in range(1, m + 1):
        H = []
        for j, e in enumerate(ab):
            if e[0] <= i:
                heappush(H, (-e[1], j))
            else:
                break

        if H:
            e = heappop(H)
            ans -= e[0]
            ab.pop(e[1])

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
job_list = {}
ans = 0
kouho = []
for _ in range(N):
  A, B = map(int, input().split())
  B = B * (-1)
  if A in job_list.keys():
    job_list[A].append(B)
  else:
    job_list[A] = [B]

for day in range(1, M + 1):
  try: 
    kouho += job_list[day]
    heapq.heapify(kouho)
  except KeyError:
    pass
  if len(kouho) != 0:
    ans += heapq.heappop(kouho)

print(ans * (-1))

Submission status: Time Limit Exceeded

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from queue import PriorityQueue
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        # convert horizontal to vertical
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    # if return value has one and only one element(list),
    if wint == 1:
        # then add an empty list.
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    # destructive.
    for i in range(len(lst)):
        lst[i] = value


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    # read here
    (n, m) = hints()[0]
    ab_s = hints(n)

    # solve here

    # delay asc, prize desc
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = PriorityQueue(n)
    for t in range(m + 1):
        # from (m days after) to today
        while ab_s and ab_s[0][0] == t:
            a, b = ab_s.pop(0)
            tasks.put(-b)
        if not tasks.empty():
            # do task
            ans -= tasks.get(0)

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:-x[1])
ans=0
for i in range(m):
    ltmp=[j for j in l if j[0]<=i+1]
    if len(ltmp)>0:
        ans+=ltmp[0][1]
        l.remove(ltmp[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from queue import PriorityQueue
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        # convert horizontal to vertical
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    # if return value has one and only one element(list),
    if wint == 1:
        # then add an empty list.
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    # destructive.
    for i in range(len(lst)):
        lst[i] = value


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    # read here
    (n, m) = hints()[0]
    ab_s = hints(n)

    # solve here

    # delay asc, prize desc
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = PriorityQueue()
    for t in range(m + 1):
        # from (m days after) to today
        while ab_s and ab_s[0][0] == t:
            a, b = ab_s.pop(0)
            tasks.put(-b)
        if not tasks.empty():
            # do task
            ans -= tasks.get(0)

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

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())
    if a in L:
        L[a].append(b)
    else:
        L[a]=[b]

ans=0
tab=[0 for i in range(m)]
for i in range(m):
    if i+1 in L:
        tab.extend(L[i+1])
    tmax=max(tab)
    ans+=tmax
    tab.remove(tmax)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = [[] for _ in range(10**5 + 1)]

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

p = []
ans = 0

for m in range(1, M+1):
    p += P[m]
    if p:
        max_b = max(p)
        ans += max_b
        p.remove(max_b)

print(ans)