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: Wrong Answer

Solution code:
N, M = map(int, input().split())  # N件のアルバイト, M日後までの報酬
hoge = M  # M日後まではもらえる
arubaito = [list(map(int, input().split())) for _ in range(N)]  # A日後に, B円報酬がもらえる。

arubaito = sorted(arubaito, key=lambda x: (x[1], x[0]), reverse=True)  # 報酬が高い順にソート, 報酬が同じならもらえるまでに時間がかかる方を先にする。
ans = 0

for i in range(N):
    if hoge >= arubaito[i][0]:  # その仕事の報酬を得ることができるなら仕事を行う
        ans += arubaito[i][1]
        hoge -= 1  # その日雇いアルバイトしたなら日付を進める

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

N, M = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    heapq.heappush(AB, (a, b))

print(N, M, AB)

ans = 0
work = []
for i in range(M):
    remain = i + 1
    # print('remain={}, AB={}, ans={}'.format(remain, AB, ans))
    while len(AB) > 0:
        ab = heapq.heappop(AB)
        if ab[0] > remain:
            heapq.heappush(AB, ab)
            break
        heapq.heappush(work, (-ab[1], ab[0]))
    if len(work) == 0:
        continue
    v = heapq.heappop(work)
    ans -= v[0]
    # print('work={}'.format(work))
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = input().split()
N,M = int(n),int(m)
rest = M
p = 0
box = []
for i in range(N):
  box.append([int(s) for s in input().split()])
  
box.sort(key=lambda x:(-x[1], -x[0]))
for k in range(M):
  for i,j in enumerate(box):
    dels = []
    if j[0] > rest:
      dels.append(i)
    elif j[0] <= rest:
      p += j[1]
      dels.append(i)
      dels.reverse()
      for l in dels:
        del box[l]
      break
  rest -= 1
  
print(p)

Submission status: Wrong Answer

Solution code:
n,m = input().split()
N,M = int(n),int(m)
rest = M
p = 0
box = []
for i in range(N):
  box.append([int(s) for s in input().split()])
  
box.sort(key=lambda x:(-x[1], -x[0]))

for k in range(M):
  for i,j in enumerate(box):
    if j[0] > rest:
      del box[i]
    elif j[0] <= rest:
      p += j[1]
      del box[i]
      break
  rest -= 1
  
print(p)

Submission status: Wrong Answer

Solution code:
n,m = input().split()
N,M = int(n),int(m)
rest = M
p = 0
box = []
for i in range(N):
  box.append([int(s) for s in input().split()])
  
box.sort(key=lambda x:(-x[1], -x[0]))
print(box)
for k in range(M):
  for i,j in enumerate(box):
    if j[0] > rest:
      del box[i]
    elif j[0] <= rest:
      p += j[1]
      del box[i]
      break
  rest -= 1
  
print(p)

Submission status: Wrong Answer

Solution code:
n,m = input().split()
N,M = int(n),int(m)
rest = M
p = 0
box = []
for i in range(N):
  box.append([int(s) for s in input().split()])
box.sort(key=lambda x:-x[0])
box.sort(key=lambda x:-x[1])

for k in range(M):
  for i,j in enumerate(box):
    if j[0] <= rest:
      p += j[1]
      del box[i]
      break
  rest -= 1
  
print(p)

Submission status: Wrong Answer

Solution code:
n,d=map(int,input().split())
a={}
for i in range(n):
  td,tp=map(int,input().split())
  if a.get(td)==None:
    a[td]=[tp]
  else:
    a[td].append(tp)
r=0
for i in range(d):
  for k in list(a.keys()):
    if i+k>d or not a[k]:
      del a[k]
  if not a:
    break
  m=max(max(kl) for kl in a.values())
  r+=m
  for j in sorted(list(a.keys()), reverse=True):
    if m in a[j]:
      a[j].remove(m)
      break
print(r)

Submission status: Wrong Answer

Solution code:
IN1 = input()
N, M = [int(x) for x in IN1.split()]

IN2 = [[int(x) for x in input().split()] for _ in range(N)]
# 戦略 残りj日のとき働くべき：j日より期限が短く、最大の報酬が得られるもの
j = 1
E = 0
while j < M+1:
    j_choices = [x for x in IN2 if x[0] <= j]
    #print(j_choices)
    #print(len(j_choices))
    if len(j_choices) > 1:
        M = max([x[1] for x in j_choices])
        j_choices = [x for x in j_choices if x[1] == M]
        m = min([x[0] for x in j_choices])
        j_choice = [x for x in j_choices if x[0] == m][0]
        E = E + j_choice[1]
        IN2.remove(j_choice)
    elif len(j_choices) == 1:
        j_choice = j_choices[0]
        #print(j_choice)
        E = E + j_choice[1]
        IN2.remove(j_choice)
    j+=1
print(E)

Submission status: Wrong Answer

Solution code:
import heapq

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

d = {}
for a,b in AB:
    d.setdefault(a, []).append(b)

ans = 0
hp = []
for v in d.values():
    for b in v:
        heapq.heappush(hp, -b)
    if hp: ans += -heapq.heappop(hp)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for i in range(n)]
# 必要な日数の照準にソートする
jobs.sort()
# 次に選ぶバイト候補の保存場所
money = []
ans = 0

i = 0
# より制約の強い、最終リミットに近い日に行うバイトの割当てから攻めていく
for limit in range(1, m + 1):
    # limit日までに報酬のもらえるアルバイトを抽出
    while i < n and jobs[i][0] <= m:
        a = jobs[i][0]
        b = jobs[i][1]
        # 次に選ぶバイト候補に追加
        heapq.heappush(money, -b)
        i += 1
    # 要素数が空の場合のエラー処理
    if money != []:
        ans -= heapq.heappop(money)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
jobs = [tuple(map(int, input().split())) for i in range(n)]
# 必要な日数の照準にソートする
jobs.sort()
# 次に選ぶバイト候補の保存場所
money = []
ans = 0

# より制約の強い、最終リミットに近い日に行うバイトの割当てから攻めていく
for limit in range(1, m + 1):
    for a, b in jobs:
        # limit日までに報酬のもらえるアルバイトを抽出
        if a == limit:
            # 次に選ぶバイト候補に追加
            heapq.heappush(money, -b)
            jobs.pop(0)
        elif a > limit:
            break
    # 要素数が空の場合のエラー処理
    if money != []:
        ans += heapq.heappop(money) * (-1)

print(ans)