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 collections import defaultdict
import sys, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()

job_dict = defaultdict(lambda: list())
for i in range(N):
    d, r = read_int()
    job_dict[d].append(-r)

hq = []
heapq.heapify(hq)

def solve():
    ans = 0
    for i in range(1, M + 1):
        for j in job_dict[i]:
            heapq.heappush(hq, j)
        if hq:
            ans += - heapq.heappop(hq)
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
# from collections import defaultdict
import sys, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N, M = read_int()

jobs = [[] for _ in range(M + 1)]
for i in range(N):
    d, r = read_int()
    if d <= M:
        jobs[d].append(-r)


hq = []
heapq.heapify(hq)

def solve():
    ans = 0
    for i in range(1, M + 1):
        for j in jobs[i]:
            heapq.heappush(hq, j)
        if hq:
            ans += - heapq.heappop(hq)
    return ans

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
# -*- coding utf-8 -*-
import heapq
MOD = 10 ** 9 + 7

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

AB.sort(key=lambda x: -x[0])

ans = 0
hq = []
for i in range(M + 1):
    while len(AB) != 0 and AB[-1][0] <= i:
        ab = AB.pop()
        ba = [-ab[1], ab[0]]
        heapq.heappush(hq, ba)

    if len(hq) != 0:
        ans += heapq.heappop(hq)[0]

print(-ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import functools
def sorted_by(a, b):
    if a[0] > b[0]:
        return a[0] - b[0]
    if a[0] == b[0]:
        return b[1] - a[1]
    return -1

def solve(n, m, a, b):
    v = sorted(zip(a, b), key=functools.cmp_to_key(sorted_by))
    i = 0
    q = []
    ans = 0
    for t in range(1, m+1):
        while (i < n) and (v[i][0] <= t):
            heappush(q, -v[i][1])
            i += 1
        if len(q) > 0:
            ans -= heappop(q)
    return ans

n, m = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
print(solve(n, m, a, b))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
import heapq
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N, M = _li()

a_list = []
b_list = []
for _ in range(N):
    a, b = _li()
    a_list.append(a)
    b_list.append(b)

a_list = np.array(a_list)
b_list = np.array(b_list)
index = np.argsort(a_list)
a_list = a_list[index]
b_list = b_list[index]

ans = 0
cand = []
start = 0
for i in range(1, M+1):
    for j in range(start, N):
        if a_list[j] <= i:
            heapq.heappush(cand, -b_list[j])
            start = j+1
        else:
            break
    if len(cand) > 0:
        ans -= heapq.heappop(cand)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from heapq import *
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
job = defaultdict(list)
for _ in range(N):
	A, B = MAP()
	job[A].append(-B)

ans = 0
l = []

for i in range(1, M+1):
	for j in job[i]:
		heappush(l, j)
	if l:
		ans += -heappop(l)

print(ans)

Submission status: Accepted

Solution code:
from heapq import *
n,m=map(int,input().split())
ss={}
it=[0]*n
for i in range(n):
    a,b=map(int,input().split())
    it[i]=b
    try:
        ss[m-a].append(i)
    except:
        ss[m-a]=[i]
heap=[]
tot=0
for i in range(m-1,-1,-1):
    try:
        x=ss[i]
        for i in x:
            heappush(heap,-it[i])
    except:
        pass
    if heap==[]:
        continue
    a=heappop(heap)
    tot-=a
print(tot)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    jobs = {}
    for _ in range(N):
        A, B = map(int, input().split())
        if A > M:
            continue
        if A in jobs.keys():
            jobs[A] += [-B]
        else:
            jobs[A] = [-B]

    profit = 0
    days = jobs.keys()
    potential_jobs = []
    
    # M-1日後から今日まで遡る
    for elappsed_day in range(1, M+1):
        if elappsed_day in days:
            for job in jobs[elappsed_day]:
                heappush(potential_jobs, job)
        if len(potential_jobs) > 0:
            profit += heappop(potential_jobs)
            
    print(-profit)

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()

h=[]
ans=0
j=0

for i in range(1,m+1):
    while j<n:
        if ab[j][0]>i:
            break
        else:
            heapq.heappush(h,-ab[j][1])
            j += 1
            
    if h!=[]:
        k=-heapq.heappop(h)
        ans+=k

print(ans)

Submission status: Accepted

Solution code:
# D - Summer Vacation
from heapq import *
from collections import defaultdict

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

result = 0
pool = []
for i in range(1, m+1):
    for j in jobs[i]:
        heappush(pool, j)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
jobs=[[] for _ in range(m)]
for i in range(n):
    d,r=map(int,input().split())
    if d-1<m:
        jobs[d-1].append(-r)
rewards=0
heap=[]
for i in range(m):
    for reward in jobs[i]:
        heapq.heappush(heap,reward)
    if len(heap)>0:
        rewards+=-heapq.heappop(heap)

print(rewards)

Submission status: Accepted

Solution code:
#abc137d
import heapq

n,m=map(int,raw_input().split())
ab=[]
for i in xrange(n):
 l=map(int,raw_input().split())
 ab.append(l)
ab=sorted(ab,reverse=True)
q=[]
res=0
for i in xrange(1,m+1):
 while ab and ab[-1][0]==i:
  heapq.heappush(q,ab.pop()[1]*(-1))
 if q:
  res-=heapq.heappop(q)
print res

Submission status: Accepted

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

X = []

for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        X.append((a,b))


X = sorted(X, key=lambda x:(x[0], x[1]), reverse=True)

# print(X)
q = []
ans = 0
for i in range(1, M + 1):
    while X and X[-1][0] <= i:
        _, b = X.pop()
        heappush(q, -b)
    if q:
        ans -= heappop(q)
        
print(ans)

Submission status: Accepted

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

def main():
    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 = sorted(ab, key=lambda x: (x[0], x[1]))
    # print(ab)
    q = []
    j = 0
    ans = 0
    for i in range(M):
        # 候補の追加
        while j < len(ab):
            a, b = ab[j]
            if a <= i+1:
                heapq.heappush(q, (-b, a))
            else:
                break
            j += 1
        # 最大のものを取り出す
        if len(q) > 0:
            b, a = heapq.heappop(q)
            # print("day", M-i-1, "->", -b)
            ans += -b
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import *
from collections import defaultdict

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

result = 0
pool = []
for i in range(1, m+1):
    for j in jobs[i]:
        heappush(pool, j)
    if 0 < len(pool):
        result += -heappop(pool)

print(result)

Submission status: Accepted

Solution code:
import heapq

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

for i in s:
    if i[0] <= M:
        jobs[i[0]-1].append(-i[1])

condidate=[]
rewards=0
for k in range(M):
    for reward in jobs[k]:
        heapq.heappush(condidate, reward)
    if len(condidate) > 0:
        reward = heapq.heappop(condidate)
        rewards += -reward

print(rewards)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def resolve():
    n, m = map(int, input().split())
    jobs = [[] for _ in range(m+1)]
    for i in range(n):
        days, reward = map(int, input().split())
        if days <= m:
            jobs[days].append(-reward)

    res = 0
    heap = []
    # 残りi日の時点でどの仕事をするか
    for i in range(m+1):
        for j in jobs[i]:
            heappush(heap, j)
        if len(heap) > 0:
            res += -heappop(heap)

    print(res)
resolve()

Submission status: Accepted

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

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

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

dic = defaultdict(list)
for a, b in lst:
    dic[a].append(b)

heap = []
heapify(heap)

r = 0
for i in range(1, M + 1):
    can = dic[i]
    while can:
        heappush(heap, -can.pop(0))

    if len(heap) != 0:
        r += heappop(heap) * (-1)

print(r)

Submission status: Accepted

Solution code:
import heapq
n,m = list(map(int,input().split()))
jobs = [[] for _ in range(m)]
for i in range(n):
    d,r = list(map(int,input().split()))
    if d-1 < m:
        jobs[d-1].append(-r)
rewords = 0
heap = []
for i in range(m):
    for reword in jobs[i]:
        heapq.heappush(heap,reword)
    if len(heap) > 0:
        reword = heapq.heappop(heap)
        rewords += -reword
print(rewords)

Submission status: Accepted

Solution code:
import heapq
import sys
from collections import defaultdict

input = sys.stdin.readline
N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split())
jobs = [[] for _ in range(M+1)]
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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[1]))
q = []

res = 0
idx = 0
for i in range(1,m+1):
    while idx<n and ab[idx][0]<=i:
        heapq.heappush(q,-ab[idx][1])
        idx += 1

    if len(q)>0:
        res += -q[0]
        heapq.heappop(q)

print(res)

Submission status: Accepted

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

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

heap = []
res = 0
for m_i in range(1, m + 1):
    for i in in_dict.get(m_i, []):
        heappush(heap, -i)
    if heap:
        res += -heappop(heap)

print(res)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
def main():
    n,m = map(int,input().split())
    dc = defaultdict(list)
    for _ in range(n):
        a,b = map(int,input().split())
        dc[a].append(-b)
    a = []
    ans = 0
    for i in range(1,m+1):
        for j in dc[i]:
            heapq.heappush(a,j)
        if len(a)==0:
            pass
        else:
            ans += -1 * heapq.heappop(a)
    
    print(ans)
            
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc137/submissions/6808061

heapq構造をうまく使っている
「要素を追加」＆「その要素から最小値を取得」といったものを大規模に早く処理したい場合はこのやり方が基本となりそう
"""

import sys
from heapq import heappush, heappop
 
n, m = list(map(int, input().split()))
works = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > m:
        continue
    works.append((a, b))
 
works.sort(reverse=True) # works [(4, 3), (4, 1), (2, 2)]

q = []
ans = 0
for i in range(1, m + 1):
    ## 日単位で報酬をqueueに入れる＆worksのリストから削除
    # 仕事がある、かつ、まだ給料を受け取ることができる
    while works and works[-1][0] <= i: 
        _, b = works.pop() # 報酬を取得&worksから削除
        heappush(q, -b) # queueに報酬の負の値を入れる(heapqは最小値を取得するものなので負の値にする)
    ## 一番報酬が高いものを選択
    if q:
        b = -heappop(q) # queueからもっとも報酬の高い仕事の報酬を取得&queueから削除
        ans += b

print(ans)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
Mod = 1000000007




def main(): #startline--------------------------------------------
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(N)]
    AB.sort(reverse = True)
    heap = []
    ans = 0
    for i in range(1,M+1):
        while AB and AB[-1][0]<=i:
            heappush(heap,-AB.pop()[1])
        if heap:
            ans -= heappop(heap)
    print(ans)
        
if __name__ == "__main__":
    main() #endline===============================================





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Accepted

Solution code:
import heapq as hq


def solve(n, m, jobs):
    """
    n: jobの数
    m: 期限
    jobs: (期日、報酬)のリスト
    """

    jobs.sort()

    sal = 0
    j = 0
    heap = []
    for d in range(1, m + 1):
        while j < n:
            job = jobs[j]
            if job[0] > d:
                break
            hq.heappush(heap, -job[1])
            j += 1
        # print(d, heap)
        if len(heap) > 0:
            sal = sal - hq.heappop(heap)
    return sal


n, m = [int(x) for x in input().split()]

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

print(solve(n, m, jobs))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
 
n, m = list(map(int, input().split()))
#print (n)
#print (m)
works = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a > m:
        continue
    works.append((a, b))
 
works.sort(reverse=True)
 
q = []
ans = 0
for i in range(1, m + 1):
    while works and works[-1][0] <= i:
        a, b = works.pop()
        heappush(q, -b)
    #print(q)
    if q:
        b = -heappop(q)
        ans += b
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key = itemgetter(0))
q = []
idx = 0
ans = 0
for i in range(1, m+1):
    while idx < n:
        a, b = ab[idx]
        if a <= i:
            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:
from heapq import heappush, heappop
 
N,M = map(int,input().split())

allhiyatoi = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    allhiyatoi[temp[0]].append(temp[1])
 
reward = 0
Q = []
for i in allhiyatoi:
    for j in i:
        heappush(Q,j*-1)
    if len(Q) == 0:
        continue
    reward -= (heappop(Q))

print(reward)