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:
#!/usr/bin/env python3
import sys
import collections
from operator import itemgetter


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):

    jobs_time = collections.defaultdict(list)
    for a,b in zip(A,B):
        jobs_time[b].append(a)

    jobs_time = sorted(jobs_time.items(),reverse=True)
    job_list = [0] * M

    for k,v in jobs_time: 
        v.sort()
        st = -1
        for vv in v:
            if vv <= M:
                for i in range(max(st,vv-1),len(job_list)):
                    if job_list[i] < k:
                        job_list[i] = k
                        st = min(i+1,len(job_list))
                        break
            else:
                break

        if all(j>0 for j in job_list):
            break

    print(sum(job_list))

    return

def solve2(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((b,a))

    jobs_time = sorted(jobs_time,key=itemgetter(0,1),reverse=True)
    #jobs_time = sorted(jobs_time,key=lambda x: -x[0]*10**6+x[1])
    job_list = [0] * M
    job_cnt = 0
    res = 0
    end = len(job_list)
    for b,a in jobs_time: 
        if a <= M:
            for i in range(a-1,end):
                if job_list[i] < b:
                    if job_list[i] == 0:
                        job_cnt += 1
                    else:
                        res -= job_list[i]
                    job_list[i] = b
                    res += b
                    break
            if job_cnt >= len(job_list):
                break

            for i in range(end-1,-1,-1):
                if job_list[i] == 0:
                    end = i + 1
                    break

    print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve2(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    q = deque()
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        q.append((a, b))

    ans = 0
    cnt = 1
    while cnt <= M:
        q_ = deque()
        max_a, max_b = 0, 0
        while q:
            a, b = q.pop()
            if a > cnt:
                q_.append((a, b))
                continue
            elif b > max_b:
                q_.append((max_a, max_b))
                max_a, max_b = a, b
            else:
                q_.append((a, b))

        ans += max_b
        cnt += 1
        q = q_


    return ans


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

Submission status: Time Limit Exceeded

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


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

ab_list = sorted(ab_list, reverse=True)

monies = [0 for i in range(m + 1)]
d2c = collections.Counter()

for money, day in ab_list:
  try:
    idx = monies.index(0, day + d2c[day])
  except:
    continue
  monies[idx] = money
  d2c[day] += 1
# print(monies)
print(sum(monies))

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque
 
N, M = map(int,input().split())
 
work = [list(map(int,input().split())) for _ in range(N)]
 
wq = deque(sorted(work))
 
paytree = []
 
ans = 0
 
for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        bisect.insort_left(paytree,wq.popleft()[1])
    if len(paytree) > 0:
        ans += paytree.pop(len(paytree) - 1)
 
print(ans)

Submission status: Time Limit Exceeded

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

allhiyatoi = []
for i in range(N):
    temp = list(map(int,input().split()))
    allhiyatoi.append(temp)

allhiyatoi.sort()

reward = 0
fin = []
for i in range(M+1):
    today = 0
    todaypos = -1
    for j,hiya in enumerate(allhiyatoi):
        if hiya[0]>i:
            break
        if j in fin:
            continue

        if today<hiya[1]:
            today = hiya[1]
            todaypos = j

    reward += today
    if todaypos!=-1:
        fin.append(todaypos)


print(reward)

Submission status: Time Limit Exceeded

Solution code:


N,M = list(map(lambda x: int(x),input().split()))
dic = {}
#maxs = [-10**6]*(M+1)
counts = [0] * (M+1)
for i in range(N):
    x,y = list(map(lambda x: int(x),input().split()))
    if x > M:
      continue
    counts[x] +=1
    if x not in dic.keys():
        dic[x] = [y]
        #maxs[x]=y
    else:
        dic[x].append(y)
        #if y > maxs[x]:
        #    maxs[x]=y
    
for i in range(1,M+1):
    if counts[i]>0:
        dic[i].sort()

#print(dic)
answer=0

for i in range(1,M+1):
    #print(i)
    max_v = -10**6
    idx=-1
    for j in range(1,i+1):
        #print("j:{}".format(j))
        if counts[j]==0:
            continue
        if max_v < dic[j][-1]:
            max_v = dic[j][-1]
            idx = j
    if idx > 0:
        answer += max_v
        dic[idx].remove(max_v)
        counts[idx] -= 1
        
    #print(maxs)
    #print(dic)
 
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split()]
arbs = [tuple(int(v) for v in input().split()) for _ in range(n)]
cands = [[] for _ in range(m)]
for arb in arbs:
    t = m - arb[0]
    if t >= 0:
        cands[t].append(arb[1])
cands = [sorted(c, reverse=True) for c in cands]
rest = []
total_reward = 0
for cand in reversed(cands):
    new_cand = []
    i, j = 0, 0
    while i < len(cand) and j < len(rest):
        if cand[i] > rest[j]:
            new_cand.append(cand[i])
            i += 1
        else:
            new_cand.append(rest[j])
            j += 1
    if i < len(cand):
        new_cand += cand[i:]
    else:
        new_cand += rest[j:]
    cand = new_cand
    if len(cand) == 0:
        continue
    rest = cand[1:]
    total_reward += cand[0]

print(total_reward)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
X = []
for _ in range(n):
    a, b = map(int, input().split())
    if m>=a:
        X += [(-b, a)]

X = sorted(X)
ans = [0]*(m+1)
ansx = 0

for ax, bx in X:
    if ans[bx]==0:
        ans[bx] = 1
        ansx -= ax
    elif ans[bx]==1:
        if 0 in ans[bx+1:]:
            ind = ans[bx+1:].index(0)
            ans[bx+1+ind] = 1
            ansx -= ax

print(ansx)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

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

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)

    for l in DV:
        l.sort(reverse=True)
    ans = 0

    pre = []
    for i in range(1,M+1):
        tmpL = [0] * i
        for j in range(1,i+1):

            if len(DV[j]) > i-j:
                tmpL[j-1] = DV[j][i-j]

        tmpL += pre
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
        pre = tmpL 
    print(ans)
        
        



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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = [0 for _ in range(10**4+1)]
#maxi = 0
cnt = 0
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      add = ab[here][1]
      pool[add] += 1
      '''
      if add > maxi:
        maxi = add
      '''
      here += 1
      cnt += 1
    else:
      break
  if cnt != 0:
    cnt -= 1
    for j in range(10**4):
      if pool[10**4-j] != 0:
        ans += 10**4-j
        #print(10**4-j,i)
        pool[10**4-j] -= 1
        break
    '''
    ans += maxi
    pool[maxi] -= 1
    if pool[maxi] == 0:
      if cnt == 0:
        maxi = 0
      else:
        while True:
          maxi -= 1
          if pool[maxi] != 0:
            break
    '''
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: (x[0], x[1]))
A, B = [0], [0]
for i in range(N):
    A.append(X[i][0])
    B.append(X[i][1])

ans = 0
index_upper = 1
for k in range(1, M + 1):
    Ak = [a for a in A if a <= k]
    index_upper = len(Ak)
    res = max(B[:index_upper])
    if res != 0:
        A.remove(A[B.index(res)])
        B.remove(res)
    ans += res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(N)]
works.sort(key=lambda x:(-x[1], -x[0]))
days = [0] * (M+1)
ans = 0
max_day = M+1
for work in works:
  if work[0] > M or work[0] >= max_day:
    continue
  full = True
  for day in range(work[0], max_day):
    if days[day] == 0:
      days[day] = 1
      ans += work[1]
      full = False
      break
  if full:
    max_day = work[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
nums = list(map(int, input().split()))
N, M = nums[0], nums[1]
E = []

for i in range(N):
    nums = list(map(int, input().split()))
    E.append((nums[0], nums[1]))
E = sorted(E, key=lambda x:x[0], reverse=True)
E = sorted(E, key=lambda x:x[1])
dp = [0 for _ in range(M+1)]
for i in range(M):
    E_sub = []
    f = False
    while len(E) > 0:
        e = E.pop()
        if e[0] <= i+1:
            dp[i+1] = dp[i] + e[1]
            f = True
            break
        else:
            E_sub.append(e)
    E += E_sub[::-1]
    if not f:
        dp[i+1] = dp[i]
if len(E) == 0:
    print(max(dp))
else:
    print(dp[M])

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split())

AB = [[int(i) for i in input().split()] for i in range(N)]

ans = 0
for i in range(M):
    h = 0
    hp = 0
    f = False
    for a_b in AB:
        b = 0
        if i + a_b[0] <= M:
            if h <= a_b[1] and b < a_b[0]:
                h = a_b[1]
                hp = a_b
                b = a_b[0]
                f = True
    if f:
        AB.remove(hp)
        ans += h

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint
from collections import deque

sys.setrecursionlimit(4100000)

B = 10


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    jobs = list(map(string_to_int, inputs))
    jobs.sort(key=lambda x: (x[0]))
    jobs = deque(jobs)

    can_select_jobs = []
    money = 0

    for day in range(1, M + 1):
        while len(jobs) != 0:
            if jobs[0][0] > day:
                break
            else:
                can_select_jobs.append(jobs.popleft())

        if len(can_select_jobs) != 0:
            can_select_jobs.sort(key=lambda x: x[1])
            best_job = can_select_jobs.pop()
            money += best_job[1]

        new_can_select_jobs = []

        while len(new_can_select_jobs) <= M and len(can_select_jobs) != 0:
            new_can_select_jobs.append(can_select_jobs.pop())
        can_select_jobs = new_can_select_jobs
    return money


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(N))
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(n):
  a,b=map(int,input().split())
  l+=[[a,b]]
l.sort(reverse=1,key=lambda x:x[1])
#l.sort(reverse=0,key=lambda x:x[0])

a=[0 for i in range(m)]
ans=0
for i in range(n):
  for j in range(l[i][0]-1,m):
    if a[j]<l[i][1]:
      a[j]=l[i][1]
      break

#print(a)
print(sum(a))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        if len(current) != 0:
            if len(q) != 0:
                if current[-1] > q[-1]:
                    res += current.pop()
                else:
                    res += q.pop()
            else:
                res += current.pop()
            q += current
            q.sort()
            # q = sorted(q + current)
            q = q[-(M - i):]
        else:
            if len(q) != 0:
                res += q.pop()
            else:
                pass
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# D
n,m = map(int,input().split())
a,b = [0]*n ,[0]*n

for i in range(n):
    aa,bb = map(int,input().split())
    if aa <= m: a[i]=aa; b[i]=bb

val = 0
rest = m
tmp  = -1
tmpa = -1
while rest > 0:
    maxi = 0
    for i in range(n):
        if b[i] > maxi:  maxi = b[i]; tmp = i; tmpa = a[i]
        elif b[i] == maxi:
            if a[i] > tmpa: maxi = b[i]; tmp = i; tmpa = a[i]
    if a[tmp] <= rest:
        val += maxi ; rest -= 1
    b[tmp] = 0

print(val)

Submission status: Time Limit Exceeded

Solution code:
N,M = (int(i) for i in input().split())
A = [0]*(N+1)
B = [0]*(N+1)

ans = 0
for i in range(N):
    A[i],B[i] = (int(j) for j in input().split())

for j in range(1,M+1):
    max = -1
    temp = -1
    for i in range(N):
        if A[i]<=j and B[i] > max :
            max = B[i]
            temp = i
    if temp != -1:
        ans+=B[temp]
        A[temp] = M+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
A =[ list(map(int,input().split())) for i in range(n)]
A.sort(key=lambda x: x[1])
dp=[0]*(m+1)
ans = 0
for i in range(n):
    k=m-A[n-1-i][0]
    while True:
        if k < 0:
            break
        elif dp[k] ==0:
            dp[k] =1
            ans += A[n-1-i][1]
            break
        else:
            k -= 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(lambda x: int(x), input().split()))

jobs = []
for i in range(n):
    jobs.append(list(map(lambda x: int(x), input().split())))

# 貪欲解法
# 最終日から決める
jobs.sort()
selected = []
ans = 0
for i in range(m+1):
    # 振込までi+1日以内の仕事のうち最大の仕事を選び働く
    max_reward = 0
    max_job = -1
    for j in range(n):
        if jobs[j][0] < i+1:
            if max_reward <= jobs[j][1]:
                max_reward = max([max_reward, jobs[j][1]])
                max_job = j
        else:
            break
    ans += max_reward
    if max_job != -1:
        jobs[max_job][1] = 0

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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
li = []
for i in range(M):
    li.extend(jobs[i])
    if len(li) >0:
        reword = np.max(li)
        rewords += reword
        li.remove(reword)
    
print(rewords)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
N, M =LI()
AB = []
for i in range(N):
    AB.append(LI())
AB.sort(key=lambda x: x[0])
perr(AB)
#  AB_dict = {}
#  for ab in AB:
#      if ab[0] not in AB_dict.keys():
#          AB_dict[ab[0]] = [ab[1]]
#      else:
#          AB_dict[ab[0]].append(ab[1])
#  for k in AB_dict.keys():
#      AB_dict[k].sort()
#  perr(AB_dict)

ans = 0
tmp = []
crr = 0
for i in range(1, M+1):
    if crr < N:
        if AB[crr][0] == i:
            while True:
                if crr == N:
                    break
                if AB[crr][0] != i:
                    break
                tmp.append(AB[crr][1])
                crr += 1

    perr('tmp')
    perr(tmp)
    if len(tmp) == 0:
        continue

    max_v = max(tmp)
    ans += max_v
    tmp.remove(max_v)
    #  tmp.sort()
    #  ans+=tmp.pop()

"""
貪欲か？
日が長くて報酬の高いものから選んでいく
そうすると
10 1
9 10
みたいなときに10 1のほうから選んでしまうからだめ
残り日数を意識
残ってる中で最も報酬の高いものから？
2 10
1 11
のパターンで、先に1をやってしまうためだめ
2 10
1 11
1 15
のパターンで、1 1をやるのが正解
"""

#  ans = 0
#  tmp = []
#  for i in range(1, M+1):
#      # 残りi日
#      if i in AB_dict.keys():
#          tmp += AB_dict[i]
#      perr('tmp')
#      perr(tmp)
#      if len(tmp) == 0:
#          continue
#      tmp.sort()
#      #  max_v = max(tmp)
#      #  ans += max_v
#      ans += tmp.pop()
print(ans)

Submission status: Time Limit Exceeded

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

from operator import itemgetter
AB.sort(key = itemgetter(0))
AB.sort(key = itemgetter(1),reverse = True)

days = [0]*(M+1)
for a,b in AB:
    point = M - a
    if point >= 0:
        while point >= 0:
            if days[point] == 0:
                days[point] = b
                break
            else:
                point -= 1
print(sum(days))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

ans = np.array([0] * m)

ab = sorted(ab, key=lambda x:(-x[1], -x[0]))

for a, b in ab:
    if m - a < 0:
        continue
    if np.min(ans[:m - a + 1]) != 0:
        continue
        
    ind = np.max(np.where(ans[:m - a + 1] == 0)[0])
    ans[ind] = b
    
print(sum(ans))

Submission status: Time Limit Exceeded

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

A = [0]*N
B = [0]*N

for n in range(N):
  B[n],A[n] = map(int,input().split())

F = [True]*N
sr = 0
for m in range(M):
  cr = 0
  ci = -1
  for n in range(N):
    if B[n] <= m+1 and F[n] and cr<A[n]:
      ci = n
      cr = A[n]
  if ci!=-1:
    sr += cr
    F[ci] = False
print(sr)

Submission status: Time Limit Exceeded

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

count_lis = [[0 for _ in range(M)] for _ in range(N)]
x = M - ab[0][0]
if x >= 0:
  for i in range(x+1):
    count_lis[0][i] = ab[0][1]

for i in range(1, N):
  count_lis[i][:] = count_lis[i-1][:]
  if ab[i][0] <= M:
    count_lis[i][0] = max(count_lis[i-1][0], ab[i][1])
  for j in range(1, M-ab[i][0]+1):
    count_lis[i][j] = max(count_lis[i-1][j-1] + ab[i][1], count_lis[i-1][j])
print(max(count_lis[N-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = []
for _ in range(n):
   a,b = map(int, input().split())
   A.append((b, a))
A.sort()
w = [0]*m
for a in reversed(A):
    for i in range(a[1]-1, m):
        if w[i]==0:
            w[i]=a[0]
            break
        i += 1
        
print(sum(w))

Submission status: Time Limit Exceeded

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

reward = 0 # 報酬
for i in range(1,M+1):
    local_max_reward = -1
    local_max_task = -1
    for j in range(len(array)):
        if array[j][0] <= i and array[j][1] > local_max_reward:
            local_max_reward = array[j][1]
            local_max_task = j
    #print(i,local_max_task,array[local_max_task][1])
    if local_max_task != -1:
        reward += array[local_max_task][1]
        array.pop(local_max_task)
print(reward)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(v) for v in input().split()]
arbs = [tuple(int(v) for v in input().split()) for _ in range(n)]
cands = [[] for _ in range(m)]
for arb in arbs:
    t = m - arb[0]
    if t >= 0:
        cands[t].append(arb[1])
cands = [sorted(c, reverse=True) for c in cands]
rest = []
total_reward = 0
for d, cand in enumerate(reversed(cands)):
    new_cand = []
    i, j = 0, 0
    while i < len(cand) and j < len(rest):
        if cand[i] > rest[j]:
            new_cand.append(cand[i])
            i += 1
        else:
            new_cand.append(rest[j])
            j += 1
    if i < len(cand):
        new_cand += cand[i:]
    else:
        new_cand += rest[j:]
    cand = new_cand
    if len(cand) == 0:
        continue
    rest = cand[1:]
    total_reward += cand[0]

print(total_reward)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab = {i:[] for i in range(m+1)}
for i in range(n):
    a,b = map(int,input().split())
    if a in ab:
        ab[a].append(b)
    else:
        ab[a] = [b]
#print(ab)
ans = 0
for i in range(m)[::-1]:
    rem = m - i
    if ab[rem]:
        job = ab[rem]
        ans += max(job)
        del ab[rem][job.index(max(job))]
        if rem < m:
            ab[rem+1] += ab[rem]
            ab[rem] = []
    #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N,M=map(int,input().split())
A,B=[],[]
for i in range(N):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)

used=set()

def search_best(hi):
    best=0
    best_i=-1
    for i in range(N):
        if i not in used:
            if A[i] <= hi:
                if best < B[i]:
                    best=B[i]
                    best_i=i
    
    if best_i >= 0:
        return best, best_i
    else:
        return 0, -1

dp=[0]*(M+1)
res=list()

for i in range(1,M+1):
    best,best_i = search_best(i)
    if best < 0:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1] + best
        used.add(best_i)


print(dp[M])

Submission status: Time Limit Exceeded

Solution code:
from heapq import *

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        heappush(c[m - a], -b)
r=0
for i in range(m - 1, -1, -1):
    if c[i]:
        r -= heappop(c[i])
        if i:
            for x in c[i]:
                heappush(c[i - 1], x)  
print(r)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
x=[]
an=0
for i in range(M+1):
    x.insert(i,[])
for i in range(N):
    a,b=map(int,input().split())
    if a<=M:
        x[a].append(b)
y=[]
for n in range(M+1):
    y+=x[n]
    try:
        an+=max(y)
        y.remove(max(y))
    except:
        continue
print(an)

Submission status: Time Limit Exceeded

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

def main():
    N,M = [int(x) for x in input().split()]
    work = {}
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        if(a in work):
            work[a].append(b)
        else:
            work[a] = [b]

    cand = []
    cnt = 0
    for i in range(1,M+1):
        if(i in work):
            cand += work[i]
        if(len(cand)==0):
            continue
        x = max(cand)
        cand.remove(x)
        cnt += x

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(-x[1],x[0]))

from bisect import bisect_left
s = [i for i in range(1,M+1)]
ans = 0
for i in range(N):
  if a[i][0]<=M:
    place = bisect_left(s,a[i][0])
    if place <= len(s)-1:
      s.pop(place)
      ans += a[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
work_list = [list(map(int, input().split())) for i in range(n)]
work_list.sort()
ans = 0
for i in range(1, m+1):
  max_f = 0
  p = 0
  p_max = -1
  while p<len(work_list) and work_list[p][0]<=i:
    if max_f<work_list[p][1]:
      p_max = p
      max_f = work_list[p][1]
    p += 1
  if p_max>=0:
    _ = work_list.pop(p_max)
  ans += max_f
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

task.sort()

wa = []
ans = 0
j = 0
for i in range(M):
    while j < N and task[j][0] == i + 1:
        bisect.insort_right(wa, task[j][1])
        j += 1
    if wa:
        ls = wa[-1]
        ans += ls
        del (wa[-1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
num, day = [int(x) for x in input().split()]
 
#worklist = [[] for i in range(day+4)]
 
wd = {}
 
for i in range(num):
  d, m = [int(x) for x in input().split()]
#  if d <= day:
#    worklist[d-1].append(m)
  if d-1 in wd.keys():
    wd[d-1].append(m)
  else:
    wd[d-1] = [m]

ans = 0
 
canworklist = []
 
workday = wd.keys()
 
for i in range(day):
  if i in workday:
    canworklist += wd[i]
    canworklist.sort(reverse=True)
  if canworklist:
    ans += canworklist.pop(0)
print(ans)
 
#print(wd)

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(i) for i in input().split()]
AB = []
for n in range(N):
    temp = [int(i) for i in input().split()]
    if temp[0] <= M:
        AB.append(temp)
from collections import deque
works = sorted(AB,key=lambda x:(-x[1],x[0],))
works = deque(works)
work_schedule = [0]*M
for w in range(len(works)):
    work = works.popleft()
    if work[0] > M:
        pass
    else:
        cnt = 0
        while True:
            if (work[0]-1+cnt) >= M:
                break
            elif work_schedule[work[0]-1+cnt]  == 0:
                work_schedule[work[0]-1+cnt] = work[1]
                break
            else:
                cnt+=1
print(sum(work_schedule))

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None
N, M =LI()
AB = []
for i in range(N):
    AB.append(LI())
AB.sort(key=lambda x: x[0])
perr(AB)
#  AB_dict = {}
#  for ab in AB:
#      if ab[0] not in AB_dict.keys():
#          AB_dict[ab[0]] = [ab[1]]
#      else:
#          AB_dict[ab[0]].append(ab[1])
#  for k in AB_dict.keys():
#      AB_dict[k].sort()
#  perr(AB_dict)

ans = 0
tmp = []
crr = 0
for i in range(1, M+1):
    if crr < N:
        if AB[crr][0] == i:
            while True:
                if crr == N:
                    break
                if AB[crr][0] != i:
                    break
                tmp.append(AB[crr][1])
                crr += 1

    perr('tmp')
    perr(tmp)
    if len(tmp) == 0:
        continue
    tmp.sort()
    ans+=tmp.pop()

"""
貪欲か？
日が長くて報酬の高いものから選んでいく
そうすると
10 1
9 10
みたいなときに10 1のほうから選んでしまうからだめ
残り日数を意識
残ってる中で最も報酬の高いものから？
2 10
1 11
のパターンで、先に1をやってしまうためだめ
2 10
1 11
1 15
のパターンで、1 1をやるのが正解
"""

#  ans = 0
#  tmp = []
#  for i in range(1, M+1):
#      # 残りi日
#      if i in AB_dict.keys():
#          tmp += AB_dict[i]
#      perr('tmp')
#      perr(tmp)
#      if len(tmp) == 0:
#          continue
#      tmp.sort()
#      #  max_v = max(tmp)
#      #  ans += max_v
#      ans += tmp.pop()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M = map(int, input().split())

d = defaultdict(list)

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

works = []
for k in range(M, 0, -1):
    d[k] = sorted(d[k], reverse=True)
    if M-k+1 >= 1:
        works.extend(d[k][:M-k+1])
        works = sorted(works, reverse=True)
        works = works[:M-k+1]
        # print(works)

works = sorted(works, reverse=True)

print(sum(works[:M]))