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:
from heapq import heappop, heappush
from collections import defaultdict


def solve(string):
    n, m, *ab = map(int, string.split())
    dd = defaultdict(list)
    for a, b in zip(*[iter(ab)] * 2):
        dd[a].append(-b)
    hq, ans = [], 0
    for d in range(1, m + 1):
        if d in dd:
            for _b in dd[d]:
                heappush(hq, _b)
        if hq:
            ans += heappop(hq)
    return str(-ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq, index, cap, count, ans = [], 0, 1, m, 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            ans += -heapq.heappop(hq) if len(hq) > 0 else 0
            count += -1
            cap += 1
    ans += sum([-heapq.heappop(hq) for _ in range(count) if len(hq) > 0])
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq, index, cap, count, ans = [], 0, 1, m, 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            ans -= heapq.heappop(hq) if len(hq) > 0 else 0
            count -= 1
            cap += 1
    ans += sum([-heapq.heappop(hq) for _ in range(count) if len(hq) > 0])
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq, index, cap, count, ans = [], 0, 1, m, 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            ans += -heapq.heappop(hq) if len(hq) > 0 else 0
            count -= 1
            cap += 1
    ans += sum([-heapq.heappop(hq) for _ in range(count) if len(hq) > 0])
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq, index, cap, count, ans = [], 0, 1, m, 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            ans -= heapq.heappop(hq) if len(hq) > 0 else 0
            count -= 1
            cap += 1
    ans -= sum([heapq.heappop(hq) if len(hq) > 0 else 0 for _ in range(count)])
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
import heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq, index, cap, count, ans = [], 0, 1, m, 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            ans += -heapq.heappop(hq) if len(hq) > 0 else 0
            count -= 1
            cap += 1
    ans += sum([-heapq.heappop(hq) if len(hq) > 0 else 0 for _ in range(count)])
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

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

ans = 0
a = []
for i in range(1,m+1):
  for j in l[i]:
    heappush(a,-j)
  if a:
    ans -= heappop(a)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
jobs = {}
for i in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    k = m - a
    if k not in jobs:
        jobs[k] = []
    jobs[k].append(b)
h = []
ans = 0
for i in range(m - 1, -1, -1):
    if i in jobs:
        for b in jobs[i]:
            heappush(h, -b)
    if len(h) > 0:
        ans += -heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

for i in range(N):
    A, B = map(int, input().split())
    l[i] = [A,-B]
l.sort()

tmp = []
ans = 0
j = 0

for i in range(1, M + 1):
    while j < N:
        A, B = l[j][0], -l[j][1]
        memo = [-B, A]
        if A <= i:
            heapq.heappush(tmp, memo)
            j += 1
        else:
            break
    if len(tmp) > 0:
        ans -= heapq.heappop(tmp)[0]
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
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 heapq


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([(a, b) for a, b in zip(*[iter(ab)] * 2)])
    hq = []
    index, cap, count = 0, 1, m
    ans = 0
    while index < n:
        _a, _b = ab[index]
        if _a > m:
            break
        if _a <= cap:
            heapq.heappush(hq, -_b)
            index += 1
        else:
            if len(hq) > 0:
                ans += -heapq.heappop(hq)
            count -= 1
            cap += 1
    for _ in range(count):
        if len(hq) > 0:
            ans += -heapq.heappop(hq)
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    heapify(ab)
    for i in range(N):
        a,b = inputMap()
        if a > M:
            continue
        heappush(ab, (a,b))
    
    ans = 0
    pq = []
    heapify(pq)
    for i in range(1,M+1):
        while True:
            if len(ab) == 0 or ab[0][0] != i:
                break
            a,b = heappop(ab)
            heappush(pq, -b)
            
        if len(pq) > 0:
            ans = ans + (heappop(pq) * (-1))
        
    
    print(ans)
    
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from heapq import *
n,m = map(int,input().split())
t = [[] for i in range(10**5+1)]
for i in range(n):
    a,b = map(int,input().split())
    t[a].append(b)

ans = 0
h = []
for i in range(1,m+1):
    #print(i,"日目")
    for j in t[i]:
        heappush(h, -j)
        #print("heappush",j)
    if h:
        a = -heappop(h)
        #print("heappop",a)
        ans += a
print(ans)

Submission status: Accepted

Solution code:

#%%
import heapq

N, M = map(int, input().split())
l = [0] * N
for i in range(N):
    l[i] = list(map(int, input().split()))

l.sort()
#print(l)

L = [[] for _ in range(M+1)]
for i in range(N):
    if l[i][0] <= M:
        L[l[i][0]].append(l[i][1]) 

#print(L)


a = []
ans = 0
for i in range(M+1):
    for j in range(len(L[i])):
        heapq.heappush(a, -L[i][j])
    if len(a) != 0:
        ans += heapq.heappop(a)

print(-ans)

#%%

Submission status: Accepted

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

def sol():
    n,m=map(int,input().split())
    d=[]
    for i in range(n):
        a,b=map(int,input().split())
        #if a<=m: d.append((a,b))
        if a<=m: heapq.heappush(d,(a,b))
    #d.sort(reverse=True)
    q=[]
    ans=0
    for i in range(1,m+1):
        #while d and d[-1][0]<=i:
        while d and d[0][0]<=i:
            #a,b=d.pop()
            a,b=heapq.heappop(d)
            heapq.heappush(q,-b)
        if q:
            ans += -heapq.heappop(q)
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import heapq

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

table = [list(map(int, input().split())) for _ in range(n)]
table.sort(reverse=True)

ans = 0
pay = []

for day in range(1, m+1):
    while table and table[-1][0] <= day:
        tmp = table.pop()
        heapq.heappush(pay, -tmp[1])
   
    if pay:
        ans -= heapq.heappop(pay)

print(ans)

Submission status: Accepted

Solution code:
import heapq
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=True)
List = []

ans = 0
for i in range(1,M+1):
    while AB and AB[-1][0] <= i:
        tmp = AB.pop()
        heapq.heappush(List,-tmp[1])

    if len(List) > 0:
        ans -= heapq.heappop(List)
        
print(ans)

Submission status: Accepted

Solution code:
import heapq
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_list = [[] for _ in range(M)]
 
for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a <= M:
        each_days_list[a-1].append(b)

max_list = []
salary_count = 0
for i in range(M):
    for j in range(len(each_days_list[i])): 
        heapq.heappush(max_list,-each_days_list[i][j])
    if len(max_list) > 0:
        salary_count += -heapq.heappop(max_list)
        
print(salary_count)

Submission status: Accepted

Solution code:
#from https://atcoder.jp/contests/abc137/submissions/6808061
import heapq
import sys
input=sys.stdin.readline

def sol():
    n,m=map(int,input().split())
    d=[]
    for i in range(n):
        a,b=map(int,input().split())
        if a<=m: d.append((a,b))
    d.sort(reverse=True)
    q=[]
    ans=0
    for i in range(1,m+1):
        while d and d[-1][0]<=i:
            a,b=d.pop()
            heapq.heappush(q,-b)
        if q:
            ans += -heapq.heappop(q)
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(n)]
ab_list.sort()
idx = 0
q = []
ans = 0
for j in range(1, m+1):
    while idx < n:
        a, b = ab_list[idx]
        if a <= j:
            heapq.heappush(q, -b)
            idx += 1
        else:
            break
    if len(q) > 0:
        b = heapq.heappop(q)
        ans -= b
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import heapq

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

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

ans = 0
heap = []

for i in range(M+1):
    if i in works:
        [heapq.heappush(heap, work) for work in map(lambda x: x * -1, works[i])]
    if heap:
        ans += heapq.heappop(heap) * -1

print(ans)

Submission status: Accepted

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

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

que = []#候補入れ
ans = 0
for i in range(m-1, -1, -1):
  for wage in jobs[i]:
    heapq.heappush(que, wage*-1)
  if len(que):
    ans += heapq.heappop(que)*-1
    
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ab = {}

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


q = []
ans = 0
for day in range(1, M+1):
    if day in ab:
        for i in ab[day]:
            heapq.heappush(q, i)

    if q != None and len(q) != 0:
        ans += -1 * heapq.heappop(q)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
AB =[tuple(map(int,input().split())) for i in range(n)]
ans,memo=0,0
hq=[]
AB.sort(key=lambda tup:tup[0])
for day in range(m):
	for i in range(memo,n):
		if AB[i][0]<=(day+1):
			heapq.heappush(hq,-AB[i][1])
			memo+=1
		else:
			break
	if len(hq):	
		ans += -heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

Submission status: Accepted

Solution code:
import heapq

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

L=[]
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,-b])
L.sort()
#print(L)
Q=[]
heapq.heapify(Q)
l=0
ans=0
for i in range(1,M+1):
    for j in range(l,N):
        if L[j][0]==i:
            heapq.heappush(Q,[L[j][1],L[j][0]])
            #print(i,L[j])
            l+=1
        else:
            break
    
    if len(Q)==0:
        pass
    else:
        ans-=Q[0][0]
        #print(i,ans)
        heapq.heappop(Q)
print(ans)

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
import heapq
input = sys.stdin.readline
hq = []
heapq.heapify(hq)

N, M = map(int, input().split())
# AでsortされたA, Bのペアを格納
P = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[0])
j = 0
ans = 0
for i in range(1, M+1):  # M - i日後にするバイトを考える
    while j < N and P[j][0] <= i:
        heapq.heappush(hq, -P[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heapq.heappop(hq)
print(ans)

Submission status: Accepted

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

import heapq

n, m = map(int, input().split())
ab = []

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

l = []

idx = 0
ans = 0
for i in range(1, m+1):
    while idx < n and ab[idx][0] <= i:
        heapq.heappush(l, ab[idx][1])
        idx += 1
    if len(l) > 0:
        ans -= heapq.heappop(l)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
j = []
for i in range(n):
    j1 = list(map(int,input().split()))
    j.append(j1)
j.sort(key=lambda x:x[1],reverse=True)
j.sort(key=lambda x:x[0])
day = 1
i = 0
q = []
ans = 0
count = 0
while day <= m and i < n:
    if day == j[i][0]:
        heapq.heappush(q,-(j[i][1]))
        ans = ans + heapq.heappop(q)*(-1)
        day = day + 1
        i = i + 1
    elif day > j[i][0]:
        heapq.heappush(q,-(j[i][1]))
        i = i + 1
        count = count + 1
    else:
        day = day + 1
        if count > 0:
            ans = ans + heapq.heappop(q)*(-1)
            count = count - 1
while day <= m and count > 0:
        ans = ans + heapq.heappop(q)*(-1)
        day = day + 1
        count = count - 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n,m=map(int,input().split())
a=[]
for i in range(n):
    heappush(a,list(map(int,input().split())))
heap=[]
s=0
for i in range(m):
    while 1:
        if len(a)==0:break
        else:
            if a[0][0]==i+1:heappush(heap,-heappop(a)[1])
            else:break
    if len(heap)>0:s+=-heappop(heap)
print(s)

Submission status: Accepted

Solution code:
# 優先度キューを使う
import heapq

N, M = [int(x) for x in input().split()]
AB = [0] * N

for i in range(N):
    AB[i] = [int(x) for x in input().split()]

# 毎日、候補となる集合を再計算すると間に合わない
# M-1日後から当日に向けて計算してけば、
# day 日時点で day + a = M となる仕事だけを候補に追加することで
# day + 1日までに追加した候補を再利用できる。
# さらに、候補からpopした要素は次回から考慮しないため、設問の条件とも一致する。

# 仕事の候補、徐々に追加していく
candidates = []
# nextpush 次に候補としてpush するか判定するcandidates の添え字
nextpush = 0

# 期間の短いものから候補に入れていくので期間でソートしておく
# AB[i][0] が期間なので、キー指定不要

AB = sorted(AB)

# 回答
answer = 0

for day in range(M)[::-1]:
    while nextpush < N:
        a, b = AB[nextpush]
        if day + a == M:
            # 給料が高い順ものを優先して取り出したいので、-b をキューにいれる。
            heapq.heappush(candidates, -b)
            nextpush += 1
        else:
            # AB はソート済みなので、これ以降の要素に候補に追加できるものはない
            # 次回は nextpush から再開する。
            break
    if candidates: # 仕事が出来ない日もあるかも・・・
        b = heapq.heappop(candidates)
        # マイナスで入れてるので、符号を逆にして戻す
        answer -= b

print(answer)

Submission status: Accepted

Solution code:
import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# ヒープ
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)
# 最大公約数 / 最小公倍数
def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2
# 二分探索
def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)
# Union-Find木
class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)
# グラフ
class graph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def append(self, v1, v2, cost=1):
        self.graph[v1].append((v2, cost))
    # 最短経路：ダイクストラ法(Dijkstra's Algorithm)
    def dks(self, v):
        costs = [INF] * self.n
        costs[v] = 0
        done = [False] * self.n
        heap = heapque((0, v))
        while heap.que:
            c_cost, c_index = heap.pop()
            if done[c_index]:
                continue
            done[c_index] = True
            for n_index, n_cost in self.graph[c_index]:
                if c_cost + n_cost < costs[n_index]:
                    costs[n_index] = c_cost + n_cost
                    heap.push((costs[n_index], n_index))
        return costs

def main():
    N, M = map(int, input().split())
    ab = dd(list)
    for _ in range(N):
        a, b = map(int, input().split())
        ab[a].append(b)

    heap = heapque()
    v = 0
    for m in range(1, M + 1):
        if m in ab:
            for b in ab[m]:
                heap.push(-b)
        if heap.que:
            v += -heap.pop()
    print(v)

main()

Submission status: Accepted

Solution code:
import heapq

N, M = [int(x) for x in input().split()]
AB = [0] * N

for i in range(N):
    AB[i] = [int(x) for x in input().split()]

AB = sorted(AB)

jobs = set()
answer = 0
nextpush = 0
candidates = []

for day in range(M)[::-1]:
    while nextpush < N:
        a, b = AB[nextpush]
        if day + a <= M:
            heapq.heappush(candidates, (-b, a))
            nextpush+=1
        else:
            break
    if candidates:
        b, a = heapq.heappop(candidates)
        answer -= b
print(answer)

Submission status: Accepted

Solution code:
import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# ヒープ
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)
# 最大公約数 / 最小公倍数
def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2
# 二分探索
def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)
# Union-Find木
class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)
# グラフ
class graph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def append(self, v1, v2, cost=1):
        self.graph[v1].append((v2, cost))
    # 最短経路：ダイクストラ法(Dijkstra's Algorithm)
    def dks(self, v):
        costs = [INF] * self.n
        costs[v] = 0
        done = [False] * self.n
        heap = heapque((0, v))
        while heap.que:
            c_cost, c_index = heap.pop()
            if done[c_index]:
                continue
            done[c_index] = True
            for n_index, n_cost in self.graph[c_index]:
                if c_cost + n_cost < costs[n_index]:
                    costs[n_index] = c_cost + n_cost
                    heap.push((costs[n_index], n_index))
        return costs

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

    ab = sorted(AB)
    heap = heapque()
    v, i = 0, 0
    for m in range(1, M + 1):
        while i < N:
            if ab[i][0] <= m:
                heap.push(-ab[i][1])
                i += 1
            else:
                break
        if heap.que:
            v += -heap.pop()
    print(v)

main()

Submission status: Accepted

Solution code:
import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# ヒープ
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)
# 最大公約数 / 最小公倍数
def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2
# 二分探索
def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)
# Union-Find木
class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)
# グラフ
class graph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def append(self, v1, v2, cost=1):
        self.graph[v1].append((v2, cost))
    # 最短経路：ダイクストラ法(Dijkstra's Algorithm)
    def dks(self, v):
        costs = [INF] * self.n
        costs[v] = 0
        done = [False] * self.n
        heap = heapque((0, v))
        while heap.que:
            c_cost, c_index = heap.pop()
            if done[c_index]:
                continue
            done[c_index] = True
            for n_index, n_cost in self.graph[c_index]:
                if c_cost + n_cost < costs[n_index]:
                    costs[n_index] = c_cost + n_cost
                    heap.push((costs[n_index], n_index))
        return costs

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

    ab = dd(list)
    for a, b in AB:
        ab[a] += [b]
    heap = heapque()
    v = 0
    for m in range(1, M + 1):
        if m in ab:
            for b in ab[m]:
                heap.push(-b)
        if heap.que:
            v += -heap.pop()
    print(v)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

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

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

for a in range(1,M + 1):
  for b in d[a]:
    heappush(h,-b)
  if len(h) > 0:
    c = heappop(h)
    res -=c
    
print(res)

Submission status: Accepted

Solution code:
import heapq as hp

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
j = 0
list = sorted(list)

for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      hp.heappush(temp,-list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans -= hp.heappop(temp)
print(ans)

Submission status: Accepted

Solution code:
import heapq as hp
import sys
def input():
    return sys.stdin.readline()

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
j = 0
list = sorted(list)

for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      hp.heappush(temp,-list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans -= hp.heappop(temp)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import heapq

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

## solution 1
AB = sorted(AB, reverse = True)

# print (AB)

H = []
sum_c = 0
for m in range(1, M + 1):
    while AB and AB[-1][0] <= m:
        c = AB.pop()[1]
        heapq.heappush(H, -c)

    if H:
        sum_c -= heapq.heappop(H)

print (sum_c)

Submission status: Accepted

Solution code:
import heapq
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)

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

q = Heapq([], True)
ans = 0

for a in range(1,M+1) :
    for b in D[a] :
        q.push(b)
    if q.size() > 0 :
        ans += q.pop()
print(ans)