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

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


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

JOBS = {i:[] for i in range(1, m + 1)}
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        JOBS[a].append(b)

answer = 0
REWARDS = []
heapify(REWARDS)
for i in range(1, m + 1):
    for reward in JOBS[i]:
        heappush(REWARDS, -reward)
    if len(REWARDS) > 0:
        reward = -heappop(REWARDS)
        answer += reward

print(answer)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(n)]
points.sort()

ans = 0
i = 0
days = 0
heap = []
while days <= m:
    while i < len(points) and points[i][0] <= days:
        d, p = points[i]
        heapq.heappush(heap, -p)
        i += 1

    days += 1
    if heap: ans += heapq.heappop(heap)

print(-ans)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()

Ws=[]
for i in range(N):
    a,b=LI()
    Ws.append((a,b))
Ws.sort()

cur = 0
HQ=[]
res = 0

for rest in range(1,M+1):
    while cur < N and Ws[cur][0] <= rest:
        heapq.heappush(HQ, -Ws[cur][1])
        cur += 1

    if HQ:
        nagated_gain = heapq.heappop(HQ)
        # print("debug: {} {}".format(rest, -nagated_gain))
        res -= nagated_gain

print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
import heapq as hq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab.sort()
ls = []
hq.heapify(ls)
k = max([a[0] for a in ab]+[m])
daylist = [0]*(k+1)
for i in range(n):
  daylist[ab[i][0]] += 1
daylistsum = list(accumulate(daylist))
ans = 0
for i in range(1,m+1):
  for j in range(daylistsum[i-1],daylistsum[i]):
    hq.heappush(ls,-ab[j][1])
  if ls:
    ans -= hq.heappop(ls)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    from heapq import heapify, heappop, heappush
    from collections import defaultdict
    sche = defaultdict(list)
    for i in range(N):
        a, b = (int(i) for i in input().split())
        sche[a].append(b)

    q = []
    heapify(q)

    ans = 0
    for i in range(1, M+1):
        for s in sche[i]:
            heappush(q, -s)
        if q:
            ans += -heappop(q)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

fee = [[] for _ in range(10**5+10)]  # i日後に収入がもらえるバイトの価値
for _ in range(N):
    a, b = map(int, input().split())
    fee[a].append(-b)

task = []
ans = 0

# 締め切り日からさかのぼっていって、できるバイトで最大の収入をもらえるやつを実行する感じ
for i in range(1, M + 1):
    for f in fee[i]:
        heapq.heappush(task, f)

    if task:
        ans -= heapq.heappop(task)

print(ans)

Submission status: Accepted

Solution code:
import heapq

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])
h=[0]*M
heapq.heapify(h)

out=0
j=0
for i in range(1, M+1):
  while j<N and AB[j][0]<=i:
    heapq.heappush(h, -1*AB[j][1])
    j+=1
    
  out+=-1*heapq.heappop(h)
  
print(out)

Submission status: Accepted

Solution code:
#最終日から見る，残り日数条件を満たす中で最大収入のものを選ぶ

import heapq

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

for i in range(N):
    AB[i][0],AB[i][1] = map(int,input().split())

AB.sort()

ans=0
q=[]
heapq.heapify(q)
ne=0
#dは残り日数
for d in range(1,M+1):
    for i in range(ne,N):
        if AB[i][0]<=d:
            heapq.heappush(q,AB[i][1]*-1)
            ne=i+1
        else:
            break
    if len(q)!=0:
        a=heapq.heappop(q)
        ans-=a
    
print(ans)

Submission status: Accepted

Solution code:
# ABC-137-D
import heapq

N, M = map(int, input().split())
day_value = [[] for _ in range(M+1)]

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

ans = 0
check_M = 1
BA = []
heapq.heapify(BA)

while check_M <= M:
    for item in day_value[check_M]:
        heapq.heappush(BA, -1*item)
    try:
        max_B = heapq.heappop(BA)
    except:
        check_M += 1
        continue
    ans += (-1) * max_B
    check_M += 1
print(ans)

Submission status: Accepted

Solution code:
# ABC137D - Summer Vacation
import sys
from heapq import heappop, heappush

read = sys.stdin.buffer.read
heappop_max = lambda heap: -heappop(heap)
heappush_max = lambda heap, x: heappush(heap, -x)


def main():
    N, M, *all_jobs = map(int, read().split())
    available_jobs = [[] for _ in range(M + 1)]
    for waiting_days, reward in zip(*[iter(all_jobs)] * 2):
        if waiting_days <= M:
            available_jobs[waiting_days].append(reward)
    heap = []
    max_rewards = 0
    for jobs in available_jobs[1:]:
        for job in jobs:
            heappush_max(heap, job)
        if heap:
            max_rewards += heappop_max(heap)
    print(max_rewards)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC137D - Summer Vacation
import sys
from heapq import heappop, heappush

readline = sys.stdin.buffer.readline
heappop_max = lambda heap: -heappop(heap)
heappush_max = lambda heap, x: heappush(heap, -x)


def main():
    N, M = map(int, readline().split())
    available_jobs = [[] for _ in range(M + 1)]
    for _ in range(N):
        waiting_days, reward = map(int, readline().split())
        if waiting_days <= M:
            available_jobs[waiting_days].append(reward)
    heap = []
    max_rewards = 0
    for jobs in available_jobs[1:]:
        for job in jobs:
            heappush_max(heap, job)
        if heap:
            max_rewards += heappop_max(heap)
    print(max_rewards)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC137D - Summer Vacation
import sys
from heapq import heappop, heappush

readline = sys.stdin.buffer.readline
heappop_max = lambda heap: -heappop(heap)
heappush_max = lambda heap, x: heappush(heap, -x)


def main():
    N, M = map(int, readline().split())
    all_jobs = tuple(tuple(map(int, readline().split())) for _ in range(N))
    available_jobs = [[] for _ in range(M + 1)]
    for waiting_days, reward in all_jobs:
        if waiting_days <= M:
            available_jobs[waiting_days].append(reward)
    heap = []
    max_rewards = 0
    for jobs in available_jobs[1:]:
        for job in jobs:
            heappush_max(heap, job)
        if heap:
            max_rewards += heappop_max(heap)
    print(max_rewards)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC137D - Summer Vacation
from heapq import heappop, heappush

heappop_max = lambda heap: -heappop(heap)
heappush_max = lambda heap, x: heappush(heap, -x)


def main():
    N, M = map(int, input().split())
    all_jobs = tuple(tuple(map(int, input().split())) for _ in range(N))
    available_jobs = [[] for _ in range(M + 1)]
    for waiting_days, reward in all_jobs:
        if waiting_days <= M:
            available_jobs[waiting_days].append(reward)
    heap = []
    max_rewards = 0
    for jobs in available_jobs[1:]:
        for job in jobs:
            heappush_max(heap, job)
        if heap:
            max_rewards += heappop_max(heap)
    print(max_rewards)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019/12/27

from heapq import heapify,heappop,heappush
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:continue
    ab[a].append(-b)

que=[]
heapify(que)
ans=0
for i in range(1,m+1):
    if ab[i]:
        for e in ab[i]:
            heappush(que,e)
    if que:
        ans+=heappop(que)

print(-ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    aa = sorted([LI() for _ in range(n)]) + [[inf,0]]
    r = 0
    q = []
    ai = 0
    for i in range(m+1):
        while aa[ai][0] <= i:
            heapq.heappush(q,-aa[ai][1])
            ai += 1
        if len(q) > 0:
            t = heapq.heappop(q)
            r -= t

    return r


print(main())

Submission status: Accepted

Solution code:
from heapq import heappush, heappushpop

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

tasks = [[] for _ in range(M)]

for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        tasks[M-a].append(b)
q = []
for day in range(M):
    for v in tasks[day]:
        if len(q) < day + 1:
            heappush(q, v)
        else:
            heappushpop(q, v)
ans = sum(q)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import heapq
    n,m = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    q = []
    ans = 0
    now = 0
    for i in range(1,m+1):
        for j in range(now,n):
            if l[j][0] <= i:
                heapq.heappush(q,-l[j][1])
                now = j+1 
            else:
                now = j
                break
        if q:
            ans -= heapq.heappop(q)
       
    print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
Cs = []
for _ in range(N):
    a, b = map(int, input().split())
    Cs.append((M-a, b))
Cs.sort()
Ds = []
r = 0
for i in range(M):
    j = M - i -1
    while True:
        if not len(Cs):
            break
        if Cs[-1][0] < j:
            break
        heappush(Ds, -Cs.pop()[1])
    if len(Ds):
        s = -heappop(Ds)
        r += s
print(r)

Submission status: Accepted

Solution code:
import heapq

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

ans = 0
candidates = []
now = 0
for i in range(M+1):
  for j in range(now, N):
    if AB[j][0] <= i:
      heapq.heappush(candidates, -AB[j][1])
      now = j + 1
      
    else:
      now = j
      break
  
  if candidates:
    ans -= heapq.heappop(candidates)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
earn = 0
AB.sort(key=lambda x:x[0])
pos=0
cando=[]
for remain in range(M+1):
    for i in range(pos,len(AB)):
        if AB[i][0] <= remain:
            heapq.heappush(cando, -AB[i][1])
            pos=i+1
        else:
            pos=i
            break
    if cando:
        earn-=heapq.heappop(cando)
print(earn)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
queue = []
flag = 0
heapq.heapify(queue)
ans = 0
for i in range(1,m+1):
  for j in range(flag,n):
    if ab[j][0] <= i:
      heapq.heappush(queue,-ab[j][1])
      flag += 1
    else:
      break
  if queue != []:
    k = heapq.heappop(queue)
    ans += k
print(-ans)

Submission status: Accepted

Solution code:
import sys
import collections
import heapq


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    ab = [list(map(int, readline().split())) for _ in range(n)]
    ab.sort()
    ab = collections.deque(ab)
    hq = []
    heapq.heapify(hq)
    t = 0
    for i in range(1, m + 1):
        while len(ab):
            if len(ab) != 0:
                if ab[0][0] <= i:
                    heapq.heappush(hq, -ab.popleft()[1])
                else:
                    break
            else:
                break
        if len(hq) != 0:
            t -= heapq.heappop(hq)
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import heapq
from collections import deque

class job:
    def __init__(self,date,award):
        self.award=award
        self.date=date
    def __gt__(self,other):
        if self.award<other.award:
            return True
#         elif self.award==other.award and self.date>other.date:
#             return True
#         elif self.award==other.award and self.date==other.date and self.name>other.name:
#             return True
        else:
            return False
    def __lt__(self,other):
        if self.award>other.award:
            return True
#         elif self.date==other.date and self.award>other.award:
#             return True
#         elif self.award==other.award and self.date==other.date and self.name<other.name:
#             return False
        else:
            return False
    def __eq__(self,other):
        if self.award==other.award:
            return True
        else:
            return False

jobs=[]
n,m=[int(i) for i in input().split()]
for i in range(n):
    info=[int(j) for j in input().split()]
    jobs.append(info)
jobs.sort()

jobdeque=deque()
for i in jobs:
    jobdeque.append(i)
    
ans=0
heap=[]
heapq.heapify(heap)
for i in range(m):
    while jobdeque:
        a=jobdeque.popleft()
        if a[0]==i+1:
            heapq.heappush(heap,job(a[0],a[1]))
        else:
            jobdeque.appendleft(a)
            break
    if heap:
        b=heapq.heappop(heap)
        ans+=b.award
                          
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

ans = 0
q = []
for m in range(1, M + 1):
    for j in J_day[m]:
        heappush(q, -j)
    if len(q):
        ans -= heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq


n, m = [int(_) for _ in input().split()]
l = []
for i in range(n):
    a, b = [int(_) for _ in input().split()]
    l.append((a, b))
l = sorted(l, reverse=True)
# print(l)

ans = 0
que = []
heapq.heapify(que)
i = 1
while i <= m:
    if len(l) != 0:
        while l[-1][0] == i:
            a, b = l.pop()
            heapq.heappush(que, -b)
            if len(l) == 0:
                break
    # print('i', i)
    # print('que', que)
    # print('ans', ans)
    if len(que) != 0:
        ans += (-1) * heapq.heappop(que)
    i += 1
# print(que)
print(ans)

Submission status: Accepted

Solution code:
# 2019/12/27

from heapq import heapify,heappop,heappush
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:continue
    ab[a].append(-b)

que=[]
heapify(que)
ans=0
for i in range(1,m+1):
    if ab[i]:
        for e in ab[i]:
            heappush(que,e)
    if que:
        ans+=heappop(que)

print(-ans)

Submission status: Accepted

Solution code:
import heapq

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

AB.sort()
#print("AB:", AB)

H = []
iab = 0
answer = 0
for i in range(M + 1):
  while iab <= N - 1 and AB[iab][0] <= i:
    heapq.heappush(H, -AB[iab][1])
    iab += 1
  if len(H):
    answer += heapq.heappop(H)
print(-answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop,heappush
def resolve():
    n,m=map(int,input().split())
    AB=[None]*n
    for i in range(n):
        a,b=map(int,input().split())
        a-=1
        AB[i]=(a,b)
    AB.sort(reverse=1)

    Q=[]
    ans=0
    for d in range(m):
        while(AB and AB[-1][0]<=d):
            a,b=AB.pop()
            heappush(Q,-b)
        if(Q):
            ans+=heappop(Q)

    print(-ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from heapq import heappop,heappush
def resolve():
    n,m=map(int,input().split())
    V=[[] for _ in range(m)]
    for _ in range(n):
        a,b=map(int,input().split())
        if(a>m): continue
        heappush(V[a-1],-b)


    ans=0
    Q=[]
    for d in range(m):
        if(V[d]):
            heappush(Q,(heappop(V[d]),d))
        if(Q):
            b,a=heappop(Q)
            ans+=-b
            if(V[a]):
                heappush(Q,(heappop(V[a]),a))

    print(ans)
resolve()

Submission status: Accepted

Solution code:
import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

from collections import defaultdict

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

if __name__ == "__main__":

    ans = 0
    pq = PriorytyQueue([], target='max')
    for d in range(1, M+1):
        if d in jobs.keys():
            moneys = jobs[d]
            for money in moneys:
                pq.push(money)
        if not(pq.is_empty()):
            ans += pq.pop()
    print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

N,M = [int(k) for k in sys.stdin.readline().split()]

job=[]
for i in range(N):
    A,B = [int(k) for k in sys.stdin.readline().split()]
    job.append((A,-B))

job.sort(key=lambda t: -t[0])

heap=[]
heapq.heapify(heap)

ans=0

for i in range(1,M+1):
    if len(job)!=0:
      while job[-1][0]==i:
          heapq.heappush(heap,job.pop()[1])
          if len(job)==0:
             break
    if len(heap) == 0:
        continue
    ans -= heapq.heappop(heap)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    d={}
    for i in range(N):
        A,B=map(int,input().split())
        if A in d:
            d[A].append(B)
        else:
            d[A]=[B]
    h=[]
    ans=0
    for i in range(1,M+1):
        if i in d:
            l=d[i]
            for x in l:
                heappush(h,-x)
        if h:
            ans-=heappop(h)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import defaultdict


def main():
    input = sys.stdin.readline
    
    N, M = map(int, input().split())

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

    candidate = []
    heapq.heapify(candidate)

    ret = 0

    for i in range(1, M+1):
        for value in table[i]:
            heapq.heappush(candidate, value)
        if len(candidate) > 0:
            ret -= heapq.heappop(candidate)

    print(ret)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

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

que = []
ans = 0
for i in range(1, M+1):
    if len(baito[i]) != 0:
        for val in baito[i]:
            heapq.heappush(que, val*-1)
    if len(que) != 0:
        ans += heapq.heappop(que)*-1

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
day = [[] for _ in range(10**5+1)]
for _ in range(n):
    a, b = map(int, input().split())
    day[a].append(b)
benefit = []
heapq.heapify(benefit)
ans = 0
for i in range(1, m+1):
    for j in day[i]:
        heapq.heappush(benefit, -j)
    if benefit:
        ans -= heapq.heappop(benefit)  # 最大値を加算
print(ans)

Submission status: Accepted

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

a=[]
ans, j = 0, 0

for i in range(1, M + 1):
  #M-1~Mから0~MまでのM日間について後ろから考える
  while (j < N) and (X[j][0] <= i):
    #i=1　1日で報酬が受け取れるものを取り出し最大の物をプラス　2日以内で報酬が…の繰り返し
    heapq.heappush(a, -X[j][1])  
    j += 1
  if len(a):
    ans += -heapq.heappop(a)  
    
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import groupby
from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
ABg = [(a, list(it))for a, it in groupby(AB, key=itemgetter(0))]
R = 0
H = []
for m in range(1, M+1):
    if ABg and ABg[-1][0] == m:
        for a, b in ABg.pop()[1]:
            heappush(H, -b)
    if H:
        R -= heappop(H)

print(R)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
task = []
for i in range(N):
    heapq.heappush(task, tuple(map(int, input().split())))
heapq.heappush(task, (1000000,1000000))

availR = []
ans = 0
for i in range(M+1):  #i日前
    while task[0][0] <= i:
        tmp = list(heapq.heappop(task))
        tmp[1] *= -1
        tmp = tuple(reversed(tmp))
        heapq.heappush(availR, tmp)
    #print(availR)
    if len(availR) >= 1:
        todayReward = heapq.heappop(availR)[0] * (-1)
        ans += todayReward

print(ans)

Submission status: Accepted

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

c = [[] for _ in range(M)]

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

    if a > M:
        continue
    c[M - a].append(b)

import heapq

h = []
heapq.heapify(h)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import collections
import heapq
n, m = map(int, input().split())
c = collections.defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    c[m - a].append(b)
h = []
heapq.heapify(h)    
ans = 0
for i in range(m - 1, -1, -1):
    for b in c[i]:
        heapq.heappush(h, -b)
    if len(h) >0:
        ans += -1 * heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

for i in range(1, M+1):
    for s in salary[i]:
        heappush(queue, -s)
    if queue:
        ans += -heappop(queue)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappushpop

N,M = map(int,input().split())
# task[締切][価値]
tasks = [[] for _ in range(M)] 
for _ in range(N):
    a,b = map(int,input().split())
    if a <= M:
        tasks[M-a].append(b)

# 受注したバイト
q = []
# 締切=dayとなる最大の価値をqに格納
for day in range(M):
    # その日締切のバイト
    for v in tasks[day]:
        # まだ今日は受注してない
        if len(q) < day+1:
            heappush(q,v)
        else:
            heappushpop(q,v)

answer = sum(q)
print(answer)

Submission status: Accepted

Solution code:
import heapq

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

hp=[]
ans=0
d=0
for i in range(1,m+1):
    while d<n:
        if l[d][0]<=i:
            heapq.heappush(hp,-l[d][1])
            d+=1
        else:
            break
    if hp!=[]:
         ans+=-heapq.heappop(hp)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import collections
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
table = collections.defaultdict(list)
for a, b in AB:
    table[a].append(b)

job = []
ans = 0
heapq.heapify(job)
for i in range(M):
    for x in table[i+1]:
        heapq.heappush(job, -1 * x)
    if job:
        ans -= heapq.heappop(job)

print(ans)

Submission status: Accepted

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

import heapq
a = []
ans = 0
heapq.heapify(a)
for i in range(m):
  for j in range(len(l[i])):
    heapq.heappush(a, (-1)*l[i][j])
  if len(a) != 0:
    ans += heapq.heappop(a)*(-1)
print(ans)

Submission status: Accepted

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

import heapq
a = []
ans = 0
heapq.heapify(a)
for i in range(m):
  for j in range(len(l[i])):
    heapq.heappush(a, (-1)*l[i][j])
  if len(a) != 0:
    ans += heapq.heappop(a)*(-1)
print(ans)

Submission status: Accepted

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

from collections import deque
import heapq
ab=deque(ab)
cand=[]
heapq.heapify(cand)

ans=[0]*m
for i in range(m):
    while len(ab)>0:
        c=ab.popleft()
        if c[0]==i+1:
            heapq.heappush(cand,-c[1])
        else:
            ab.appendleft(c)
            break
    if len(cand)>0:
        ma = -heapq.heappop(cand)
        ans[i]=ma
print(sum(ans))

Submission status: Accepted

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

def calculate(N,M,arr):
    ret = 0

    j = 0

    res = []

    # 1,2,3,4,5
    #         ↑
    # 4,3,2,1

    # M = 4
    # range(1,5) => 1,2,3,4

    for i in range(1,M+1):
        # i = 1,2,3
        # 比如M=4的话，第三天(最多1天),第二天(最多2天),第一天(最多3天)

        # 记下来循环打工信息资源,以j为标记
        # j为资源编号
        # arr[j][0]为该编号资源的天数


        # 候补的资源，满足所有天数，因为是满足后续的天数来算的

        while (j < N) and (arr[j][0] <= i):

                heappush(res, -arr[j][1])
                j = j + 1 #j找到的话就往上顶一格，一共这一天，或者前一天寻找的时候以下一个资源天为开始

        if len(res) > 0:
            ret -= heappop(res)

    return ret


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


# 后面的逻辑是基于前面的从小到大的排序的
list = [list(map(int,input().split())) for i in range(N)]

arr = sorted(list,key=lambda x:x[0])

result = calculate(N,M,arr)

print(result)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

n, m = map(int, input().split())
jobs = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    jobs[a].append(b)

res = 0
candidates = PriorytyQueue(arr=[],
                           target='max')
for d in range(1, m+1):
    if d in jobs.keys():
        for m in jobs[d]:
            candidates.push(m)
    if not(candidates.is_empty()):
        res += candidates.pop()
print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]
result = 0
candidates = []
for a in range(1, m + 1):
  if a in jobs:
    for b in jobs[a]:
      heappush(candidates, -b)
  else:
    if len(candidates) == 0:
      continue
  result += -heappop(candidates)
print(result)

Submission status: Accepted

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

from heapq import *

h = []

AB = sorted(AB)

result = 0
p = 0
for i in range(1, M + 1):
    while p < len(AB) and AB[p][0] <= i:
        heappush(h, -AB[p][1])
        p += 1
    if h:
        result -= heappop(h)
    
print(result)