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
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
l=[[] for i in range(10**5)]
for i in range(N):
    a,b=map(int,input().split())
    l[a-1].append(b)
h=[]
import heapq
a=0
for i in range(M):
    for j in l[i]:
        heapq.heappush(h,-j)
    if h:
        a-=heapq.heappop(h)
print(a)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
from bisect import bisect_right

N, M = mapint()

from heapq import heappop, heappush
days = [[] for _ in range(M)]
for _ in range(N):
    a, b = mapint()
    if a>M:
        continue
    days[a-1].append(-b)

queue = []

ans = 0
for i in range(M):
    lis = days[i]
    for b in lis:
        heappush(queue, b)
    if queue:
        ans += heappop(queue)

print(-ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7
import heapq

N,M = I()
L = [l() for _ in range(N)]
A = deque([])
B = deque([])
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
q = []
heapq.heapify(q)
for i in range(1,M+1):
    for j in range(len(A)):
        if A[0] > i:
            break
        else:
            A.popleft()
            heapq.heappush(q,B.popleft()*-1)
    if q:
        ans += heapq.heappop(q)*-1
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
N,M = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
A = [(-A[i][1],A[i][0]) for i in range(N)]
A = deque(A)
heap = []
cnt = 0
for i in range(M-1,-1,-1):
    k = M-i
    while len(A)>0 and A[0][1]<=k:
        heapq.heappush(heap,A.popleft())
    if len(heap)>0:
        b,a = heapq.heappop(heap)
        b = -b
        cnt += b
print(cnt)

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
#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#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import 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 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)]
class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=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.sort(key=itemgetter(1),reverse=True)
    #print(S)
    ans=0
    fil=[1 for i in range(M)]

    tot=M
    bit=BIT(M)
    bit.initialize(fil)
    for s in S:
        a,b=s
        if a>M:continue
        #print(tot,tot-bit.get_sum(a-1),M+1-a)
        
        #print(a-1,M)
        t=bit.get_sum(a-1)
        #print(t,tot)
        if t>=tot:
            continue

        x=bit.find_kth_element(t+1)
        
        bit.add(x,-1)
        ans+=b
        tot-=1

    print(ans)
    


        




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 = sorted(AB, key=lambda x: x[0])

x = 0
res = 0

hq = []
heapq.heapify(hq)

for i in range(M):
    for j in range(x, N):
        if AB[j][0] > i+1:
            x = j
            break
        heapq.heappush(hq, AB[j][1]*-1)
    else:
        x = N
    
    if hq:
        res += heapq.heappop(hq)*-1

print(res)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N,M = map(int,input().split())
A = [[] for _ in range(M+1)]
#HQ = []
for i in range(N):
  a,b = map(int,input().split())
  if a <= M:
    A[a].append(b)
#print(A)
ans = 0
L = []
for day in range(1,M+1):
  for t in A[day]:
    heappush(L,-t)
  #print(L)
  if not L:
    continue
  temp = heappop(L)
  ans += -temp
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify
from collections import deque

N,M=map(int,input().split())
A,B,C = [0]*N,[0]*N,[0]*N
for i in range(N):
    A[i],B[i] = map(int,input().split())
    C[i]=[A[i],B[i]]
C.sort()
C=deque(C)

a=[]
heapify(a)
ans=0

for i in range(M,-1,-1):
    while C:
        if C[0][0]<=M-i:
            heappush(a,(-1)*C[0][1])
            C.popleft()
        else:
            break
    if len(a)>0:
        p = heappop(a)
        ans += (-1)*p
        
print(ans)

Submission status: Accepted

Solution code:
import sys
# from collections import defaultdict, deque
# import math
# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # update min with holding index
        return max(lch, rch)

    def unit(self):
        return -INF

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def solve():
    n, m = getList()
    baito = []
    for i in range(n):
        a, b = getList()
        baito.append((b, a))

    baito.sort(reverse=True)
    st = Segtree_op(m)
    for i in range(m):
        st.update(i, i)

    ans = 0
    for kin, hi in (baito):
        if hi > m:
            continue
        tgt = st.query(0, m - hi + 1)
        if tgt != -INF:
            ans += kin
            st.update(tgt,-INF)

    # st.show()
    # st.update(0, -10)
    # print(st.query(0, 1))
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
jobs = [inpl() for _ in range(n)]
jobs.sort()
can = []
ind = 0
res = 0
for i in range(1,m+1):
    while ind < n:
        a,b = jobs[ind]
        if a == i:
            heappush(can,-b)
            ind += 1
            continue
        break
    if can != []:
        res -= heappop(can)
print(res)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
d=[]
for i in range(n):
  a,b=map(int,input().split())
  d.append([a,b])
d=sorted(d, key=lambda student: student[0])
pointer=0
queue=[]
ans=0
for i in range(m+1):
  while pointer<n and d[pointer][0]==i:
    heapq.heappush(queue,-d[pointer][1])
    pointer+=1
    if pointer>=n:
      break
  if queue:
    ans+=heapq.heappop(queue)
print(-ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]+[[100000000,0]]
for i in range(m):ab.append([i+1,0])
ab.sort()
from heapq import heappop,heappush
h=[]
j=0
ans=0
for i in range(1,m+1):
  while ab[j][0]<=i:
    heappush(h,-ab[j][1])
    j+=1
  ans-=heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

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

print(-ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
b_list = [[] for _ in range(10**5+10)]

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

candy = []
heapq.heapify(candy)
ans = 0
for i in range(1,m+1):
    for j in b_list[i]:
        heapq.heappush(candy,j)
    if candy: 
        ans += (-1*heapq.heappop(candy))

print(ans)

Submission status: Accepted

Solution code:
import heapq
n , m = map(int,input().split())
kouho = [[] for i in range(m)]
for i in range(n):
    a , b = map(int,input().split())
    if a <= m:
        kouho[a-1].append(-b)
ans = 0
p = []
heapq.heapify(p)

for i in range(m):

    for j in kouho[i]:
        heapq.heappush(p,j)
    if p:
        ans -= heapq.heappop(p)
print(ans)

Submission status: Accepted

Solution code:
import heapq
n , m = map(int, input().split())
ab=[[] for i in range(10**5)]

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

que=[]
ans = 0
for i in range(m):
    for b in ab[i]:
        heapq.heappush(que,b)
    if que:
        ans+=heapq.heappop(que)
print(ans*(-1))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())

    J = [[] for _ in range(M)]
    for a, b in zip(*[iter(AB)] * 2):
        if a > M:
            continue
        J[a - 1].append(b)

    hq = []
    ans = 0
    for i in range(M):
        for b in J[i]:
            heappush(hq, -b)
        if hq:
            ans += -heappop(hq)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    ans = 0
    heap = []
    for a in range(M):
        for b in AB[a]:
            heappush(heap, b)
        if heap:
            ans -= heappop(heap)
    
    print(ans)

main()

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
al = [[] for i in range(10**5)]
ans = 0
h = []
for i in range(n):
    a,b = map(int,input().split())
    al[a-1] += [-b]
for i in range(m):
    for j in al[i]:
        heapq.heappush(h,j)
    if h:
        ans -= heapq.heappop(h)
print(ans)

Submission status: Accepted

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

N, M = list(map(int, input().split()))
jobs = defaultdict(list)
heap = []
ans = 0
for _ in range(N):
    a, b = list(map(int, input().split()))
    if a <= M:
        jobs[a].append(b)

for m in range(1, M+1):
    for b in jobs[m]:
        heappush(heap, -b)
    if heap:
        maxb = -heappop(heap)
        ans += maxb
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [[] for _ in range(m+1)]
for i in range(n):
  t = [int(inp) for inp in input().split()]
  if t[0] <= m:
    ab[t[0]].append(-t[1])
ans = 0
import heapq
h = ab[1]
heapq.heapify(h)
for i in range(1, m+1):
  if len(h) > 0:
    ans += heapq.heappop(h)
  if i != m:
    for t in ab[i+1]:
      heapq.heappush(h, t)
print(-ans)

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
n,m=map(int,input().split())
l=[[]for i in range(10**5)]
ans=0
for i in range(n):a,b=map(int,input().split());l[a-1].append(-b)
for i in range(10**5):heapify(l[i])
p = []
heapify(p)
for i in range(m):
 if len(l[i])!=0:heappush(p,[heappop(l[i]),i])
 if len(p)!=0:
  x=heappop(p)
  ans+=-x[0]
  if len(l[x[1]])!=0:heappush(p,[heappop(l[x[1]]),x[1]])            
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import heapq

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(n)]
    a_t = list(zip(*ab))
    AB = [[] for _ in range(m+1)]
    for a, b in zip(*a_t):
        if a <= m:
            AB[a].append(b*-1)
    # print(AB)
    cnt = 0
    h = [] 
    heapq.heapify(h)
    for i in AB:
        for j in i:
            heapq.heappush(h, j)
            # print('h', h)
        if h:
            cnt += heapq.heappop(h)
    print(-1*cnt)   

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(N, M, AB):
    AB.sort(key=lambda x: x[0], reverse=True)
    from heapq import heappop, heappush
    q = []
    ans = 0
    for i in range(1, M+1):
        while AB and AB[-1][0] <= i:
            _, b = AB.pop()
            heappush(q, -b)
        if q:
            ans += -heappop(q)
    return ans



def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n,m = map(int,input().split())
x = []
xa = x.append
for _ in range(n):
  ai,bi = map(int,input().split())
  xa((ai,bi))
x.sort(key=lambda a:a[0])
y = []
count = 0
j = 0
for i in range(1,m+1):
  while x[j][0] == i:
    heappush(y,-x[j][1])
    if j+1 < n:
      j += 1
    else:
      break
  if len(y) != 0:
    count -= heappop(y)
print(count)

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush

N,M = map(int,input().split())
AB=[]

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

AB.sort()
q = []
heapify(q)
cersol = 0
ans = 0
for i in range(0,M+1,1):#残り日数
    while 1:
        if cersol < N and AB[cersol][0] <= i:
            heappush(q,-AB[cersol][1])
            cersol+=1
        else:
            break
    if len(q)>0:
        ans += -heappop(q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush as hpush
from heapq import heappop as hpop

class Descending_HeapQueue:
    def __init__(self, hq=[]):
        self.hq = []
        for i in hq:
            self.push(i)
    def push(self, n):
        hpush(self.hq, -n)
    def pop(self):
        return -hpop(self.hq)
    def __len__(self):
        return len(self.hq)

def main():
    N, M = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    ans = 0
    dhq = Descending_HeapQueue()
    pointer = 0
    for m in range(1, M+1):
        while (pointer < N) and (AB[pointer][0] <= m):
            dhq.push(AB[pointer][1])
            pointer += 1
        if len(dhq) > 0:
            ans += dhq.pop()
    print(ans)
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.append([m+1,0])
ab = sorted(ab, key=lambda x:x[0])



max_values = [0 for _ in range(m)]
hq = []

possible_days = 0

for now in range(n+1):
    # if necessary day exceed the (now_day), extract the most valuable work
    while possible_days <= ab[now][0]:
        if len(hq) < 1:
            pass
        else:
            max_values[possible_days-2] = -heapq.heappop(hq)
        possible_days += 1
    if possible_days-2 > m-1:
        break
    heapq.heappush(hq, -ab[now][1])
print(sum(max_values))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
from collections import deque
N,M=map(int,input().split())
A=[0]*N #ラグ
B=[0]*N #報酬
C=[0]*N
for i in range(N):
    A[i],B[i]= map(int,input().split())
    C[i]=[A[i],B[i]]
C.sort()
D=deque(C)
reward=0
#print(D)

h=[]
heapify(h)

for i in range(M-1,-1,-1):   
    while D:
        e = D.popleft()
        if e[0]==M-i:
            heappush(h,-1*e[1])
        else:
            D.appendleft(e)
            break
    #print(h)
    if h:
        reward += (-1)*heappop(h)
        
print(reward)

Submission status: Accepted

Solution code:
import heapq as hq
import numpy as np

N, M = map(int, input().split())
job = [list(map(int, input().split())) for _ in range(N)]
ans = 0
job.sort()
job.append([np.inf, np.inf])
jobhq = []
index = 0
for day in range(1, M + 1):
    while day >= job[index][0]:
        hq.heappush(jobhq, - job[index][1])
        index += 1
    if jobhq:
        ans += - hq.heappop(jobhq)
print(ans)

Submission status: Accepted

Solution code:
def insertHeap(array, val):
    array.append(val)
    n = len(array)-1
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break
    return array

def desertHeap(array):
    if array == []:
      return None
    array[0], array[-1] = array[-1], array[0]
    res = array.pop(-1)
    n = len(array)
    if n == 0 or n == 1: 
      return res
    parent = 0
    while True:
        child = 2 * parent + 1
        if child >= n: break
        if (child + 1 < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]:
            array[child], array[parent] = array[parent], array[child]
            parent = child;
        else:
            break
    return res

n, m = map(int, input().split())
 
li = [[] for j in range(10**5+1)]
 
for _ in range(n):
  a, b = map(int, input().split())
  li[a].append(b)
 
ans = 0
jobsHeap = []
for i in range(1, m+1):
  for val in li[i]:
    jobsHeap = insertHeap(jobsHeap, val)
  
  if jobsHeap != []:
    res = desertHeap(jobsHeap)
    ans += res
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d

# 最終日に選ぶことができるのは、Ai=1だけ
# 最終-1日に選ぶことができるのは、Ai=1,2だけ

from collections import defaultdict
from heapq import heapify, heappush, heappop

n, m = map(int, input().split())
d = defaultdict(list)
queue = []

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

ans = 0
for i in range(1, m + 1):
    for j in d[i]:
        heappush(queue, -j) # j日目までを全部push
    if len(queue) > 0: # 取れたら最大を取ってきて足す
        ans += heappop(queue) * -1

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    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)
    
    ans=0
    q=[]
    #q=heapify([])
    for i in reversed(range(M)):
        for b in jobs[i]:
            heappush(q,-b)
        if not q: continue
        ans+= -heappop(q)
    print(ans)
    
    
    

resolve()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

import heapq as hq
pq = []
hq.heapify(pq)
n, m = map(int, input().split())
arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))
arr = sorted(arr, key=lambda x: x[0])
i = 0
ans = 0
for d in range(1, m + 1):
    while i < n and arr[i][0] <= d:
        hq.heappush(pq, -arr[i][1])
        i += 1
    if pq:
        ans -= hq.heappop(pq)
print(str(ans))

Submission status: Accepted

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

AB = []
for _ in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))
AB = sorted(AB, key=lambda x: x[0])

hq = []
heapq.heapify(hq)  # リストhqのheap化

ans = 0
i = 0
for d in range(1, M+1):
    while i <= N-1 and AB[i][0] <= d:
        heapq.heappush(hq, -AB[i][1])  # heap化されたリストhqに要素xを追加
        i += 1
    if hq:
        ans -= heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)] + [[1000000, 1000000]]
li.sort()
idx = 0
hq = []
ans = 0
for i in range(m):
    while li[idx][0] <= i + 1:
        heapq.heappush(hq, -li[idx][1])
        idx += 1
    if hq:
        ans -= heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10000000)

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)
q=[]
heapq.heapify(q)
ans=0

for i in range(m-1,-1,-1):
    for b in jobs[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())
jobs = [[] for _ in range(10 ** 5 + 100)]
# 隣接リストっぽく
for i in range(n):
    a, b = map(int, input().split())
    jobs[a].append(b)

hq = []
res, j = 0, 0
for i in range(1, m + 1):
    for v in jobs[i]:
        heappush(hq, -v)
    if len(hq) > 0:
        res += -heappop(hq)
print(res)

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())
    jobs.append([a, b])

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

hq = []
res, j = 0, 0
for i in range(1, m + 1):
    while j < n and jobs[j][0] <= i:
        heappush(hq, -jobs[j][1])
        j += 1
    if len(hq) > 0:
        res += -heappop(hq)
print(res)

Submission status: Accepted

Solution code:
import heapq
n,m = map(int,input().split())
dp = [0]*(n+1)
L = []
days = []
cost = []
for i in range(n):
    a,b = map(int,input().split())
    if a > m:
        continue
    L.append([a,b])

L.sort(reverse = True)

ans = 0
li = []
for i in range(1,m+1):
    while L and L[-1][0] <= i:
        (a,b) = L.pop()
        heapq.heappush(li,b*(-1))

    if li:
        h = heapq.heappop(li)
        ans +=(-1)*h

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

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

ans = 0
job_rew = []
heapq.heapify(job_rew)
for i in range(1, M+1):
    if i in day_rew:
        for r in day_rew[i]:
            heapq.heappush(job_rew, r*(-1))
    if job_rew:
        this_day_rew = heapq.heappop(job_rew)*(-1)
        ans += this_day_rew

print(ans)