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: Time Limit Exceeded

Solution code:
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
list = sorted(list)
for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      temp.append(list[j][1])
    else:
      a = j
      break
  ans += max(temp)
  l = int(len(temp) -1)
  if l >= 1:
    temp = sorted(temp)
    temp = temp[:l]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0

for i in range(1,1+m):
  for j in list:
    if j[0] == i:
      temp.append(j[1])
  ans += max(temp)
  l = int(len(temp) -1)
  if l >= 1:
    temp = sorted(temp)
    temp = temp[:l]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
list = sorted(list)
dp = [ [0 for i in range(m+1)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(1,m+1):
    if list[i-1][0] <= j:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+list[i-1][1])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
import math, heapq
from operator import itemgetter
from collections import defaultdict
INF = float("inf")
MOD = int(1e9 + 7)

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

ab = sorted(AB)

v, que = 0, []
for n in range(1, M + 1):
    while ab:
        a, b = ab.pop(0)
        if a <= n:
            heapq.heappush(que, -b)
        else:
            ab.insert(0, (a, b))
            break
    if que:
        v += -heapq.heappop(que)
print(v)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b = [], []
hp = [[] for _ in range(m+1)]
ignore = [0] * (n+1)
ans = 0
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
for x in range(1, m+1):
    candidate = []
    for i, e in enumerate(a):
        if e <= x and not ignore[i]: candidate.append(b[i])
    if candidate:
        m = max(candidate)
        ans += m
        ignore[b.index(m)] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
albeit = [list(map(int, input().split())) for i in range(N)]
days = [albeit[p][0] for p in range(N)]
reward = [albeit[q][1] for q in range(N)]

z = 1 #z日前
#M-z日目にどの仕事を請けるか
sum_r = 0
r_ = {}
days_ = {}
reward_ = {}

while M - z >= 0:
  r = [a for a, b in enumerate(days) if b == z]
  for c in r:
    r_[c] = c
    days_[c] = days[c]
    reward_[c] = reward[c]
      
  if len(r_) == 0:
    z += 1
    continue
  
  #print('index', r_, 'days', days_, 'reward', reward_)

  days__ = {}
  ind = [s for s , t in reward_.items() if t == max(reward_.values())]
  for f in ind:
    days__[f] = days_[f]
  ind_ = [d for d , e in days__.items() if e == min(days__.values())][0]
  
  #print(r_[ind_], days_[ind_], reward_[ind_], '!!!')
  sum_r += reward_[ind_]
  z += 1
  del r_[ind_]
  del days_[ind_]
  del reward_[ind_]
  days__.clear()

print(sum_r)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m = map(int, input().split())
job = {}
for i in range(n):
    a,b = map(int, input().split())
    if a not in job.keys():
        job[a] = [(-b,a)]
    else:
        job[a].append((-b,a))

hq = []

max_income = 0
for i in range(1,m+1):
    if i in job.keys():
        for j in job[i]:
            heapq.heappush(hq,(j))
    if len(hq) < 1:
        continue
    b_i, a_i = heapq.heappop(hq)
    max_income += -b_i

print(max_income)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

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

s = sorted(ABs, key=lambda x: (x[0], -x[1]))
g = [(x[0], list(x[1])) for x in groupby(s, key=lambda x: x[0])]

c = []
for x in g:
    for _ in range(x[0] - len(c) - 1):
        c.append([])
    c.append([v[1] for v in list(x[1])])
for _ in range(M - len(c)):
	c.append([])

reward = 0
cands = []
for i in range(M):
    cands.extend(c[i])
    if len(cands) > 0:
        best = max(cands)
        reward += best
        cands.remove(best)

print(reward)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

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

cands_list = [[] for _ in range(M)]
for x in ABs:
    if x[0]-1 < M:
    	cands_list[x[0]-1].append(x[1])

reward = 0
cands = []
for i in range(M):
    cands.extend(cands_list[i])
    if len(cands) > 0:
        best = max(cands)
        reward += best
        cands.remove(best)

print(reward)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
albeit = [list(map(int, input().split())) for i in range(N)]
albeit.sort(key = lambda x: x[1])
albeit.sort(key = lambda x: x[0]) 
albeit.reverse()

days = [albeit[p][0] for p in range(N)]
reward = [albeit[q][1] for q in range(N)]

z = 1 #z日前
#M-z日目にどの仕事を請けるか
sum_r = 0
r_ = {}
reward_ = {}

while M - z >= 0:
  tt = 0
  tt += len(days)-1
  for j in range(len(days)):
    if days[tt-j] == z:
      r_[tt-j] = days[tt-j] #daysの中からz日のものを抽出
      reward_[tt-j] = reward[tt-j] #抽出したr_のindexを持つrewardの値を抽出
      del days[tt-j]
      del reward[tt-j]
    else:
      break
      
  if len(r_) == 0:
    z += 1
    continue


  ind = max([s for s , t in reward_.items() if t == max(reward_.values())])
  sum_r += reward_[ind]
  z += 1
  del r_[ind]
  del reward_[ind]

print(sum_r)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
albeit = [list(map(int, input().split())) for i in range(N)]
albeit.sort(key = lambda x: x[1])
albeit.sort(key = lambda x: x[0]) 
albeit.reverse()

days = [albeit[p][0] for p in range(N)]
reward = [albeit[q][1] for q in range(N)]

z = 1 #z日前
#M-z日目にどの仕事を請けるか
sum_r = 0

while M - z >= 0:
  r_ = [s for s, t in enumerate(days) if t <= z] #daysの中からz日以下のものを抽出
  if len(r_) == 0:
    z += 1
    continue
  reward_ = {u:reward[u] for u in r_} #抽出したr_のindexを持つrewardの値を抽出
  ma = max(reward_.values())
  ss = [s for s , t in reward_.items() if t == ma]
  ind = max(ss)
  sum_r += reward_[ind]
  del days[ind]
  del reward[ind] 
  reward_.clear()
  r_.clear()
  z += 1

print(sum_r)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
albeit = [list(map(int, input().split())) for i in range(N)]
albeit.sort(key = lambda x: x[1])
albeit.sort(key = lambda x: x[0]) 
albeit.reverse()

days = [albeit[p][0] for p in range(N)]
reward = [albeit[q][1] for q in range(N)]

z = 1 #z日前
#M-z日目にどの仕事を請けるか
sum_r = 0

while M - z >= 0:
  if min(days) <= z:
    r_ = [s for s, t in enumerate(days) if t <= z] #daysの中からz日以下のものを抽出
    reward_ = {u:reward[u] for u in r_} #抽出したr_のindexを持つrewardの値を抽出
    ma = max(reward_.values())
    ss = [s for s , t in reward_.items() if t == ma]
    ind = max(ss)
    sum_r += reward_[ind]
    del days[ind]
    del reward[ind] 
    reward_.clear()
    r_.clear()
  z += 1

print(sum_r)

Submission status: Time Limit Exceeded

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

reward = 0
for i in range(M):
    cands = list(filter(lambda x: x[0] <= i+1, ABs))
    if len(cands) > 0:
        best = max(cands, key=lambda x: x[1])
        reward += best[1]
        ABs.remove(best)

print(reward)

Submission status: Time Limit Exceeded

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

reward = 0
for i in range(M):
    cands = list(filter(lambda x: x[1][0] <= i+1, [(i, ABs[i]) for i in range(len(ABs))]))
    if len(cands) > 0:
        best = max(cands, key=lambda x: x[1][1])
        reward += best[1][1]
        ABs.pop(best[0])

print(reward)

Submission status: Time Limit Exceeded

Solution code:
class Work:
    count=0
    def __init__(self,payday,money):
        Work.count+=1
        self.count=Work.count
        self.payday=payday
        self.money=money
 #moneyが大きい方、同じなら早くもらえる方、それも同じなら最初に書いてある方が強い方
    def __gt__(self,other):
        if self.money>other.money:
            return True
        if self.money==other.money:
            if self.payday<other.payday:
                return True
            if self.payday==other.payday:
                if self.count<other.count:
                    return True
        return False

    def __ft__(self,other):
        if self.money<other.money:
            return True
        if self.money==other.money:
            if self.payday>other.payday:
                return True
            if self.payday==other.payday:
                if self.count>other.count:
                    return True
        return False

#バイトの数、いつまでに稼ぐのか 
n,limit=[int(i) for i in input().split()]

#バイトのリストを作り、クラスを入れる O(n)
baitolist=[]
for i in range(n):
    payday,money=[int(i) for i in input().split()]
    work=Work(payday,money)
    baitolist.append(work)

#日数でランク付け　O(n)
summoney=0    
rank=[[] for i in range(limit+1)]
for baito in baitolist:
    if baito.payday<=limit:
        rank[baito.payday].append(baito)

accessible=[]
count=1
while baitolist and count<=limit:#最悪O(limit)
    for baito in rank[count]:
        accessible.append(baito)
    accessible.sort()
    if accessible!=[]:
        dowork=accessible.pop()
        summoney+=dowork.money
    count+=1
    
    
print(summoney)

Submission status: Time Limit Exceeded

Solution code:

import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  for d in range(1, reversed_day+1):
    if d in conditions.keys():
      heapq.heappush(candidates, -conditions[d].pop(0))
      if len(conditions[d]) == 0:
        del conditions[d]
  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

print(ans)

Submission status: Time Limit Exceeded

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

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

allaw = 1
result = 0
for _ in range(M, 0, -1):
    memo = []
    for i, x in enumerate(array):
        limit, reward = x
        if limit <= allaw:
            memo.append([i, reward])
    if memo:
        m = -1
        mi = None
        for i, r in memo:
            if r > m:
                m = r
                mi = i
        result += m
        array.pop(mi)
    allaw += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3


def main():
  n, m = map(int, input().strip().split(' '))
  liAB = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
  liAB.sort(key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      top.sort()
      if len(top) > a-k:
        s += sum(top[-(a-k):])
        del top[-(a-k):]
      else:
        s += sum(top)
        top = []
      k = a

    top.append(b)


  top.sort()
  s += sum(top[-(m-k+1):])
  print(s)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

import collections

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  if len(candidates) == 0:
    continue

  cnt, maxval, maxkey = 0, 0, 0
  for cands in candidates:
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = cnt
    cnt += 1
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3


def main():
  n, m = map(int, input().strip().split(' '))
  liAB = sorted([tuple(map(int, input().strip().split(' '))) for _ in range(n)], key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      top.sort()
      if len(top) > a-k:
        s += sum(top[-(a-k):])
        del top[-(a-k):]
      else:
        s += sum(top)
        top = []
      k = a

    top.append(b)


  top.sort()
  s += sum(top[-(m-k+1):])
  print(s)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

import collections

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
cond_keys = []
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in cond_keys:
    conditions[inputs[0]].append(inputs[1])
  else:
    cond_keys.append(inputs[0])
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = []
cand_len = 0
for reversed_day in range(1, m + 1):
  if reversed_day in cond_keys:
    candidates.append(conditions[reversed_day])
    cand_len += 1

  if cand_len == 0:
    continue

  cnt, maxval, maxkey = 0, 0, 0
  for cands in candidates:
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = cnt
    cnt += 1
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
    cand_len -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
cond_keys = []
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in cond_keys:
    conditions[inputs[0]].append(inputs[1])
  else:
    cond_keys.append(inputs[0])
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = []
cand_len = 0
for reversed_day in range(1, m + 1):
  if reversed_day in cond_keys:
    candidates.append(conditions[reversed_day])
    cand_len += 1

  if cand_len == 0:
    continue

  cnt, maxval, maxkey = 0, 0, 0
  for cands in candidates:
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = cnt
    cnt += 1
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
    cand_len -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3

from bisect import insort

def main():
  n, m = map(int, input().strip().split(' '))
  liAB = sorted([tuple(map(int, input().strip().split(' '))) for _ in range(n)], key=lambda x:x[0])

  k = 1
  top = []
  s = 0
  for a, b in liAB:
    if a >= m+1:
      break

    if k < a:
      if len(top) > a-k:
        s += sum(top[-(a-k):])
        del top[-(a-k):]
      else:
        s += sum(top)
        top = []
      k = a

    insort(top, b)


  s += sum(top[-(m-k+1):])

  print(s)
  
  pass

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc137/tasks/abc137_d
import sys
sys.setrecursionlimit(10 ** 6)

import collections

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = {}
cand_len = 0
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates[reversed_day] = conditions[reversed_day]
    cand_len += 1

  if cand_len == 0:
    continue

  maxval, maxkey = 0, 0
  for key, cands in candidates.items():
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = key
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
    cand_len -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().split()))
A=[]
B=[]
ans=0
for i in range(N):
    a,b=list(map(int,input().split()))
    A.append(a)
    B.append(b)
for j in range(1,M+1):
    temp=[[x,B[x]] for x in range(len(B)) if A[x]<=j]  
    if len(temp)>=1:
        temp=sorted(temp,key=lambda x:x[1],reverse=True)
        ans+=temp[0][1]
        A.pop(temp[0][0])
        B.pop(temp[0][0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from copy import deepcopy

def main():
    n, m = map(int,input().split())
    
    h = []
    for i in range(n):
        day, value = map(int,input().split())
        heappush(h, (-1*value, day))
    
    res = 0
    done = []
    for i in range(1, m+1):
        cur_h = deepcopy(h)
        while cur_h:
            r = heappop(cur_h)
            if r[1] <= i and not r in done:
                res += r[0]*-1
                done.append(r)
                break

    print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = {}
cand_len = 0
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates[reversed_day] = conditions[reversed_day]
    cand_len += 1

  if cand_len == 0:
    continue

  maxval, maxkey = 0, 0
  for key, cands in candidates.items():
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = key
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
    cand_len -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i, cands in enumerate(candidates):
    if cands[0] > maxval:
      maxval = cands[0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
  if len(candidates[maxidx]) == 0:
    del candidates[maxidx]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in conditions.keys():
    conditions[inputs[0]].append(inputs[1])
  else:
    conditions[inputs[0]] = [inputs[1]]

for day in conditions.keys():
  conditions[day].sort(reverse=True)

ans = 0
candidates = []
for reversed_day in range(1, m + 1):
  if reversed_day in conditions.keys():
    candidates.append(conditions[reversed_day])

  cand_len = len(candidates)
  if cand_len == 0:
    continue
  maxval, maxidx = 0, 0
  for i in range(cand_len):
    if candidates[i][0] > maxval:
      maxval = candidates[i][0]
      maxidx = i
  ans += candidates[maxidx].pop(0)
  if len(candidates[maxidx]) == 0:
    del candidates[maxidx]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 12 21:35:06 2019

@author: doppe
"""

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

listA = []
listB = []
for i in range (0, N):
    A, B = map(int, input().split())
    listA.append([A,B])
    
sortA = sorted(listA, key=lambda k: k[0])
#sortA, sortB = sorted(listA), sorted(listB, key=lambda k: listA[k])

#print(sortB)
count = 1
ans = 0
taishoList = []
k = 0
while True:
    for i in range(k, N):
        if (count == sortA[i][0]):
            taishoList.append(sortA[i][1])
            k += 1
        else:
            break
        
    if len(taishoList) != 0:
        maxValue = max(taishoList)
        ans += maxValue
        taishoList.remove(maxValue)
    count += 1
    if (count > M):
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
AB_list = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    while(len(AB_list) > 0 and AB_list[0][0] <= i):
        tmp = AB_list.pop(0)
        h.append(tmp[1])
    if (len(h)):
        tmp = max(h)
        h.pop(h.index(tmp))
        ans += tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
# conf = [[int(x) for x in input().split()] for _ in range(n)]
conf = sorted([[int(x) for x in input().split()] for _ in range(n)], reverse=True)

maxres = 0
for cc in permutations(conf, min(m, len(conf))):
  res = 0
  for i, c in enumerate(cc):
    if i + c[0] <= m:
      res = res + c[1]
    else:
      break
  if res > maxres:
    maxres = res
print(maxres)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conf = [[int(x) for x in input().split()] for _ in range(n)]
# conf = sorted([[int(x) for x in input().split()] for _ in range(n)], reverse=True)

maxres = 0
for cc in permutations(conf, min(m, len(conf))):
  res = 0
  for i, c in enumerate(cc):
    if i + c[0] <= m:
      res = res + c[1]
    else:
      break
  if res > maxres:
    maxres = res
print(maxres)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = [int(x) for x in input().split()]
AB_list = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    while(len(AB_list) > 0 and AB_list[0][0] <= i):
        tmp = AB_list.pop(0)
        heapq.heappush(h, -1 * tmp[1])
    # print(AB_list, h)
    if (len(h)):
        ans += -1 * heapq.heappop(h)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = [int(x) for x in input().split()]
AB_list = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    lst = AB_list[:]
    for A, B in lst:
        if (A <= i):
            tmp = AB_list.pop(0)
            heapq.heappush(h, -1 * tmp[1])
        else: break
    # print(AB_list, h)
    if (len(h)):
        ans += -1 * heapq.heappop(h)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = [int(x) for x in input().split()]
AB_list = sorted([input().split() for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    lst = AB_list[:]
    for A, B in lst:
        if (int(A) <= i):
            tmp = AB_list.pop(0)
            heapq.heappush(h, -1 * int(tmp[1]))
        else: break
    # print(AB_list, h)
    if (len(h)):
        ans += -1 * heapq.heappop(h)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from heapq import heappush, heappop

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

# A日後、報酬B
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

sum = 0
used = [False] * n
for i in range(0, m):
    # A <= iで未使用のものをheapqに入れる
    hq = []
    for j in range(n):
        # print(a[j], i+1,a[j]<=i+1, not used[j])

        if a[j] <= i + 1 and not used[j]:
            heappush(hq, (-b[j], j, a[j]))

    val = None
    if len(hq) > 0:
        val = heappop(hq)
    if val is not None:
        sum += -val[0]
        used[val[1]] = True

print(sum)

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int , input().split())
#内包表記で入力
jobs = [list(map(int , input().split())) for _ in range(N)]
sum = 0
#print(jobs)
for limit in range(1 , M + 1):
    index = ''
    max_reward = 0
    for job in jobs:
        if (job[0] <= limit and job[1] > max_reward):
            max_reward = job[1]
            index = jobs.index(job)
    if index != '':
        del jobs[index]
    #print("limit : ",limit)
    #print("max_reward : " , max_reward)
    sum += max_reward
#print(jobs)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = [None] * (m + 1)
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a > m:
      continue
    if d1[a] is None:
      d1[a] = [b]
    else:
      d1[a].append(b)
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if d1[i] is None:
      if _len(d2) == 0:
        continue
    else:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 1
        else:
          d2[j] += 1
        if j > maxb:
          maxb = j
    result += maxb
    d2[maxb] -= 1
    if d2[maxb] == 0:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
      else:
        maxb = _max(d2.keys())
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = [None] * (10 ** 5 + 1)
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if d1[a] is None:
      d1[a] = [b]
    else:
      d1[a].append(b)
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if d1[i] is None:
      if _len(d2) == 0:
        continue
    else:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 1
        else:
          d2[j] += 1
        if j > maxb:
          maxb = j
    result += maxb
    d2[maxb] -= 1
    if d2[maxb] == 0:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
      else:
        maxb = _max(d2.keys())
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

def main():
    n, m = map(int,input().split())
    
    jobs = []
    for i in range(n):
        day, value = map(int,input().split())
        jobs.append((-1*value, day))
    
    cur, res = 0, 0
    done = []
    for i in range(m, 0, -1):
        cur += 1
        h = []

        for j in jobs:
            if cur >= j[1] and not j in done:
                heappush(h, j)
        try:
            r = heappop(h)

            res += -1*r[0]
            done.append(r)
        except IndexError as e:
            pass
    print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = {}
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a in d1:
      d1[a].append(b)
    else:
      d1[a] = [b]
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 1
        else:
          d2[j] += 1
        if j > maxb:
          maxb = j
    else:
      if _len(d2) == 0:
        continue
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
      else:
        maxb = _max(d2.keys())
    else:
      d2[maxb] -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = {}
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a in d1:
      d1[a].append(b)
    else:
      d1[a] = [b]
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 1
        else:
          d2[j] += 1
        if j > maxb:
          maxb = j
    else:
      if _len(d2) == 0:
        continue
    result += maxb
    d2[maxb] -= 1
    if d2[maxb] == 0:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
      else:
        maxb = _max(d2.keys())
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conf = [[int(x) for x in input().split()] for _ in range(n)]
# conf = sorted([[int(x) for x in input().split()] for _ in range(n)], reverse=True)

maxres = 0
cache = []
for cc in permutations(conf, min(m, len(conf))):
  res = 0
  if cc in cache:
    continue
  cache.append(cc)
  for i, c in enumerate(cc):
    if i + c[0] <= m:
      res = res + c[1]
  if res > maxres:
    maxres = res
print(maxres)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conf = [[int(x) for x in input().split()] for _ in range(n)]
# conf = sorted([[int(x) for x in input().split()] for _ in range(n)], reverse=True)

maxres = 0
for cc in permutations(conf, min(m, len(conf))):
  res = 0
  for i, c in enumerate(cc):
    if i + c[0] <= m:
      res = res + c[1]
  if res > maxres:
    maxres = res
print(maxres)