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:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, m = f.read_int_list()
    d = collections.defaultdict(list)
    for _ in xrange(n):
        a, b = f.read_int_list()
        d[a].append(b)

    h = []

    ans = 0
    for i in xrange(m+1):
        for di in d[i]:
            heapq.heappush(h, -di)
        if len(h) == 0:
            continue
        ans -= heapq.heappop(h)

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import heapq
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ls =[]
    v = []
    heapq.heapify(v)
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        ls.append([a, b])
    ls.sort(reverse=True)
    r = 0
    for i in range(1, m + 1):
        while True:
            if len(ls) != 0:
                a, b = ls.pop()
                if a <= i:
                    heapq.heappush(v, -b)
                else:
                    ls.append([a, b])
                    break
            else:
                break
        if len(v) != 0:
            r += -heapq.heappop(v)
    print(r)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
x = []
for _ in range(n):
    a,b = (int(i) for i in input().split())
    x.append((-b,a))
c,v,x,ans = [int(i) for i in range(m+1)],[1]*(m+1),sorted(x),0
for i in range(n):
    num,y = x[i][1],[x[i][1]]
    while num<=m and num!=c[num]:
        num = c[num]
        y.append(num)
    if num<=m:
        for j in y: c[j] = num+1
        ans-=x[i][0]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print(max(a + b, a - b, a * b))
    return

#B
def B():
    k, x = LI()
    ans = []
    for i in range(x - k + 1, x + k):
        ans.append(i)
    print(*ans)
    return

#C
def C():
    n = II()
    d = defaultdict(int)
    for _ in range(n):
        s = S()
        s.sort()
        d[tuple(s)] += 1
    ans = 0
    for i in d.values():
        ans += i * (i - 1) // 2
    print(ans)
    return

# D
# 解説AC
# 後方から見ていくのはわかったけど。。。
# i日前に選べるバイトの中から一番報酬が大きいを選んでいく
def D():
    n, m = LI()
    q = []
    d = defaultdict(list)
    ans = 0
    for _ in range(n):
        a, b = LI()
        d[a].append(b)
    for i in range(m):
        for di in d[i+1]:
            heappush(q, -di)
        if q:
            ans -= heappop(q)
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

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

N, M = map(int, input().split())
W = [list(map(int, input().split())) for i in range(N)]
W.sort()
  
ans = 0
C = []

for i in range(1,M+1):
  j = -i
  while W != [] and W[0][0] <= i:
    a,b = heappop(W)
    heappush(C,-b)
  if C != []:
    ans += -heappop(C)
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
W = []
for i in range(N):
  a = list(map(int, input().split()))
  heappush(W, a)
  
ans = 0
C = []

for i in range(1,M+1):
  j = -i
  while W != [] and W[0][0] <= i:
    a,b = heappop(W)
    heappush(C,-b)
  if C != []:
    ans += -heappop(C)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

N, M = map(int, input().split())
W = []
for i in range(N):
  a = list(map(int, input().split()))
  heappush(W, a)
  
ans = 0
C = []

for i in range(1,M+1):
  j = -i
  while W != [] and W[0][0] <= i:
    a,b = heappop(W)
    heappush(C,-b)
  if C != []:
    ans += -heappop(C)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

Days = [[] for i in range(m)]
for i in range(n):
    if Jobs[i][0] <= m:
        Days[Jobs[i][0]-1] += [[-Jobs[i][1],Jobs[i][0]]]

Heap = []
heapq.heapify(Heap)
ans = 0
for i in range(m):
    for job in Days[i]:
        heapq.heappush(Heap,job)
    if Heap:
        ans -= heapq.heappop(Heap)[0]
        
print(ans)

Submission status: Accepted

Solution code:
import numpy
import heapq
import math

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

rew = 0
heap=[]
for i in range(M):
    for rewo in data[i]:
        heapq.heappush(heap,rewo)
    if len(heap) > 0:
        r = heapq.heappop(heap)
        rew += -r

print(rew)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
n,m=map(int,input().split())
data=[[] for _ in range(m+1)]
for _ in range(n):
    a,b=map(int,input().split())
    if a<=m:
        data[a].append([-b,a])
for i in range(1,m+1):
    data[i].sort()
    data[i]=deque(data[i])
h=[]
s=0
for i in range(1,m+1):
    if data[i]:
        heappush(h,data[i].popleft())
    if h:
        d=heappop(h)
        if data[d[1]]:
            heappush(h,data[d[1]].popleft())
        s+=-d[0]
print(s)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys
import heapq
from collections import defaultdict

"""解説PDF
(1) 0日目から考えると、最初に選べるアルバイトが多すぎて、どれを適切に選んでいけばよいかわからない

(2) M日後から考えると、M日後からi日前には、A_i<=iとなるアルバイトしか選べないので、これで考えると貪欲的に解ける

"""
def solve():
    N, M = list(map(int, sys.stdin.readline().split()))
    jobs = defaultdict(lambda: [])

    # jobs[a] := 報酬がa日後に貰えるアルバイトのリスト
    for i in range(N):
        a, b = list(map(int, sys.stdin.readline().split()))
        jobs[a].append(b)

    ans = 0
    heap = []  # アルバイト候補
    for i in range(1, M+1):
        # M-i日目に何のアルバイトをすればよいかを考える
        for b in jobs[i]:
            # 候補の追加
            heapq.heappush(heap, -b)  # 最大値を根にするために、マイナスをかける

        if len(heap) != 0:
            # 候補の中で報酬が最大値を取り出す
            ans += -heapq.heappop(heap)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

jobs = []
available = []
for _ in range(N):
    temp = tuple(map(int, input().split()))
    jobs.append(temp)

heapq.heapify(jobs)
ans = 0
for i in range(1, M+1):
    while(len(jobs)):
        a, b = heapq.heappop(jobs)
        if a == i:
            heapq.heappush(available, -b)
        else:
            heapq.heappush(jobs, (a, b))
            break
    if len(available):
        val = heapq.heappop(available)
        ans += -val

print(ans)

Submission status: Accepted

Solution code:
import heapq

n, m = list(map(int, input().split()))
tasks = []
for i in range(n):
    ai, bi = list(map(int, input().split()))
    tasks.append((-bi, i, ai))
tasks.sort(key=lambda x: x[2])    
prtasks = []
money = 0
j = 0
for i in range(1,m+1):
    for k in range(j,len(tasks)):
        if tasks[k][2] <= i:
            heapq.heappush(prtasks, tasks[k])
            j += 1
        else:
            break
    if not prtasks:
        continue
    work = heapq.heappop(prtasks)
    money += work[0]

print(-money)

Submission status: Accepted

Solution code:
import heapq


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(n)]
    ab = sorted(ab)
    # print(n, m)
    # print(ab)
    index = 0
    ans = []
    money = 0
    for day in range(1, m+1):
        # print(day)
        while index < n and ab[index][0] <= day:
            heapq.heappush(ans, -ab[index][1])
            index += 1
            # print(ans)
        if ans:
            money -= heapq.heappop(ans)

    print(money)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

baitos = sorted(baitos)
# print(sorted(baitos))
# print(baitos)

money = 0
avail = []
# heapq.heapify(avail)
index = 0
for day in range(m):
    while index < n and baitos[index][0] <= day + 1:
        heapq.heappush(avail, -baitos[index][1])
        index += 1
        # baitos.remove(baitos[0])
    # for baito in baitos:
    #     print(baito)
    #     if baito[0] > day + 1:
    #         print("break")
    #         break
    #     else:
    #         heapq.heappush(avail, -baito[1])
    #         baitos.remove(baito)
    # print("baitos", baitos)
    # print("avail", avail)
    if avail:

        money += -heapq.heappop(avail)
        # print(day, money)
    # money += max[1]
    # baitos.remove(max)

print(money)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n)]
ls.sort(key=lambda x: x[0])

q = []
res = 0
index = 0
for i in range(1, m + 1):
    while index < n and ls[index][0] <= i:
        heapq.heappush(q, -ls[index][1])
        index += 1
    if len(q) > 0:
        res += -heapq.heappop(q)
print(res)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n, m = map(int, input().split())
l = [[] for i in range(n)]
for i in range(n):
    a,b = map(int, input().split())
    c = min(m-a, n-1)
    if c < 0:
        continue
    heappush(l[c], -b)
heap = []
ans = 0
for i in range(n)[::-1]:
    for b in l[i]:
        heappush(heap, b)
    if heap:
        b = heappop(heap)
        ans += -b
print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    if a <= m:
        ab.append((a,b))
ab.sort(reverse=1)

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

print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    if a <= m:
        ab.append((a,b))
ab.sort(reverse=1)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for line in sys.stdin:
    a,b = map(int,line.split())
    if a <= m:
        ab.append((a,b))
ab.sort(reverse=1)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for line in sys.stdin:
    a,b = map(int,line.split())
    if a <= m:
        ab.append((a,b))
ab.sort()

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

print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
ab = []
for i in range(n):
    a,b = map(int,input().split())
    if a <= m:
        ab.append((a,b))
ab.sort()

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop

n,m = map(int,input().split())
ab = []
for line in sys.stdin:
    a,b = map(int,line.split())
    if a <= m:
        ab.append([a,b])
ab.sort()

stock = []
ans = 0
for i in range(1,m+1):
    while ab and ab[0][0] <= i:
        a = ab.pop(0)
        heappush(stock,-a[1])
    if stock:
        ans += -heappop(stock)

print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int,input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
for i in range(N):
    A[i], B[i] = map(int,input().split())
ptj = {}
for i in range(N):
    if A[i] in ptj:
        ptj[A[i]].append(-B[i])
    else:
        ptj[A[i]] = [-B[i]]
count = 0
s = []
for i in range(1,M+1):
    if i in ptj:
        for j in ptj[i]:
            heapq.heappush(s,j)
    if s != []:
        count -= heapq.heappop(s)
print(count)

Submission status: Accepted

Solution code:
import heapq

def main():
    n, m, *ab = map(int, open(0).read().split())

    ab_dict = {}
    for a, b in zip(*[iter(ab)] * 2):
        if a > m:
            continue
        if a in ab_dict:
            ab_dict[a].append(-b)
        else:
            ab_dict[a] = [-b]

    cand = []
    ans = 0
    for day in range(1, m+1):
        if day in ab_dict:
            for cand_b in ab_dict[day]:
                heapq.heappush(cand, cand_b)
        if cand:
            ans += -heapq.heappop(cand)

    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

def main():
    N,M=[int(x) for x in input().split()]

    jobs=defaultdict(list)
    for _ in range(N):
        a,b=[int(x) for x in input().split()]
        jobs[M-a].append(b)
    
    # print(jobs)

    hq=[]
    heapq.heapify(hq)
    ans=0
    for day in reversed(range(M)):
        for job in jobs[day]:
            heapq.heappush(hq, -job)

        if hq:
            ans+=-heapq.heappop(hq)

    print(ans)


main()

Submission status: Accepted

Solution code:
import heapq

N,M=[int(s) for s in input().split()]
baito = []
for i in range(N):
  a,b=[int(s) for s in input().split()]
  heapq.heappush(baito, (-a,-b))
job=[]

while baito:
  x, y = heapq.heappop(baito)
  r = M-len(job)
  if -x > r:
    heapq.heappush(job, -y)
    heapq.heappop(job)       #より高給の仕事（ｙが高い）だった場合、他のを押し出す
  else:
    heapq.heappush(job, -y)
print(sum(job))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc137/tasks/abc137_d

import heapq

# n: 日雇いアルバイトの案件数
# m: m日後までに稼げるお金を最大化
n, m = map(int, input().split())

# (期限から) m日以内に開始しなければ終わらない仕事
money_schedule = [[] for _ in range(m)]
for i in range(n):
    # a日後にb円振り込まれる
    a, b = map(int, input().split())
    if m < a:
        continue
    money_schedule[a - 1].append(b)

job_pool = []
heapq.heapify(job_pool)
income = 0
for available_jobs in money_schedule:
    for salary in available_jobs:
        heapq.heappush(job_pool, -salary)

    if 0 < len(job_pool):
        income -= heapq.heappop(job_pool)

print(income)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import heapq


class MaxHeap:
    def __init__(self, li):
        self.heap = [-e for e in li]
        heapq.heapify(self.heap)

    def push(self, val):
        heapq.heappush(self.heap, -val)

    def pop(self):
        return -heapq.heappop(self.heap)

    def __len__(self):
        return len(self.heap)


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

ab.sort()

h = MaxHeap([])

i = 0
ans = 0
for day in range(1, m + 1):
    while i < n and ab[i][0] <= day:
        h.push(ab[i][1])
        i += 1
    if len(h) == 0:
        continue
    ans += h.pop()

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

dic=defaultdict(list)
for a,b in ab:
    dic[a]+=[-b]

li=[]
ans=0
for i in range(1,m+1):
    if dic[i]:
        for j in dic[i]:
            heapq.heappush(li,j)
    if li:
        ans+=heapq.heappop(li)
print(-ans)

Submission status: Accepted

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

lis = []
for i in range(n):
  a, b = map(int, input().split())
  heapq.heappush(lis, [-a,-b])

s = []
while lis:
  x, y = heapq.heappop(lis)
  r = m-len(s)
  if -x > r:
    heapq.heappush(s, -y)
    heapq.heappop(s)
  else:
    heapq.heappush(s, -y)
print(sum(s))

Submission status: Accepted

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

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

for i in range(1, m+1):
    for x in day[i]:
        heapq.heappush(q, x)
    if q != []:
        ans += -heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq
import bisect

N,M = (int(i) for i in input().split()) 
ab = [[int(i) for i in input().split()] for i in range(N)] 

ans=0
ab.sort()
_index=[i[0] for i in ab]
p=[]
heapq.heapify(p)

for i in range(1,M+1):
	for g in ab[bisect.bisect_left(_index, i) : bisect.bisect_right(_index, i)]:
		heapq.heappush(p, -g[1])
	if p!=[]:
		ans+=heapq.heappop(p)*(-1)

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)]
d_AB = {a:[] for a,b in AB}
for a,b in AB:
    d_AB[a].append(-b)
H = []
money = 0
for i in range(1,M+1):
    if i in d_AB.keys():
        for ab in d_AB[i]:
            heapq.heappush(H,ab)
        money += heapq.heappop(H)
    else:
        money += heapq.heappushpop(H,0)
print(-money)

Submission status: Accepted

Solution code:
import heapq

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


d_AB = {a:[] for a,b in AB}
for a,b in AB:
    d_AB[a].append(-b)
#print(d_AB)
H = []
heapq.heapify(H)
money = 0
for i in range(1,M+1):
    if i in d_AB.keys():
        for ab in d_AB[i]:
            heapq.heappush(H,ab)
        #print(H)
        money += heapq.heappop(H)
        #print(money)
        
    else:
        money += heapq.heappushpop(H,0)

print(-money)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bisect

def main():
    n, m, *ab = map(int, open(0).read().split())

    rate = []
    for a, b in zip(*[iter(ab)] * 2):
        if a > m:
            continue
        rate.append([a, b])

    rate = sorted(rate, key=lambda x: -x[1])

    day = list(range(1, m + 1))
    day_len = m
    ans = 0
    for term, money in rate:
        work_day = bisect(day, term)
        if work_day == day_len:
            continue
        else:
            del day[work_day]
            day_len -= 1
            ans += money

    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
c=[[] for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in c[i]:
        heapq.heappush(d,j)
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
c=[[] for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(len(c[i])):
        heapq.heappush(d,c[i][j])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)

Submission status: Accepted

Solution code:
import heapq
import sys

N, M = map(int, input().split())
tmp = [[] for _ in range(M + 1)]
for i in range(N):
    a, b = map(int, input().split())
    if M >= a:
        tmp[M - a].append(b)
ans = []
for i in range(M + 1):
    for j in tmp[i]:
        heapq.heappush(ans, j)
        if len(ans) > i + 1:
            heapq.heappop(ans)

print(sum(ans))

Submission status: Accepted

Solution code:
import heapq

# max heap
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign
 
    def size(self):
        return len(self.hq)

from collections import defaultdict
d = defaultdict(list)

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

q = Heapq([], True)
 
ans = 0
for i in range(1,m+1):
    for b in d[i]:
        q.push(b)
    if q.size():
        ans += q.pop()
print(ans)

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    Q = []
    for _ in range(N):
        a, b = map(int, input().split())
        heapq.heappush(Q, [a, b])
    
    ans = 0
    P = []
    for i in range(1, M+1):
        if len(Q)!=0:
            a, b = heapq.heappop(Q)
            while a==i:
                heapq.heappush(P, [b*(-1), a])
                if len(Q)==0:
                    break
                a, b = heapq.heappop(Q)
            heapq.heappush(Q, [a, b])
        if len(P)!=0:
            b, a = heapq.heappop(P)
            ans += b*(-1)
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq


def input(): return sys.stdin.readline().strip()


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

    w = [[] for _ in range(10 ** 5 + 1)]
    for _ in range(N):
        a, b = map(int, input().split())
        w[a].append(b)

    ans = 0
    hq = []
    for i in range(1, M+1):
        for x in w[i]:
            heapq.heappush(hq, -x)

        if not hq:
            continue

        ans += -heapq.heappop(hq)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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


work = defaultdict(list)

for i in range(N):
    a,b = map(int, input().split())
    work[a-1].append(-b)



# 終了日から１日前、２日前、...の順で仕事を選ぶ
current_work = []
ans = 0
for i in range(M):
    if i in work.keys():
        for j in work[i]:
            #元が空っぽなので、heapifyしなくてもheapを保てる
            heapq.heappush(current_work, j)

    if current_work:
        #heapq.heapify(current_work)
        ans += -1 * heapq.heappop(current_work)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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


work = defaultdict(list)

for i in range(N):
    a,b = map(int, input().split())
    work[a-1].append(-b)



# 終了日から１日前、２日前、...の順で仕事を選ぶ
current_work = []
ans = 0
for i in range(M):
    if i in work.keys():
        for j in work[i]:
            heapq.heappush(current_work, j)

    if current_work:
        #heapq.heapify(current_work)
        ans += -1 * heapq.heappop(current_work)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

for _ in range(N):
    A, B = input().split()
    daily_jobs[A].append(-int(B))

ans = 0
now_cand = []
for i in range(1, M+1):
    for job in daily_jobs[str(i)]:
        heapq.heappush(now_cand, job)
    if now_cand:
        ans += heapq.heappop(now_cand)

print(-ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
ABs = []
for i in range(N):
  A, B = map(int, input().split())
  ABs.append((A, B))
ABs.sort()
r = 0
q = []
i = 0
for m in range(1, M+1):
  while i < N:
    A, B = ABs[i]
    if A <= m:
      heapq.heappush(q, -B)
      i += 1
    else:
      break
  if q:
    B = -heapq.heappop(q)
    r += B
print(r)

Submission status: Accepted

Solution code:
import heapq

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

heap_lst = []
heapq.heapify(heap_lst)
j = 0
res = 0

sorted_lst = sorted(lst, key = lambda x: x[0])
for i in range(1, m+1):
    while j < n and sorted_lst[j][0] <= i:
        a, b = sorted_lst[j]
        heapq.heappush(heap_lst, (-b, a))
        j += 1
    if len(heap_lst) == 0:
        continue
    else:
        minus_b, a = heapq.heappop(heap_lst)
        res += -minus_b
print(res)

Submission status: Accepted

Solution code:
import heapq

# 標準入力受け取り
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]  #日数分(M)だけ[]を用意
# print(jobs)

for i in range(N):
    d, r = list(map(int, input().split()))   #d = A[i], r = B[i]
    if d - 1 < M:   #d-1番目の要素にrを追加して、同じ受け取り日数のバイトを同じ要素に入れる。d-1より、2日後のはjobs[1]におかれる。
        jobs[d - 1].append(-r)  # マイナスにしている
# print(jobs)

rewards = 0
heap = []

# 解法
for i in range(M):
    # 要素を一つづつヒープに追加
    for reward in jobs[i]:
        heapq.heappush(heap, reward)
    # print(heap)
    if len(heap) > 0:
        # 最大値(最小値)をヒープから取り出し
        reward = heapq.heappop(heap)
        rewards += -reward  # マイナスにしている
    # print(heap)

print(rewards)

Submission status: Accepted

Solution code:
import heapq
#標準入力受け取り
N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r) #マイナスにしている

rewards = 0
heap = []

#解法
for i in range(M):
    #要素を一つづつヒープに追加
    for reward in jobs[i]:
        heapq.heappush(heap, reward)
    if len(heap) > 0:
        #最大値(最小値)をヒープから取り出し
        reward = heapq.heappop(heap)
        rewards += -reward#マイナスにしている

print(rewards)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
n, m = map(int, input().split())
jobs = [None]*n
q = []
heapq.heapify(q)
day = 0
ans = 0

for i in range(n):
    jobs[i] = tuple(map(int, input().split()))
jobs.sort(key = lambda x:x[1], reverse=True)
jobs.sort(key = lambda x:x[0])
jobs = deque(jobs)

for i in range(m):
    while True:
        if  not len(jobs) == 0:
            j = jobs.popleft()
            if not j[0] == i+1:
                jobs.appendleft(j)
                break
            else:
                heapq.heappush(q, -j[1])
        else:
            break
    if q:
        ans -= heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
n,m=map(int,input().split())
dic=defaultdict(list)
for i in range(n):
    a,b=map(int,input().split())
    dic[a]+=[-b]
    
li=[]
ans=0

for i in range(1,m+1):
    if dic[i]:
        for j in dic[i]:
            heapq.heappush(li,j)
    if li:
        ans+=heapq.heappop(li)
print(-ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
n,m=map(int,input().split())
dic=defaultdict(list)
for i in range(n):
    a,b=map(int,input().split())
    dic[a].append(-b)
    
li=[]
ans=0

for i in range(1,m+1):
    if dic[i]:
        for j in dic[i]:
            heapq.heappush(li,j)
    if li:
        ans+=heapq.heappop(li)
print(-ans)

Submission status: Accepted

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


def main():
    N, M, *A = map(int, open(0).read().split())
    # T[i] := candidates of values on i-th deadline
    T = [[] for _ in range(M + 1)]
    for a, b in zip(*[iter(A)] * 2):
        if a <= M:
            T[M - a] += [b]
    q = []  # heapq
    for i in range(M + 1):
        for v in T[i]:
            # keep i worthwhile tasks in i-th day
            if len(q) <= i:
                heappush(q, v)
            else:
                heappushpop(q, v)
    print(sum(q))


if __name__ == "__main__":
    main()