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:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            candidates.append(b)
        else:
            s = j
            break
    candidates.sort()
    if len(candidates) > 0:
        # print(candidates)
        ans += candidates[-1]
        candidates = candidates[:-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        l.append((a,b))
    l.sort(key=lambda x: x[0])
    t = {}
    i = 0
    r = 0
    for d in range(1, M+1):
        while i < len(l):
            a, b = l[i]
            if a <= d:
                if b in t:
                    t[b] += 1
                else:
                    t[b] = 1
            else:
                break
            i += 1
        if not t:
            continue
        m = max(t)
        if t[m] == 1:
            t.pop(m)
        else:
            t[m] -= 1
        r += m
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort(key=lambda x: -x[1])
    M += 1
    w = [False] * M
    r = 0
    c = 0
    for a, b in AB:
        for i in reversed(range(M - a)):
            if w[i]:
                continue
            w[i] = True
            r += b
            c += 1
            break
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop

nm = list(map(int, input().split()))
n, m = nm[0], nm[1]
d = {}
ab_list = list()
for i in range(n):
    ab = list(map(int, input().split()))
    rem_day, reward = ab[0], ab[1]
    if rem_day in d:
        d[rem_day].append(-reward)
    else:
        d[rem_day] = [-reward]


result = 0

candidates = list()

for rem in range(1, m + 1):
    added_candidates = d.get(rem)
    if added_candidates is not None and len(added_candidates) > 0:
        candidates.extend(added_candidates)

    if len(candidates) > 0:
        heapify(candidates)
        top = heappop(candidates)
        result += -top

print(result)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop

nm = list(map(int, input().split()))
n, m = nm[0], nm[1]
ab_list = list()
for i in range(n):
    ab = list(map(int, input().split()))
    a, b = ab[0], ab[1]
    ab_list.append((-b, a))


result = 0

candidates = list()

for rem in range(1, m + 1):
    added_candidate = list(filter(lambda x: x[1] == rem, ab_list))
    if len(added_candidate) > 0:
        candidates.extend(added_candidate)

    if len(candidates) > 0:
        heapify(candidates)
        top = heappop(candidates)
        result += -top[0]

print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
tasks = []
for _ in range(n):
    days, rev = [int(i) for i in input().split()]
    tasks.append((rev, days))

tasks.sort(reverse=True)

worked = [False for _ in range(m)]
max_revenue = 0
for rev, days in tasks:
    try:
        to_work = worked[days - 1 :].index(False) + days - 1
        max_revenue += rev
        worked[to_work] = True
    except:
        continue

print(max_revenue)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
N,M = map(int,input().split())
AB = defaultdict(list)
for i in range(N):
    a,b = list(map(int,input().split()))
    if a not in AB:
        AB[a] = [-b]
    else:
        AB[a] += [-b]
work = 0
AB2 = []
for i in range(1,M+1):
    AB2 += AB[i]
    heapq.heapify(AB2)
    if not AB2:
        continue
    b = heapq.heappop(AB2)
    work += -b
print(work)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
work = 0
for i in range(1,M+1):
    AB2 = list(filter(lambda x:x[1]<=i,AB))
    heapq.heapify(AB2)
    if not AB2:
        continue
    b,a = heapq.heappop(AB2)
    work += -b
    AB.remove([b,a])
print(work)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
work = [0 for i in range(M)]
for i in range(1,M+1):
    AB2 = list(filter(lambda x:x[1]<=i,AB))
    heapq.heapify(AB2)
    if not AB2:
        continue
    b,a = heapq.heappop(AB2)
    work[i-1] = -b
    AB.remove([b,a])
print(sum(work))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
heapq.heapify(AB)
work = [0 for i in range(M)]
ABlist = []
for i in range(M):
    ABlist.append(list(filter(lambda x:x[1]<=i+1,AB)))
ABremoved = []
for i in range(1,M+1):
    AB2 = ABlist[i-1]
    heapq.heapify(AB2)
    flag = False
    while AB2:
        b,a = heapq.heappop(AB2)
        if [b,a] not in ABremoved:
            flag = True
            break
    if flag:
        work[i-1] = -b
        ABremoved.append([b,a])
print(sum(work))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
heapq.heapify(AB)
work = [0 for i in range(M)]
for i in range(1,M+1):
    AB2 = list(filter(lambda x:x[1]<=i,AB))
    if not AB2:
        continue
    heapq.heapify(AB2)
    b,a = heapq.heappop(AB2)
    work[i-1] = -b
    AB.remove([b,a])
print(sum(work))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy
N,M = map(int,input().split())
AB = []
for i in range(N):
    a,b = list(map(int,input().split()))
    AB.append([-b,a])
heapq.heapify(AB)

work = [0 for i in range(M)]
for i in range(1,M+1):
    AB2 = copy.deepcopy(AB)
    heapq.heapify(AB2)
    while AB2:
        b,a = heapq.heappop(AB2)
        b = -b
        if a <= i:
            work[i-1] = b
            AB.remove([-b,a])
            break
print(sum(work))

Submission status: Time Limit Exceeded

Solution code:
class Job:
  def __init__(self,day, pay):
    self.day = day
    self.pay = pay

def searchjob(n, jobs):
  ans = None
  m = -1
  for j in jobs:
    if j.pay > m and j.day <= n:
      ans = j
      m = j.pay
  return ans

n, m = tuple(map(int,input().rstrip().split()))
jobs = []
for _ in range(n):
  d, p = tuple(map(int,input().rstrip().split()))
  jobs.append(Job(d, p))

psum = 0
for i in range(1, 1+m):
  j = searchjob(i, jobs)
  if j != None:
    psum += j.pay
    jobs.remove(j)
print(psum)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

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

AB = sorted(AB , key = lambda x : x[0])
heap = []
j = 0

for i in range(M+1):
    while j<N and AB[j][0] < i+1:
        heapq.heappush(heap,-AB[j][1])
        j += 1

    if len(heap):
        heapq.heapify(heap)
        sum += -heapq.heappop(heap)
                           
print(sum)

Submission status: Time Limit Exceeded

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


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

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

REWARDS = [0] * m
count = 0
for job in JOBS:
    i = m - job[1]
    while i >= 0:
        if REWARDS[i] == 0:
            REWARDS[i] = job[0]
            count += 1
            break
        else:
            i -= 1
    if count == m:
        break

answer = sum(REWARDS)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
a = sorted(a, key=itemgetter(1), reverse=1)
money = 0
length = len(a)
for i in range(1,m+1):
    for k in range(length):
        if a[k][0] <= i:
            item = a.pop(k)
            money += item[1]
            length -= 1
            break

print(money)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ans = 0
for i in range(1, m + 1):
    reward = []
    for j in range(n):
        if ab[j][0] <= i :
            reward.append([ab[j][1], j])
    if reward :
        mx = max(reward)
        ans += mx[0]
        ab[mx[1]][1] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
AB = []
for _ in range(N):
  a,b = map(int,input().split())
  AB.append([b,a])
AB.sort(reverse=True)
ans = 0
used = [False for _ in range(M+1)]
for b,a in AB:
  for i in range(M-a,-1,-1):
    if used[i] == False:
      ans += b
      used[i] = True
      break 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def problem(firstline, thereafter):
    N, M = firstline.strip().split()
    N = int(N)
    M = int(M)
    points = []
    for i in thereafter:
        a, b = i.strip().split()
        points.append((int(b),int(a)))
    points.sort(reverse=True)
    days = {}
    for i in range(M, -1 , -1):
        days[i] = 0
    for i in points:
        if i[1] <= M:
            for j in range(M - i[1], -1, -1):
                if not days[j]:
                    days[j] = i[0]
                    break
    out = 0
    for i, values in days.items():
        out += values
    return out





def main():
    print(problem(stdin.readline(), stdin.readlines()))

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def problem(firstline, thereafter):
    N, M = firstline.strip().split()
    N = int(N)
    M = int(M)
    points = []
    for i in thereafter:
        a, b = i.strip().split()
        points.append((int(b),int(a)))
    points.sort(reverse=True)
    days = {}
    keys = set()
    for i in points:
        if i[1] <= M:
            for j in range(M - i[1], -1 , -1):
                if j not in keys:
                    keys.add(j)
                    days[j] = i[0]
                    break
    out = 0
    for i, values in days.items():
        out += values
    return out





def main():
    print(problem(stdin.readline(), stdin.readlines()))

main()

Submission status: Time Limit Exceeded

Solution code:
#最終日から見る，残り日数条件を満たす中で最大収入のものを選ぶ

import heapq

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

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

ans=0
q=[]
heapq.heapify(q)
ne=0
#dは残り日数
for d in range(1,M+1):
    for i in range(ne,N):
        if AB[i][0]<=d:
            heapq.heappush(q,AB[i][1]*-1)
            ne=i+1
    if len(q)!=0:
        a=heapq.heappop(q)
        ans-=a
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC-137-D
import heapq
import bisect
N, M = map(int, input().split())
AB = []#Aでソートをかけて利用する。
BA = []#Bでソートをかけてheapqで利用する。
heapq.heapify(BA)

for _ in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))    
AB = sorted(AB)

ans = 0
check_M = 1
while check_M <= M:
    r = bisect.bisect_right(AB, (check_M+1, 0))
    for A, B in AB[:r]:
        heapq.heappush(BA, (-1*B, A))
    try:
        max_B = heapq.heappop(BA)
    except:
        check_M += 1
        AB = AB[r:]
        continue
    ans += (-1) * max_B[0]
    check_M += 1
    AB = AB[r:]

print(ans)

Submission status: Time Limit Exceeded

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

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

BA.sort(reverse=True)

ans = 0
used = [False] * (M+1)
for b, a in BA:
  if a >= M+1:
    continue
    
  while used[a]:
    a += 1
    if a == M+1:
      break
  
  if a <= M:
    used[a] = True
    ans += b

print(ans)

Submission status: Time Limit Exceeded

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

    l.sort(key = lambda x: x[1],reverse=True)

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

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

    l.sort(key = lambda x: x[1],reverse=True)

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


main()

Submission status: Time Limit Exceeded

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

l.sort(key = lambda x: x[1],reverse=True)

for i in range(n):
    a,b = l[i]
    for j in range(a,m+1):
        if ans[j] == 0:
            ans[j] = b
            break
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
queue = [0]*m
flag = 0
ans = 0
for i in range(1,m+1):
  for j in range(flag,n):
    if ab[j][0] > i:
      flag = j
      break
    queue.append(ab[j][1])
  k = heapq.nlargest(1,queue)
  ans += k[0]
  queue.remove(k[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

# ------------------------------------------ #
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for i in range(N):
    a, b = map(int, input().split())
    if a > M:
        continue
    jobs[a].append(b)

if __name__ == "__main__":

    ans = 0
    pq = PriorytyQueue([], target='max')
    # d: 残りの日数(d日以上の仕事なら可能)
    for d in range(1, M+1):
        if d in jobs.keys():
            moneys = jobs[d]
            for money in moneys:
                pq.push(money)
        if len(pq.get_arr()) != 0:
            ans += pq.pop()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

from collections import defaultdict

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

if __name__ == "__main__":

    ans = 0
    pq = PriorytyQueue([], target='max')
    for d in range(1, M+1):
        if d in jobs.keys():
            moneys = jobs[d]
            for money in moneys:
                pq.push(money)
        if len(pq.get_arr()) != 0:
            ans += pq.pop()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

class PriorytyQueue(object):

    def __init__(self, arr, target='min'):
        self.arr = arr
        self.target = target
        self._heapify()
    
    def _heapify(self):
        if self.target == 'max':
            self.arr = list(map(lambda x:x*(-1), self.arr))
        heapq.heapify(self.arr)
    
    def push(self, x):
        if self.target == 'max':
            x *= -1
        heapq.heappush(self.arr, x)

    def pop(self):
        res = heapq.heappop(self.arr)
        if self.target == 'max':
            return res*(-1)
        else:
            return res
    
    def get_arr(self):
        if self.target == 'max':
            return list(map(lambda x:x*(-1), self.arr))
        else:
            return self.arr
    
    def is_empty(self):
        return len(self.arr) == 0

# ------------------------------------------ #
from collections import defaultdict

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

if __name__ == "__main__":

    ans = 0
    pq = PriorytyQueue([], target='max')
    # d: 残りの日数(d日以上の仕事なら可能)
    for d in range(1, M+1):
        moneys = jobs[d]
        for money in moneys:
            pq.push(money)
        if len(pq.get_arr()) != 0:
            ans += pq.pop()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

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

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

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

que = []
ans = 0
for i in range(1, M+1):
    tmp = copy.copy(baito)
    for val in baito:
        if val[0] <= i:
            heapq.heappush(que, val[1]*-1)
            tmp.pop(0)
        else:
            break
    baito = tmp
    if len(que) != 0:
        ans += heapq.heappop(que)*-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab_list = {}
for i in range(n):
    a,b = map(int,input().split())
    ab_list.setdefault(a,[]).append(b)
sort_list = sorted(ab_list.keys())
amount = 0
in_list = []
for i in range(m):
    if i+1 in sort_list:
        in_list = in_list + ab_list[i+1]
    if len(in_list)>0:
        max_v = max(in_list)
        amount = amount +  max_v
        in_list[in_list.index(max_v)] = 0

print(amount)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab_list = {}
for i in range(n):
    a,b = map(int,input().split())
    ab_list.setdefault(a,[]).append(b)
sort_list = sorted(ab_list.keys())
amount = 0
in_list = []
for i in range(m):
    if i+1 in sort_list:
        in_list = in_list + ab_list[i+1]
        in_list.sort()
    if len(in_list)>0:
        amount = amount + max(in_list)
        in_list.pop()

print(amount)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]
AB.sort()
queue = []
heapify(queue)
ans = 0

for i in range(1, M+1):
    while len(AB) > 0:
        if AB[0][0] <= i:
            heappush(queue, -AB.pop(0)[1])
        else:
            break

    if queue:
        ans += -heappop(queue)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m = map(int, input().split())
ab_lis = []
for i in range(n):
    ab_lis.append(list(map(int, input().split())))
def rec(ab_lis, path, rew, r_day, ans):
    if r_day == 0:
        ans.append(rew)
        return
    for t_lis in ab_lis:
        if t_lis in path:
            continue
        elif t_lis[0] > r_day:
            ans.append(rew)
            continue
        path_c = copy.copy(path)
        path_c.append(t_lis)
        rec(ab_lis, path_c, rew + t_lis[1], r_day - 1, ans)   
ans = []
rec(ab_lis, [], 0, m, ans)        
print(max(ans))

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort(reverse=True)

answer = 0
for j in range(M-1,-1,-1):
    maxB = 0
    index = -1
    for i in range(len(AB)-1,-1,-1):
        a,b = AB[i]
        if a + j <= M:
            if maxB < b:
                maxB = b
                index = i
            if i == 0:
                AB.pop(index)
                answer += maxB
        else:
            if index < 0:
                break
            else:
                AB.pop(index)
                answer += maxB
                break

print(answer)

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]
AB.sort(key=itemgetter(0,1),reverse=True)

answer = 0
for j in range(M-1,-1,-1):
    maxB = 0
    index = -1
    for i in range(len(AB)-1,-1,-1):
        a,b = AB[i]
        if a + j <= M:
            if maxB < b:
                maxB = b
                index = i
            if i == 0:
                AB.pop(index)
                answer += maxB
        else:
            if index < 0:
                break
            else:
                AB.pop(index)
                answer += maxB
                break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(n)], reverse=True)

dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(n):
    for j in range(m+1):
        dp[i+1][j] = dp[i][j]

        if ab[i][0] <= m-j:
            dp[i+1][j] = max(dp[i][j-1]+ab[i][1], dp[i][j])

print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
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] = 0
      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 = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,M = map(int,input().split())
lis = [[int(i) for i in input().split()]for _ in range(N)]
day = [[] for _ in range(M)]
for li in lis:
    if li[0] <= M:
        day[li[0]-1].append(li[1])

ans = 0
joblis = []
for li in day:
    for i in li:
        joblis.insert(bisect.bisect_left(joblis,i),i)
    if len(joblis)!=0:
        ans += joblis.pop(-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
l=list()
v=0
heapq.heapify(l)
for i in range(1,m+1):
  for j in range(n):
    if c[j][0]==i:
      heapq.heappush(l,(-1)*c[j][1])
  if l:
    v+=heapq.heappop(l)*(-1)
print(v)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
l=list()
v=0
heapq.heapify(l)
for i in range(1,m+1):
  for j in range(n):
    if c[j][0]==i:
      heapq.heappush(l,(-1)*c[j][1])
  if l:
    v+=heapq.heappop(l)*(-1)
print(v)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

L=[]
for i in range(M+1):
    L.append([])

for i in range(N):
    if AB[i][0]<=M:
        L[AB[i][0]].append(AB[i][1])

LL=[]
money=0

for i in range(1,M+1):
    LL+=[-k for k in L[i]]
    heapq.heapify(LL)
    if len(LL)==0:
        continue
    money+=heapq.heappop(LL)

print(-money)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import heapq
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    n, m = map(int, input().split())
    worked = [False]*m

    q = []
    heapq.heapify(q)

    for _ in range(n):
        a, b = map(int, input().split())
        heapq.heappush(q, (-b, a))

    ans = 0
    while (m >= 0 and len(q) > 0):
        value, nissu = heapq.heappop(q)
        #value = work[0]
        #nissu = work[1]
        #print(value, nissu)
        while(True):
            if m - nissu >= 0:
                if worked[m - nissu]:
                    nissu += 1
                    continue
                # print('work')
                ans += -value
                worked[m-nissu] = True
                #print(ans, m)
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

def aa(sh, idx, M, x, ans):
  while idx < M :
    if sh[idx] == 0:
      sh[idx] = idx+1
      sh[x["d"]] = idx+1
      ans += x["m"]
      break
    else:
      idx = sh[idx]
  return sh, idx, M, x, ans
  
sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  sh, idx, M, x, ans = aa(sh, idx, M, x, ans)
print(ans)

Submission status: Time Limit Exceeded

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  while idx < M :
    if sh[idx] == 0:
      if idx + 1 < M and sh[idx+1]!= 0:
        sh[idx] = sh[idx+1]
        sh[x["d"]] = sh[idx+1]
      else:
        sh[idx] = idx+1
        sh[x["d"]] = idx+1
      ans += x["m"]
      break
    else:
      idx = sh[idx]
print(ans)

Submission status: Time Limit Exceeded

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  while idx < M :
    if sh[idx] == 0:
      sh[idx] = idx+1
      sh[x["d"]] = idx+1
      ans += x["m"]
      break
    else:
      idx = sh[idx]
print(ans)

Submission status: Time Limit Exceeded

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

md = []
for i in range(0,N):
  d, m = map(int, input().split())
  md.append({"m":m, "d":d-1})

md = sorted(md, key=lambda x:x["m"], reverse=True)

sh = [0]*M
ans = 0
for x in md:
  idx = x["d"]
  while idx < M :
    if sh[idx] == 0:
      sh[idx] = idx+1
      ans += x["m"]
      break
    else:
      idx = sh[idx]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    job_list = []
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list.append(tuple([a, b]))

    job_list.sort(reverse=True, key=lambda x: x[1])
    rewards = [0 for _ in range(m+1)]
    count = 0
    for i in range(len(job_list)):
        if 0 in rewards[job_list[i][0]:]:
            rewards[rewards.index(0, job_list[i][0])] = job_list[i][1]
            count += 1
            if count == m:
                break
    
    print(sum(rewards))
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-16 14:51:41(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    job_list = []
    for _ in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        if a <= m:
            job_list.append(tuple([a, b]))

    job_list.sort(reverse=True, key=lambda x: x[1])
    rewards = [0 for _ in range(m+1)]
    count = 0
    for i in range(len(job_list)):
        for j in range(job_list[i][0], m+1):
            if rewards[j] == 0:
                rewards[j] = job_list[i][1]
                count += 1
                break
            else:
                continue
        if count == m:
            break
    
    print(sum(rewards))


if __name__ == "__main__":
    main()