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: Runtime Error

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []

    def merge(a, b, m):
        m = min(m, len(a) + len(b))
        res = [0] * m
        ia = len(a) - 1
        ib = len(b) - 1
        for i in range(m):
            j = m - 1 - i
            if a[ia] > b[ib]:
                res[j] = a[ia]
                ia -= 1
                if ia < 0:
                    while j >= 0:
                        res[j] = b[ib]
                        ib -= 1
                        j -= 1
            else:
                res[j] = b[ib]
                ib -= 1
                if ib < 0:
                    while j >= 0:
                        res[j] = a[ia]
                        ia -= 1
                        j -= 1
        return res

    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q = sorted(q + current)
            q = merge(q, current, M - i)
            # q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
        # q += current
        # q = sorted(q)
        # # print(q)
        # if len(q) != 0:
        #     mm = q.pop()
        #     res += mm
        # q = q[-(M - i):]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

for i in range(len(ab)-1):
    if ab[i][0]==ab[i+1][0]:
        ab[i][0]=M+1

def dfs(ab,cur,day):
    if cur==len(ab):
        return 0
    if day>M:
        return 0
    gain0 = dfs(ab,cur+1,day+ab[cur][0])+ab[cur][1]
    gain1 = dfs(ab,cur+1,day)
    return max(gain0,gain1)

min_days=ab[0][0]
if ab[0][0]>M:
    print(0)
else:
    print(dfs(ab,0,0))

Submission status: Runtime Error

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

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

pairs = sorted(pairs, key=lambda elm: [-elm[1], -elm[0]] )
#print(pairs)

finish_day = -1
out = 0

not_done = [True for _ in range(N)]

for A, B in pairs:
    for i in range(M-A, -1, -1):
        if not_done[i]:
            out += B
            #print(A, B)
            not_done[i] = False
            break

print(out)

Submission status: Runtime Error

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

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

for i in range(len(ab)-1):
    if ab[i][0]==ab[i+1][0]:
        ab[i][1]=M+1

def dfs(ab,cur,day):
    if cur==len(ab):
        return 0
    if day>M:
        return 0
    gain0 = dfs(ab,cur+1,day+ab[cur][0])+ab[cur][1]
    gain1 = dfs(ab,cur+1,day)
    return max(gain0,gain1)

min_days=ab[0][0]
if ab[0][0]>M:
    print(0)
else:
    print(dfs(ab,0,0))

Submission status: Runtime Error

Solution code:
import numpy as np

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

array = np.zeros((N, M+1), dtype=np.int32)

for i in range(N):
    a, b = map(int, input().split(' '))
    array[i, :M-a+1] = b

ans = 0
for j in reversed(range(M+1)):
    r = array[:, j].max()
    i = array[:, j].argmax()

    ans += r
    array[i] = 0

print(ans)

Submission status: Runtime Error

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

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



for i in range(len(ab)-1):
    if ab[i][0]==ab[i+1][0]:
        ab[i][1]==M+1

def dfs(ab,cur,day):
    if cur==len(ab):
        return 0
    if day>M:
        return 0
    gain0 = dfs(ab,cur+1,day+ab[cur][0])+ab[cur][1]
    gain1 = dfs(ab,cur+1,day)
    return max(gain0,gain1)

min_days=ab[0][0]
if ab[0][0]>M:
    print(0)
else:
    print(dfs(ab,0,0))

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
#最大日数は M + M-1 + M-2 + .. + 1
#最大選択数 は M個
Y = [[] for i in range(100000)]
for i in range(N):
    A, B = map(int,input().split())
    Y[A].append(B)

cnt = 0
C=[]
for i in range(1,M+1):
    if len(Y[i]) > 0:
        C.extend(Y[i])
    if len(C) > 0:
        cnt = cnt + max(C)
        C.remove(max(C))
    
print(cnt)

Submission status: Runtime Error

Solution code:
import bisect
n,m=map(int, input().split())
l={}
for i in range(n):
    a,b=map(int, input().split())
    if not a in l:
        l[a]=[b]
    else:
        l[a].append(b)

res=0
target=[0]
for i in range(1,m+1):
    if i in l:
        for j in l[i]:
            bisect.insort_left(target, j)
    val=target.pop()
    res+=val
    #print(target, max(target))

print(res)

Submission status: Runtime Error

Solution code:
from heapq import *

n, m = map(int, input().split())
hp = []
used = [0] * (m + 1)
for _ in range(n):
    a, b = map(int, input().split())
    heappush(hp, [-b, a])
while hp:
    b, a = heappop(hp)
    while a <= m:
        if used[a] == 0: break
        a += 1
    if a == m + 1:
        continue
    else:
        used[a] = -b
print(sum(used))

Submission status: Runtime Error

Solution code:
num, day = [int(x) for x in input().split()]

worklist = [[] for i in range(day)]

for i in range(num):
  d, m = [int(x) for x in input().split()]
  worklist[d-1].append(m)

ans = 0

canworklist = []

for i in range(day):
  canworklist += worklist[i]
  mm = max(canworklist)
  ans += mm
  canworklist.remove(mm)

print(ans)

Submission status: Runtime Error

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

d = dict()
for i in range(1, m+1):
    d[i] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    d[a].append(b)


ans = 0
l = []
import bisect

for i in range(1, m+1):
    for v in d[i]:
        bisect.insort(l, v)

    # print(l)

    if l != []:
        ans += l[-1]
        l.pop()
print(ans)

Submission status: Runtime Error

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

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

A.sort(reverse = True)
A.sort(key = lambda x:-x[1])

ans = 0
while(M):
    for i in range(len(A)):
        if A[i][0] <= M:
            ans += A[i][1]
            print(A[i])
            del A[i]
            break
        else:
            del A[i]
    M -= 1

print(ans)

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
c={}
for _ in range(n):
  a,b=[int(i) for i in input().split()]
  if a in c:
    c[a].append(b)
  else:
    c[a]=[b]
k=0
l=[]
for i in range(m+1):
  if i in c:
    j=sorted(c[i],reverse=True)
    if l:
      if max(j)>l[0]:
        k+=max(j)
        if len(j)>1:
          l=l+j[1:]
      else:
        k+=max(l)
        del l.index(max(l))
        l=l+j
    else:
      k+=j[0]
      l=j[1:]
  else:
    if l:
      k+=l[0]
      del l.index(max(l))
  if len(l)>m:
    l=l[:m]
print(k)

Submission status: Runtime Error

Solution code:
import heapq
N,M=(int(i) for i in input().split())



tasks=[[] for i in range(10**5+1)]
for i in range(N):
    a,b=(int(i) for i in input().split())
    tasks[a-1].append(b)

pq=[]
ans=0
for i in range(M):
    for b in tasks[i]:
        heappush(pq,b)
    if len(pq)!=0:
        ans+=heappop(pq)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())

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

work = np.array(work)
sorted_work = work[np.argsort(work[:,1])[::-1]]


avail = [0 for i in range(M)]
ans = 0
for i in range(M):
    if i < N:
        index = M-sorted_work[i][0]
        if avail[index] <= index:
            ans += sorted_work[i][1]
            for j in range(index,M):
                avail[j] += 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect


from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def check(left, right, num, max_num, data):
    half = (left + right) // 2
    kari = 0


def main():
    num, max_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    data.sort(key=lambda x: (-x[1]))

    visit = [0 for i in range(max_num + 1)]

    ans = 0
    left = 0
    # print(data)
    for i in range(num):
        day, value = data[i]
        for j in range(left, max_num + 1 - day)[::-1]:
            if visit[j] == 0:
                ans += value
                visit[j] = 1
                break
        else:
            left = max_num - day
    # print(visit)
    print(ans)







if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m = [int(x) for x in input().split()]
profits = []
for _ in range(n):
	a,b = [int(x) for x in input().split()]
    profits.append((b,a))
day = 0
pro = 0
for t in sorted(profits)[::-1]:
	if day+t[1] <= m:
      pro += t[0]
      day += 1
print(pro)

Submission status: Runtime Error

Solution code:
n = int(input())
sl = []
for _ in range(n):
    sl.append(input())
rl=[[0 for _ in range(26)] for _ in range(n)]
for i in range(n):
    for c in sl[i]:
        a=ord(c)-ord('a')
        rl[i][a]+=1
rslt=0
for i in range(n-1):
    for j in range(i+1,n):
        if rl[i] == rl[j]: rslt+=1
print(rslt)

Submission status: Runtime Error

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

delay_to_rewards = {}

for i in range(N):
    delay, reward = map(int, input().split())
    delay_to_rewards.setdefault(delay, [])
    delay_to_rewards[delay].append(reward)

for value in delay_to_rewards.values():
    value.sort(reverse=True)

#print(delay_to_rewards)

total_reward = 0
for i in range(M + 1):
    max_j = None
    max_reward = 0
    for j in range(i + 1):
        if j in delay_to_rewards:
            if max_reward < delay_to_rewards[j][0]:
                max_j, max_reward = j, delay_to_rewards[j][0]
    #print('i:', i, 'max_j, max_reward:', max_j, max_reward)
    if max_j is not None:
        total_reward += delay_to_rewards[max_j][0]
        delay_to_rewards[max_j].pop(0)
print(total_reward)

#print(delay_to_rewards)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
ab = []
for i in range(n):
    ab.append(na())

ab.sort(key=itemgetter(0))

pq = []
import  heapq

ans = 0
p = 0
for i in range(m+1):
    while p < n and ab[p][0] <= i:
        heapq.heappush(pq, -ab[p][1])
        p += 1

    if len(pq) == 0:
        continue

    ans -= heapq.heappop(pq)

print(ans)