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

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

    if a not in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)

key_all = list(d.keys())
key_all.sort()

ans = 0
l = []
import bisect

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

    # print(l)

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

Submission status: Time Limit Exceeded

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], reverse=True)

    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 = []
    for i in range(1, M + 1):
        q += ARR[i]
        q = sorted(q)
        # print(q)
        if len(q) != 0:
            mm = q.pop()
            res += mm
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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=list(reversed(sorted(c[i])))
    if l:
      if j[0]>l[0]:
        k+=j[0]
        if len(j)>1:
          l=list(reversed(sorted(l+j[1:])))
      else:
        k+=l[0]
        l=list(reversed(sorted(l[1:]+j)))
    else:
      k+=j[0]
      l=j[1:]
  else:
    if l:
      k+=l[0]
      l=l[1:]
  if len(l)>m:
    l=l[:m]
print(k)

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 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:
        target.extend(l[i])
    val=max(target)
    if val != 0:
        target.remove(val)
    res+=val

print(res)

Submission status: Time Limit Exceeded

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

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

s = [0] * (M + 1)
s[0] = 1
ret = 0
for a, b in AB :
    while a <= M :
        if s[a] == 0 :
            s[a] = 1
            ret += b
            break
        a += 1
print(ret)

Submission status: Time Limit Exceeded

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=list(reversed(sorted(c[i])))
    if l:
      if j[0]>l[0]:
        k+=j[0]
        if len(j)>1:
          l=list(reversed(sorted(l+j[1:])))
      else:
        k+=l[0]
        l=list(reversed(sorted(l[1:]+j)))
    else:
      k+=j[0]
      l=j[1:]
  else:
    if l:
      k+=l[0]
      l=l[1:]
print(k)

Submission status: Time Limit Exceeded

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(1, M + 1):
    max_j = None
    max_reward = 0
    for j in range(1, 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)
        if not delay_to_rewards[max_j]:
            delay_to_rewards.pop(max_j)
print(total_reward)

#print(delay_to_rewards)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M = map(int,input().split())
D = [[0] for i in range(10**5)]
for i in range(N):
    A,B = map(int,input().split())
    D[A-1].append(B)
count = 0
Tax = [0]
for i in range(M):
    for j in D[i]:
        bisect.insort_right(Tax,j)
    if not Tax:
        continue
    L = len(Tax)
    count += Tax.pop(L-1)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, m = map(int, input().split())
works = [[] for _ in range(10**5+1)]
for i in range(n):
    a, b = map(int, input().split())
    works[a].append(b)
reward = 0
now_works = []
for i in range(m+1):
    for kingaku in works[i]:
        index = bisect.bisect_right(now_works, kingaku)
        now_works.insert(index, kingaku)
    if not now_works:
        continue
    reward += now_works.pop(-1)
print(reward)

Submission status: Time Limit Exceeded

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

A = {}

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

total = 0
days = []
for i in range(1, M + 1):
  if i in A:
    days.extend(A[i])
    days = sorted(days)
  if len(days) > 0:
    a = len(days)
    total += days.pop()

print(total)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
work = [tuple(map(int, input().split())) for _ in range(n)]
work.sort(key = lambda x: (x[1], -x[0]), reverse = True)
do = [0] * (m+1)
money = 0
for a, b in work:
    if a > m:
        continue
    while do[a] != 0:
        a += 1
        if a > m:
            break
    if a > m:
        continue
    do[a] = 1
    money += b
print(money)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
N,M = map(int,input().split())
ls = []
for n in range(N):
  ls.append(list(map(int,input().split())))
ls = np.array(ls)
idx = np.argsort(ls[:,1])[::-1]
#print (ls[idx])
days = list(range(1,M+1))
days = {k: 0 for k in days}
#print (days)
sum = 0
for work in ls[idx]:
  d = work[0]
  while(d<=M):
    if d in days:
      sum+=work[1]
      days.pop(d)
      d=M+1
    else:
      d+=1
print (sum)

Submission status: Time Limit Exceeded

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

alist=[]

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

alist=sorted(alist)
#print(alist)

eternal=1
now=0
hoshu=0

koholist=[]
for i in range(m):
    j=i+1
    switch=1
    while switch==1 and eternal==1:
        if alist[now][0]<=j:
            koholist.append(alist[now][1])
            if now>=n-1:
                switch=0
                eternal=0
            else:
                now+=1
        else:
            switch=0
    if len(koholist)>0:
        saidai=max(koholist)
        koholist.remove(saidai)
        #print(saidai)
        hoshu+=saidai

print(hoshu)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    import heapq
    n,m = i_map()
    t = [[] for _ in range(m+1)]
    for i in range(n):
        a,b = i_map()
        if a> m:
            continue
        t[a].append(b)

    ans = 0
    h = []
    for l in t:
        for i in l:
            heapq.heappush(h, -i)
        if h:
            ans -= heapq.heappop(h)
    print(ans)






if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
 
n,m=map(int,input().split())
mm=10**5+5
c=[[0] for i in range(mm)]
 
for i in range(n):
  a,b=map(int,input().split())
  c[a].append(b)
 
#print(c)
 
ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  for j in c[d]:
    heapq.heappush(h,-j)
  #heapq.heapify(h)
  ans+=-heapq.heappop(h)
 
print(ans)

Submission status: Accepted

Solution code:
# ABC137 D
import heapq

N,M=map(int,input().split())
AB=[]
for _ in [0]*N:
    a,b=map(int,input().split())
    AB.append((-a,-b))
AB.sort()
AB=[(-a,-b) for a,b in AB]

res=0
num=0
work=[]
hard=[0]*(M+1)
for a,b in AB:
    #a日後のしごとの話をしている→M-a+1件まで受注可能
    if num<M-a+1:
        # 仕事に余裕はある
        heapq.heappush(work,(b,a))
        hard[a]+=1
        res+=b
        num+=1
    else:
        # 仕事は十分持っている
        heapq.heappush(work,(b,a))
        c,d=heapq.heappop(work)
        res+=b-c
print(res)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
mm=10**5+5
c=[[0] for i in range(mm)]

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

#print(c)

ans=0
h=[]
for i in reversed(range(m)):
  d=m-i
  for j in c[d]:
    heapq.heappush(h,-j)
  #heapq.heapify(h)
  ans+=-heapq.heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    data = {}
    priorityQ = []
    for _ in range(n):
        a, b = map(int, input().split())
        if a <= m:
            if a in data:
                data[a].append(b)
            else:
                data[a] = [b]
    ans = 0
    for i in range(1, m+1):
        if i in data.keys():
            for k in data[i]:
                heapq.heappush(priorityQ, -k)
        if priorityQ:
            ans -= heapq.heappop(priorityQ)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    data = {}
    priorityQ = []
    for _ in range(n):
        a, b = map(int, input().split())
        if m + 1 - a >= 0:
            if m+1-a in data:
                data[m+1-a].append(b)
            else:
                data[m+1-a] = [b]
    ans = 0
    for i in range(m, 0, -1):
        if i in data.keys():
            for k in data[i]:
                heapq.heappush(priorityQ, -k)
        if priorityQ:
            ans -= heapq.heappop(priorityQ)
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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
        for money in d[diff]:
            heapq.heappush(cand, money)
        if cand:
            ans -= heapq.heappop(cand)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import *
N,M = map(int,input().split())
L = [[] for m in range(M)]
H = []
ans = 0

for n in range(N):
  a,b = map(int,input().split())
  if a<=M:
    L[M-a]+=[b]
    
for m in range(M-1,-1,-1):
  for l in L[m][::-1]:
    heappush(H,-l)
  if 0<len(H):
    ans-=heappop(H)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
byte = [[] for _ in range(m+2)]

for _ in range(n):
    a, b = map(int, input().split())
    if a > m+1:
        continue
    byte[a].append(b)
search = []
day = 1
ans = 0
while day-1 != m:
    for b in byte[day]:
        heapq.heappush(search, -b)
    if not search:
        day += 1
        continue
    tmp = -heapq.heappop(search)
    ans += tmp
    day += 1

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
byte = [[] for _ in range(100001)]

for _ in range(n):
    a, b = map(int, input().split())
    byte[a].append(b)
search = []
day = 1
ans = 0
while day-1 != m:
    for b in byte[day]:
        heapq.heappush(search, -b)
    if not search:
        day += 1
        continue
    tmp = -heapq.heappop(search)
    ans += tmp
    day += 1

print(ans)

Submission status: Accepted

Solution code:
"""
Aの値が大きいものからheapqにぶち込んでいけばよい。
"""
from heapq import heappop,heappush
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(reverse=True)
que = []
for a,b in AB:
    if M >= a:
        heappush(que,b)
        M -= 1
    elif que:
        if que[0] < b:
            heappop(que)
            heappush(que,b)
print(sum(que))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
t=[[] for _ in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    if a>m:
        continue
    t[a].append(b)
ans=0
h=[]
for l in t:
    for i in l:
        heapq.heappush(h,-i)
    if h:
        ans-=heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
job_list=[]
for i in range(n):
    tmp=[int(x) for x in input().split()]
    job_list.append(tmp)
job_list.sort()

import heapq
k=0
ans=0
salary_list=[]
for i in range(1,m+1):
    while k<n and job_list[k][0]==i:
        heapq.heappush(salary_list,job_list[k][1]*(-1))
        k+=1
    if len(salary_list)>0:
        ans+=heapq.heappop(salary_list)
print((-1)*ans)

Submission status: Accepted

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 = [i for i in range(M+1)]
ans = 0
for a, b in AB:
    i = a
    while i < (M + 1) and plan[i] != i:
        plan[i] += 1
        i = plan[i] -1
    if i < (M+1):
        plan[i] += 1
        ans += b
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

# A が小さい順に増えていく
result = 0
que = [] # ヒープ
for Bs in AtoB:
    for B in Bs:
        heappush(que, -B) # Python3 のヒープはデフォルトで小さい順
    if que:
        result -= heappop(que)
print(result)

Submission status: Accepted

Solution code:
import heapq

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


rinsetuList = [[] for _ in range(100001)]

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

#print(rinsetuList[:M+1])

work_list = []
hpq = heapq.heapify(work_list)

ans = 0
for rinsetu in rinsetuList[:M+1]:
    for money in rinsetu:
        heapq.heappush(work_list, money * (-1))
    if(len(work_list) != 0):
        ans += heapq.heappop(work_list) * (-1)

#    print(ans)
#    print(work_list)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

c = []
ans = 0
for i in range(m):
    while len(ab) != 0 and ab[-1][0] <= i+1:
        _, b = ab.pop()
        heapq.heappush(c, -b)
    if c:
        ans += -heapq.heappop(c)
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M=mi()
    X = defaultdict(lambda: [])
    for i in range(N):
        a,b=mi()
        X[a].append(b)
    
    Y = []
    heapq.heapify(Y)
    ans = 0
    for x in reversed(range(M)):
        ok = M-x
        for x in X[ok]:
            heapq.heappush(Y,-1 * x)
        
        if Y:
            y = heapq.heappop(Y)
            y *= -1
            ans += y

    print(ans)


    


if __name__ == "__main__":
    main()

Submission status: Accepted

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

jobs = [[] for i in range(10**5+1)]

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

candidate = []
ans = 0
for i in range(m+1):
    for j in jobs[i]:
        heapq.heappush(candidate, -j)

    # print(i, candidate)
    if len(candidate) >= 1:
        ans += heapq.heappop(candidate) * -1


print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(n)]
ans = 0
c = 0
ab.sort(key = lambda x: (x[0], -x[1]))
from heapq import heappop as hpp, heappush as hp
class HST:
    def __init__(self, ascending=True):
        self._h = []
        self._q = []
        self.ascending = ascending
    def push(self, v):
        if not self.ascending:
            v *= -1
        hp(self._h, v)
    def remove(self, v):
        if not self.ascending:
            v *= -1
        hp(self._q, v)
    def top(self):
        while self._q and self._q[0]==self._h[0]:
            hpp(self._q)
            hpp(self._h)
        if not self._h:
            res = None
        else:
            res = self._h[0]
            if not self.ascending:
                res *= -1
        return res
h = HST(ascending=False)
ans = 0
ab = ab[::-1]
# print(ab)
for c in range(m, -1, -1):
    while ab and ab[-1][0]+c<=m:
        a,b = ab.pop()
        h.push(b)
    val = h.top()
    if val is not None:
        ans += val
        h.remove(val)
print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
d=[]
ab=sorted(ab,key=lambda x: x[0])
ans=0
j=0
for i in range(m):
    for k in range(j,n):
        if ab[k][0]>i+1:
            j=k
            break
        heapq.heappush(d,(-1)*ab[k][1])
    else:
      j=n
    if not d:
        continue
    res=heapq.heappop(d)*(-1)
    ans+=res
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from operator import itemgetter
import heapq

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

q = deque(jobs)
r = []

heapq.heapify(r)

res = 0
for i in range(M):
    while q:
        job = q.popleft()
        if job[0] > i + 1:
            q.appendleft(job)
            break
        else:
            heapq.heappush(r, -job[1])

    if len(r) >= 1:
        res -= heapq.heappop(r)

print(res)

Submission status: Accepted

Solution code:
"""
案件を報酬を受け取るまでにかかる時間で降順ソートしておく。
"""
class segTree:
    def __init__(self,n,identity):
        if bin(n).count("1") == 1:
            self.leaves = 2**(n.bit_length()-1)
        else:
            self.leaves = 2**n.bit_length()
        self.identity = identity
        self.tree = [[self.identity,-1] for i in range(self.leaves*2)]
        for i in range(self.leaves,self.leaves*2):
            self.tree[i] = [self.identity,i-self.leaves]

    def merge(self,x,y):
        #ここにマージ処理を書く
        if x[0] < y[0]:
            return x[::1]
        else:
            return y[::1]

    def update(self,i,x):
        i = i+self.leaves
        self.tree[i][0] = x
        i >>= 1
        while i > 0:
            self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
            i >>= 1

    def query(self,l,r):
        #[l:r)のクエリ結果を返す
        l = l + self.leaves
        r = r + self.leaves
        res = [self.identity,-1]
        while l < r:
            if l&1:
                res = self.merge(res,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                res = self.merge(res,self.tree[r])
            l >>= 1
            r >>= 1
        return res

N,M = map(int,input().split())
M += 1
sgt = segTree(N,float("INF"))
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x: -x[0])

today = 1
for i in range(N):
    a,b = AB[i]
    due = M-a
    #M日までに報酬を受け取るためには、何日までに働かなくてはいけないかを求める。

    if today <= due:
        #今日の日付がdue以下であれば、今日その仕事をこなす
        sgt.update(today-1,b)
        today += 1
    else:
        if due < 1:
            continue
        #今日の日付がdueを過ぎてしまっている場合は、due以前の労働で報酬がb以下の仕事のうち、報酬がもっとも低い仕事を塗り替える。
        tmp = sgt.query(0,due)
        if tmp[0] < b:
            sgt.update(tmp[1],b)
        
ans = 0
for i in range(N):
    if sgt.tree[i+sgt.leaves][0] != float("INF"):
        ans += sgt.tree[i+sgt.leaves][0]
print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
ab.sort()
ans = 0
num = 0
queue = []
heapq.heapify(queue)
for i in range(1, m + 1):
    if num < n:
        while ab[num][0] <= i:
            heapq.heappush(queue, [-ab[num][1], ab[num][0]])
            num += 1
            if num == n:
                break
    if len(queue):
        temp = heapq.heappop(queue)
        ans += -temp[0]
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    AB = [LI() for _ in range(N)]

    W = [[] for _ in range(M + 1)]
    for a, b in AB:
        if 0 <= M - a:
            W[M-a].append(b)
    # print(W)

    # 選択肢の少ない後ろの日付から決めていく
    ans = 0
    hq = []
    for i in reversed(W):
        for j in i:
            heapq.heappush(hq, -j)
        if hq:
            ans -= heapq.heappop(hq)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:

import sys

icase=0
if icase==0:
    n,m=map(int,input().split())
    ab=[[] for i in range(m)]
    for i in range(n):
        ai,bi=map(int,input().split())
        if m-ai>=0:
            ab[m-ai].append(-bi)
elif icase==1:
    n,m=3,4
    ab=[[-3, -1], [], [-2], []]    
elif icase==2:
    n,m=5,3
    ab=[[], [-1, -3], [-2, -3, -4]]
elif icase==3:
    n,m=1,1
    ab=[[]]

from heapq import heappop,heappush

if len(ab)==0:
    print(0)
    sys.exit()

n=len(ab)
h=[]
asum=0
for i in range(m-1,-1,-1):
    if len(ab[i])>0:
        for abi in ab[i]:
            heappush(h,abi)
#    print(i,h,asum)
    if len(h)>0:
        asum+=heappop(h)

print(-asum)

Submission status: Accepted

Solution code:
import sys

icase=0
if icase==0:
    n,m=map(int,input().split())
    ab=[[] for i in range(m)]
    for i in range(n):
        ai,bi=map(int,input().split())
        if m-ai>=0:
            ab[m-ai].append(-bi)
elif icase==1:
    n,m=3,4
    ab=[[-3, -1], [], [-2], []]    
elif icase==2:
    n,m=5,3
    ab=[[], [-1, -3], [-2, -3, -4]]
elif icase==3:
    n,m=1,1
    ab=[[]]

from heapq import heappop,heappush

if len(ab)==0:
    print(0)
    sys.exit()

n=len(ab)
h=[]
asum=0
for i in range(m-1,-1,-1):
    if len(ab[i])>0:
        for abi in ab[i]:
            heappush(h,abi)
#    print(i,h,asum)
    if len(h)>0:
        asum+=heappop(h)

print(-asum)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
w=[[] for i in range(m)]
for i in range(n):
  a,b=map(int,input().split())
  a-=1
  if a>=m:
    continue
  w[a].append(-b)

h=[]
c=0
for i in range(m):
  for j in w[i]:
    heapq.heappush(h,j)
  try:
    c+=heapq.heappop(h)
  except:
    pass
print(-c)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
memo = [[] for _ in range(m+1)]

for _ in range(n):
    a, b = map(int ,input().split())
    if a <= m:
        memo[a].append(-b)

ans = 0
HQ = []
heapq.heapify(HQ)
for i in range(1, m+1):
    for j in memo[i]:
        heapq.heappush(HQ, j)
    if HQ:
        ans += heapq.heappop(HQ)

print(-ans)

Submission status: Accepted

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: Accepted

Solution code:
from heapq import heappop, heapify, heappush


def main():
    n, m = map(int, input().split())
    work = [[] for _ in range(10 ** 5 + 1)]
    for _ in range(n):
        a, b = map(int, input().split())
        work[a].append(b)
    ans = 0
    q = []
    heapify(q)
    for i in range(1, m + 1):
        for w in work[i]:
            heappush(q, -w)
        if len(q) == 0:
            continue
        ans += heappop(q)
    ans *= -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

print(ans)

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
import numpy as np
import heapq
from collections import defaultdict
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def lcm(a, b):
    return a*b//math.gcd(a, b)


def main():
    N, M = mi()
    A, B = i2(N)
    ans = 0

    d = defaultdict(list)
    for i in range(N):
        d[A[i]].append(B[i])

    h = []
    heapq.heapify(h)

    for i in range(1, M+1):
        for v in d[i]:
            heapq.heappush(h, -v)
        if h:
            ans -= heapq.heappop(h)
        else:
            continue

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

task = []
heapq.heapify(task)

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

A = [[] for i in range(M+1)]
for i in range(N):
    a, b = map(int, input().split())
    if a > M: continue
    A[a].append(b)

ans = 0
for i in range(1,M+1):
    for b in A[i]:
        heapq.heappush(task, -b)
    if len(task) > 0:
        ans += heapq.heappop(task)*(-1)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

a=[[] for _ in range(m)]

d=[]

heapq.heapify(d)

for i in range(n):
  x,y=map(int,input().split())
  if x<=m:
    a[x-1].append(-y)
    
ans=0

for j in range(1,m+1):
  for h in a[j-1]:
    heapq.heappush(d,h)
  if len(d)>0:
    c=heapq.heappop(d)
    ans+=c
  
print(ans*(-1))

Submission status: Accepted

Solution code:
import heapq


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    AB = []
    for _ in range(N):
        AB.append(read_ints())
    AB.sort(reverse=True)
    rewards = []
    total = 0
    for i in range(M):
        while AB and AB[-1][0] <= i+1:
            a, b = AB.pop()
            heapq.heappush(rewards, -b)
        if rewards:
            total += -heapq.heappop(rewards)
    return total


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

Submission status: Accepted

Solution code:
import heapq
import sys


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    jobs = [tuple(map(int, input().split())) for _ in range(n)]
    jobs.sort()

    ans = 0
    index = 0
    hq = []
    # 働くのは0からm-1日後
    for i in range(m - 1, -1, -1):
        while index < n and i + jobs[index][0] <= m:
            heapq.heappush(hq, -jobs[index][1])
            index += 1
            if index == n:
                break
        if not hq:
            continue
        ans -= heapq.heappop(hq)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import*
n,m=map(int,input().split())
x=[[]for _ in range(m)]
for _ in range(n):
  a,b=map(int,input().split())
  if a<=m:x[a-1]+=[-b]
q=[]
ans=0
for i in range(m):
  for j in x[i]:heappush(q,j)
  if q:ans-=heappop(q)
print(ans)