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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import heapq
    mod=10**9+7
    N,M=MI()
    L=[[]for _ in range(M)]
    for i in range(N):
        #何日までに受ける必要があるかを気にしながら持つ
        a,b=MI()
        if a<=M:
            L[M-a].append(-b)
        
    ans=0
    hq=[]
    heapq.heapify(hq)
    
    for i in range(M-1,-1,-1):
        for bb in L[i]:
            heapq.heappush(hq,bb)
            
        if len(hq)!=0:
            temp=heapq.heappop(hq)
            ans+=-1*temp
        
    print(ans)
        
        

main()

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
AB = [[] for i in range(10**5+1)]

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

hq = []
heapq.heapify(hq)

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

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
AB=[[]for i in range(10**5+1)]
for i in range(N):
    a,b=map(int,input().split())
    AB[a].append(-b)
q=[]
heapq.heapify(q)
ans=0
for i in range(1,M+1):
    for b in AB[i]:
        heapq.heappush(q,b)
    if len(q)>0:
        ans+=-heapq.heappop(q)
print(ans)

Submission status: Accepted

Solution code:
import heapq
#解説の方法
N,M = map(int,input().split())
AB = [[] for _ in range(10**5+1)]#報酬振り込み日数ごとに報酬を格納
for _ in range(N):
    a,b = map(int,input().split())
    AB[a].append(-b)
q = []
heapq.heapify(q)
ans =0
for i in range(1,M+1):
    for b in AB[i]:
        heapq.heappush(q,b)
    if len(q)>0:
        ans += -heapq.heappop(q)
print(ans)

Submission status: Accepted

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

AB.sort(key= lambda x:(-x[1],-x[0]))#報酬が高く、かつ、振り込みの日数が長いものからやるためのソート
memo = [0]*(10**5+1)#請け負うと決めた仕事の日のメモ。1がついている日は仕事がすでにある
work = [float('inf')]*(10**5+1)#振り込みまでに必要な日数のうち、前回請け負いを決めた日
noMore = float('inf') #これ以上の日数が振り込みにかかる仕事は受けれない
ans = 0
for a,b in AB:
    if a< noMore:#期日までに報酬が受け取れる仕事であること
        flag = 1
        for idx in range(min(M-a,work[a]),-1,-1):#この検索範囲の絞り込みがTLE解消の決め手。前回検索時に請け負った日またはM-a日以前の日
            if memo[idx] == 0:#仕事が請けられる
                ans += b#報酬を足す
                memo[idx]=1#仕事を受けたことの記録。この日はもう受けられない
                flag = 0#noMoreの更新分岐のため
                work[a] = idx#次回検索時のメモ
                break
        if flag ==1:#請けれる日が見つからなければ、今後この日数以上の日は受けれないので調べない
            noMore = a
    
print(ans)

Submission status: Accepted

Solution code:

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

AB.sort(key= lambda x:(-x[1],-x[0]))
memo = [0]*(10**5+1)#請け負うと決めた仕事の日
work = [float('inf')]*(10**5+1)

noMore = float('inf') #これ以上の日数が振り込みにかかる仕事は受けれない
ans = 0
for a,b in AB:
    if a< noMore:
        flag = 1
        for idx in range(min(M-a,work[a]),-1,-1):
            if memo[idx] == 0:#仕事が請けられる
                ans += b
                memo[idx]=1
                flag = 0
                work[a] = idx
                break
        if flag ==1:
            noMore = a
    
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

# [0日後(今日), 1日後, ..., M-1日後]
jobs = [[] for _ in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    if M - a >= 0:
        jobs[M - a].append(b)

ans = 0
q = []

# M-1日後にできる仕事, ..., 1日後, 0日後
# A >= 1なのでM日後にできる仕事はない

# heappop()で出てくるのは最小値
# 最大値が欲しい場合は-1倍してpush(), pop()して-1倍

# i = M-1, M-2, ..., 1, 0
for i in range(M - 1, -1, -1):
    for values in jobs[i]:
        heapq.heappush(q, -1 * values)
    if len(q) > 0:
        ans += heapq.heappop(q) * (-1)

print(ans)

Submission status: Accepted

Solution code:
from heapq import *
n,m=map(int,input().split())
ab=[]
ans=[[] for i in range(m)]
aa=0
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b*=-1
    ab.append((a,b))
ab.sort()
t=[]
heapify(t)
for a,b in ab:
    if a<m:
        ans[a].append(b)
for i in range(m):
    for j in ans[i]:
        heappush(t,j)
    if len(t)>0:
        tt=heappop(t)*(-1)
        aa+=tt
print(aa)

Submission status: Accepted

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
q, z = [], 0
v = [[] for _ in [None] * 10**5]
for a, b in t:
    v[a - 1] += b,
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    if q:
        z += -heappop(q)
print(z)

Submission status: Accepted

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
v = [[] for _ in [None] * 10**5]
for a, b in t:
    v[a - 1] += b,
z = 0
q = []
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    if q:
        z += -heappop(q)
print(z)

Submission status: Accepted

Solution code:
from heapq import*
(N, M), *t = [map(int, s.split()) for s in open(0)]
q = [0] * 10**5
v = [[] for _ in q]
for a, b in t:
    v[a - 1] += b,
z = 0
for i in v[:M]:
    for j in i:
        heappush(q, -j)
    z += -heappop(q)
print(z)

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()

N, M = inl()


class MinHeap(object):
    def __init__(self):
        self.h = []

    def push(self, x):
        heapq.heappush(self.h, x)

    def pop(self):
        return heapq.heappop(self.h)

    def __getitem__(self, i):
        return self.h[i]

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

    def __bool__(self):
        return bool(self.h)


class MaxHeap(MinHeap):
    class Negator(object):
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val > other.val

        def __eq__(self, other):
            return self.val == other.val

        def __str__(self):
            return str(self.val)

    def push(self, x):
        heapq.heappush(self.h, self.Negator(x))

    def pop(self):
        return heapq.heappop(self.h).val


def solve():
    jobs = []
    for i in range(N):
        a, b = inl()
        jobs.append((a, b))
    jobs.sort()

    hp = MaxHeap()
    ans = 0
    j = 0
    for d in range(1, M + 1):
        while j < N and jobs[j][0] == d:
            a, b = jobs[j]
            hp.push(b)
            j += 1
        if hp:
            ans += hp.pop()
    return ans


print(solve())

Submission status: Accepted

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

jobs = [[] for _ in range(M+1)]

for i in range(N):
    a, b = map(int, input().split())
    if a <= M:
        jobs[M-a].append(b)

ans = 0
priorityQueue = []
heapq.heapify(priorityQueue)
for i in range(M-1, -1, -1):
    for jobValues in jobs[i]:
        heapq.heappush(priorityQueue, -1*jobValues)
    if len(priorityQueue) > 0:
        ans += heapq.heappop(priorityQueue) * (-1)

print(ans)

Submission status: Accepted

Solution code:
import heapq

from typing import List


def main():
    n, k = map(int, input().split())
    v = []
    for _ in range(n):
        a, b = map(int, input().split())
        v.append((a, b))

    print(sv(v, k))


def sv(v: List[List[int]], k: int) -> int:
    vv = {}
    for a, b in v:
        if str(a) in vv:
            vv[str(a)].append(b)
        else:
            vv[str(a)] = []
            vv[str(a)].append(b)

    hp = []
    result = 0
    bk = 1
    while k >= bk:
        if str(bk) in vv:
            for b in vv[str(bk)]:
                heapq.heappush(hp, -b)
        if len(hp) > 0:
            result += -heapq.heappop(hp)
        bk += 1

    return result


if __name__ == '__main__':
    main()

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(key = lambda x:x[0])
ab.append([10 ** 10, 0])
ans = 0
cand = []
day = 1
pos = 0
while day <= m:
    while ab[pos][0] <= day:
        heapq.heappush(cand, ab[pos][1] * -1)
        pos += 1
    day += 1
    if cand:
        ans += heapq.heappop(cand) * -1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush 
N, M = map(int, input().split())
score = 0
AB = [[] for i in range(M)]
for i in range(N):
  a, b = map(int, input().split())
  if M - a >= 0:
    AB[M - a].append(b)
  
#print(AB)
queue = []
for i in range(1, M + 1):
  for j in AB[-i]:
    heappush(queue, -j)
  if queue != []:
    score += -1 * heappop(queue)
  
  #print(score, queue)  
print(score)

Submission status: Accepted

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

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

h = []
ans = 0
for i in range(1, m+1):
    for j in jobs[i]:
        heapq.heappush(h, j)
    if len(h) > 0:
        ans += -heapq.heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

input = sys.stdin.readline


def main():
    MAX_A = 10 ** 5
    N, M = map(int, input().split())
    AB = [[] for _ in range(MAX_A + 1)]
    for i in range(N):
        A, B = map(int, input().split())
        AB[A].append(-B)

    p_queue = []
    ans = 0
    for m in range(1, M + 1):
        for b in AB[m]:
            heappush(p_queue, b)
        if p_queue:
            x = heappop(p_queue)
            x *= -1
            ans += x

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


class SegmentTree:
    """Segment Tree class.

    Args:
        N (int): Number of elements
        X (list[int]): List for initialization
        func (callable): Function for interval.
        init_v (int): Initial value that does not affect `func`.
            For example, specify INF when `func = min`.

    References:
        <https://en.wikipedia.org/wiki/Segment_tree>
    """
    def __init__(self, N, X, func, init_v):
        N_ = 1
        while N_ < N: N_ *= 2
        self.N = N_
        self.func = func
        self.init_v = init_v
        self.__build(X)

    def __build(self, X):
        # Initialize all nodes
        self.node = [[self.init_v, -1] for _ in range(2 * self.N)]  # 1-based index

        # Elementary intervals are stored
        for i, x in enumerate(X, self.N):
            self.node[i] = [x, i - self.N + 1]

        # The internal nodes correspond to intervals that are the union of elementary intervals
        for i in range(self.N - 1, 0, -1):
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def update(self, i, x):
        """Update the i-th node value to x.

        Args:
            i (int): index (1-based index)
            x (int): udpate value
        """
        i += self.N - 1
        self.node[i][0] = x
        while i > 1:
            i >>= 1
            self.node[i] = self.func(self.node[i << 1], self.node[i << 1 | 1])

    def query(self, l, r):
        """Query for right half-open interval [l, r).

        Args:
            l (int): index (1-based index)
            r (int): index (1-based index)
        """
        dst_l = [self.init_v, -1]
        dst_r = [self.init_v, -1]
        l += self.N - 1
        r += self.N - 1
        while l < r:
            if l & 1:
                dst_l = self.func(dst_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                dst_r = self.func(self.node[r], dst_r)
            l >>= 1
            r >>= 1
        return self.func(dst_l, dst_r)


def func(a, b):
    return a if a[0] > b[0] else b


def main():
    N, M = map(int, input().split())
    AB = [None] * N
    for i in range(N):
        AB[i] = tuple(map(int, input().split()))

    AB.sort(key=lambda x: x[0])
    B = [0] * N
    C = [0] * (1 + 10 ** 5)
    for i, (a, b) in enumerate(AB):
        B[i] = b
        C[a] += 1
    C = list(accumulate(C))

    st = SegmentTree(N, B, func, -1)
    ans = 0
    l = 1
    for r in C[1:M + 1]:
        if r == 0:
            continue
        x, i = st.query(l, r + 1)
        if x == -1:
            continue
        ans += x
        st.update(i, -1)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

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

AB = [[] for _ in range(M)]
for _ in range(N):
    a, b = map(int, input().split())
    if a > M: continue
    AB[M-a].append(b)

q = []
heapq.heapify(q)
ans = 0
for i in range(M-1, -1, -1):
    if len(AB[i]) != 0:
        for b in AB[i]:
            heapq.heappush(q, -b)
    if len(q) != 0:
        ans += heapq.heappop(q)
print(-ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
lis = [[] for i in range(10**5+10)]
for i in range(N):
    A,B = map(int,input().split())
    lis[A-1].append(-B)
ans = 0
d = []
heapq.heapify(d)
for i in range(M):
    for j in lis[i]:
        heapq.heappush(d,j)
    if len(d) > 0:
        ans += heapq.heappop(d)*-1
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
S = list()
A = [list() for _ in range(M+1)]
for _ in range(N):
    a, b = map(int, input().split())
    if M < a:
        continue
    heapq.heappush(A[a], -b)

ans = 0
for i in range(1, M+1):
    for num in A[i]:
        heapq.heappush(S, num)
    if S == []:
        continue
    ans -= heapq.heappop(S)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

# import numpy as np
import bisect as bi
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        bi.insort(now,b)
    #print(nouki, now)
    if now==[]:continue
    ans+= now[-1]
    del now[-1]


print(ans)

Submission status: Accepted

Solution code:
def main():
    import heapq
    n,m = map(int,input().split())
    A = {}
    for i in range(n):
        a,b = map(int,input().split())
        if a not in A.keys():
            A[a] = [b]
        else:
            A[a].append(b)
    J = []
    ans = 0
    for i in range(1,m+1):
        if A.get(i)!=None:
            for k in A[i]:
                heapq.heappush(J,-1*k)
        if len(J)>0:
            ans += -1* heapq.heappop(J)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
arubaito = [list(map(int, input().split())) for _ in range(N)]
arubaito.sort()
arubaito2 = [[] for _ in range(M+1)]
for i in range(N):
    if arubaito[i][0] <= M:
        arubaito2[arubaito[i][0]].append(arubaito[i][1])
for i in range(M):
    arubaito2[i].sort(reverse=True)
target = []
ans = 0
heapq.heapify(target)
for i in range(1,M+1):
    for k in arubaito2[i]:
        heapq.heappush(target,k*(-1))
    if len(target) > 0:
        ans += heapq.heappop(target)*(-1)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

ab = []

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

ab.sort()

d = 1

w = []
heapq.heapify(w)

p = 0
d = 1
i = 0
while d <= m:
    while i < n and ab[i][0] == d:
        a, b = ab[i]
        heapq.heappush(w, -b)
        i += 1
    #print(w)
        #d日前にやる仕事をきめる
    if len(w) > 0:
        p -= heapq.heappop(w)

    d += 1


print(p)

Submission status: Accepted

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

t = []
heapq.heapify(t)
ans = 0
for i in range(m):
    for dd in d[i]:
        heapq.heappush(t, dd)
    if t:
        ans += heapq.heappop(t)*(-1)
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:
        continue
    jobs[A-1].append(-B)

total = 0
heap = []
for i in range(M):
    for job in jobs[i]:
        heapq.heappush(heap, job)

    if len(heap) == 0:
        continue
    else:
        total += -heapq.heappop(heap)

print(total)

Submission status: Accepted

Solution code:
from heapq import *
from collections import defaultdict
N, M = map(int, input().split())
data = defaultdict(list)
for _ in range(N):
    A, B = map(int, input().split())
    data[A].append(-B)

res = 0
temp = []
for i in range(1,M+1):
    for a in data[i]:
        heappush(temp,a)
    if temp:
        res -= heappop(temp)
print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

day = [[] for _ in range(10 ** 5)]
for a, b in ab:
    day[a - 1].append(b)

work, ans = [], 0
for i in range(m):
    for j in day[i]:
        heappush(work, -j)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

Submission status: Accepted

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

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

day = defaultdict(list)
for a, b in ab:
    day[a].append(b)

work, ans = [], 0
for i in range(1, m + 1):
    for j in day[i]:
        heappush(work, -j)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

Submission status: Accepted

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

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

day = defaultdict(list)
for a, b in ab:
    heappush(day[a], -b)

work, ans = [], 0
for i in range(1, m + 1):
    for j in day[i]:
        heappush(work, j)
    if len(work) > 0:
        ans -= heappop(work)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
N, M = map(int, input().split())
B = [[] for _ in range(M + 1)]
for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    if a <= M:
        B[a].append(b)

ans = 0
q = []
for i in range(1, M + 1):
    for b in B[i]:
        heapq.heappush(q, -b)
    if q:
        ans += -(heapq.heappop(q))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split())
arbeit = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a > m:
        continue
    heappush(arbeit[a-1], -b)

ans = 0
next_vals = []
for i in range(m):
    if any(arbeit[i]):
        b = heappop(arbeit[i])
        heappush(next_vals, (b, i))
    if any(next_vals):
        b, i = heappop(next_vals)
        ans -= b
        if any(arbeit[i]):
            b = heappop(arbeit[i])
            heappush(next_vals, (b, i))
print(ans)

Submission status: Accepted

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

Work = []
for i in range(n):
    Work.append(list(map(int, input().split())))
Work.sort(key=lambda x: (x[0], x[1]), reverse=True)
#print(Work)

total = 0
job_stock = []
#-1をかけた値を格納
heapq.heapify(job_stock)
for day in range(m, -1, -1):
    allowed_delay = m - day
    try:
        while Work[-1][0] <= allowed_delay:
            delay, money = Work.pop()
            heapq.heappush(job_stock, -money)
    except:
        pass
    if len(job_stock) >= 1:
        job_today = -heapq.heappop(job_stock)
        total += job_today
print(total)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = list(tuple(map(int, input().split())) for i in range(N)) #改行行列

    s=heapify(S)
    q=[]
    tot=0
    for i in range(1,M+1):
        while S and S[0][0]<=i:
            a,b=heappop(S)
            heappush(q,-b)
        if q:
            tot+=-heappop(q)
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import factorial as fact
import math
import sys
from itertools import product
import numpy as np
from collections import Counter
import datetime
from collections import deque
from bisect import bisect_left, bisect_right
import heapq



#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))


n,m=input2()
AB=[[] for _ in range(m)]


for i in range(n):
	a,b=input2()
	if a-1 < m: #報酬受取日がmを超える仕事は除外する
		AB[a-1].append(-b) #heapqの仕様のため，-を追加

ans=0
heap=[]
for i in range(m):
	for b in AB[i]:
		heapq.heappush(heap,b)
	#最大値をheapから取り出し
	if len(heap)>0:
		MAX=heapq.heappop(heap)
		ans+= -MAX
print(ans)

Submission status: Accepted

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


class MaxHeapObj(object):
  def __init__(self, val):
    self.val = val

  def __lt__(self, other):
    return self.val > other.val

  def __eq__(self, other):
    return self.val == other.val

  def __str__(self):
    return str(self.val)


class MinHeap(object):
  def __init__(self, L=None):
    if L is None:
      self.h = []
    else:
      heapq.heapify(L)
      self.h = L

  def heappush(self, x):
    heapq.heappush(self.h, x)

  def heappop(self):
    return heapq.heappop(self.h)

  def __getitem__(self, i):
    return self.h[i]

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


class MaxHeap(MinHeap):
  def __init__(self, L=None):
    super(MaxHeap, self).__init__(list(map(lambda x: MaxHeapObj(x), L)))

  def heappush(self, x):
    heapq.heappush(self.h, MaxHeapObj(x))

  def heappop(self):
    return heapq.heappop(self.h).val

  def __getitem__(self, i):
    return self.h[i].val


def main():
  N, M = list(map(int, input().split()))
  L = []
  for i in range(N):
    a, b = map(int, input().split())
    L.append((a, b))
  L = sorted(L)

  H = []
  PQ = MaxHeap(H)
  max_ = 0

  start = 0
  for m in range(M-1, -1, -1):
    res = M - m
    while start < N and L[start][0] == res:
      PQ.heappush(L[start][1])
      start += 1

    if len(PQ):
      now = PQ.heappop()
      max_ += now

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:

from heapq import heappop, heappush

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

X.sort(reverse=True)
ans = 0
pq = []
for n in range(M + 1):
    while X and X[-1][0] <= n:
        a, b = X.pop()
        heappush(pq, -b)

    if pq:
        ans -= heappop(pq)

print(ans)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
l=[]
for i in range(N):
   l.append(list(map(int,input().split())))
l.sort()
import heapq
X=[]
S=0
ans=0
heapq.heapify(X)
for i in range(1,K+1):
   for j in range(S,N):
      if l[j][0]<=i:
         S+=1
         heapq.heappush(X,l[j][1]*-1)
      else:
         break
   try:
      tmp=heapq.heappop(X)
      ans+=tmp*-1
   except IndexError:
      continue
print(ans)

Submission status: Accepted

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

class node:
	def __init__(self,a_val, a_parent=None):
		self.val=a_val
		self.parent=a_parent
		self.right=None
		self.left=None

def main2():
	n, m = IN()
	vl=[]
	for n in range(n):
		a,b = IN()
		vl.append((a,b))
		
	vl.sort(key=lambda x:-x[1])
	ret = 0
	nwdl=[-1]*(m+1) #list(range(m+1))
	for a, b in vl:
		j=m-a
		while j >= 0:
			if nwdl[j]==-1:
				nwdl[j]=0
				ret+=b
				break
			j-=1
		#pa((a,b,m-a,nwdl))
	print(ret)
	
	
def main():
	n, m = IN()
	st_day=[[] for _ in range(m+1)]
	for n in range(n):
		duration, pay = IN()
		if duration > m:
			continue
		st_day[m-duration].append(pay)
	
	pq=queue.PriorityQueue()
	ret = 0
	for di in range(m+1):
		day=m-di
		for pay in st_day[day]:
			pq.put(-pay)
		if not pq.empty():
			v = pq.get()
			ret -= v
	print(ret)
			
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
n,m = map(int,input().split())
A = []
for _ in range(n):
    a,b = map(int,input().split())
    A.append((a,-b))
A.sort()
A = deque(A)
hq = []
ans = 0
for i in range(1,m+1):
    while A:
        if A[0][0] ==i:
            tmp = A.popleft()
            heapq.heappush(hq,tmp[1])
        else:
            break
    if len(hq) == 0:
        continue
    else:
        ans += heapq.heappop(hq)
print(-ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(n)]

    AB.sort(key=lambda x: x[0])
    H = []
    ans = 0
    mi = 1
    for a, b in AB:
        while a > mi:
            if len(H) > 0:
                ans += -heapq.heappop(H)

            mi += 1
            if mi > m:
                break

        if a > m:
            break

        heapq.heappush(H, -b)

    while mi <= m and len(H) > 0:
        ans += -heapq.heappop(H)
        mi += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
X = [[]*3 for i in range(M)]
for i in range(N):
    A,B = list(map(int,input().split()))
    if A>M:
        continue
    else:
        X[M-A].append(B)

import heapq
out = 0
Y = []
heapq.heapify(Y)
for i in range(M):
    P = M-1-i
    Ls = X[P]
    for L in Ls:
        heapq.heappush(Y, -1*L)
    if len(Y)>0:
        Q = heapq.heappop(Y)
        out += -1*Q
print(out)

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())
A = [[] for _ in range(m)]
ans = 0

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

available = []

for i in range(m-1, -1, -1):
    for item in A[i]:
        heapq.heappush(available, -item)
    if available:
        ans += -heapq.heappop(available)

print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int, input().split())
ab = [[] for i in range(m+1)]
d = []
for i in range(n):
    a,b=map(int, input().split())
    if(not a>m):
        ab[a-1].append(-1*b)
res = 0
cnt = 0

for i in range(m):
    for j in range(len(ab[i])):
        heapq.heappush(d,ab[i][j])
    if(len(d)):
        res+=(heapq.heappop(d))
print(-1*res)