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:
from collections import defaultdict
n, m = [int(v) for v in input().split()]
arbs = [tuple(int(v) for v in input().split()) for _ in range(n)]
rewards = sorted(set([a[1] for a in arbs]), reverse=True)
cands = {rw: 0 for rw in rewards}
day_arbs = defaultdict(list)
for arb in arbs:
    t = m - arb[0]
    if t >= 0:
        day_arbs[t].append(arb[1])
total_reward = 0
for day in range(m-1, -1, -1):
    for rw in day_arbs[day]:
        cands[rw] += 1
    for rw in rewards:
        if cands[rw] > 0:
            total_reward += rw
            cands[rw] -= 1
            break

print(total_reward)

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

x=sorted(ab, key=lambda x :x[1])
x.reverse()

v=[i for i in range(1,m+1)]


for i in range(n):
    if len(v)==0:
        break
    for j in range(m):
        if v[-1]>=x[i][0]:
            if v[j]>=x[i][0]:
                ans+=x[i][1]
                del v[j]
                break
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, queue
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] = collections.Counter(AB_dict[k])
#  for k in AB_dict.keys():
#      AB_dict[k].sort()
perr(AB_dict)

#  tmp = []
#  day = 1
#  ans = 0
#  crr = 0
#  while True:
#      if day == M + 1:
#          break

#      if crr < N:
#          if AB[crr][0] > day:
#              perr('nextday')
#              perr(tmp)
#              day += 1
#              if len(tmp) == 0:
#                  continue
#              tmp.sort()
#              ans += tmp.pop()
#          else:
#              perr('add')
#              tmp.append(AB[crr][1])
#              crr += 1
#      else:
#          if len(tmp) == 0:
#              break
#          tmp.sort()
#          for time in range(M-day+1):
#              ans += tmp.pop()
#              day += 1
        
#  print(ans)
#  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 = queue.PriorityQueue()
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in keys:
        for ab in AB_dict[i]:
            tmp.put((-ab, ab))
        #  tmp[len(tmp):] = AB_dict[i]
    perr('tmp')
    perr(tmp)
    if tmp.empty():
        continue
    #  tmp.sort()
    #  max_v = max(tmp)
    #  ans += max_v
    ans += tmp.get()[1]
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for j in range(M):
    X = [X[i] for i in range(len(X)) if X[i][0] <= M-j]

    if not X:
        break


    y = [X[i][1] for i in range(len(X))]
    cnt += max(y)
    maxindex = [i for i, x in enumerate(y) if x == max(y)]

    z = [X[i][0] for i in range(len(X)) if i in maxindex]
    z = max(z)
    ppop = X.index([z, max(y)])

    X.pop(ppop)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
P = [[] for _ in range(10**5 + 1)]

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

p = []
ans = 0

for m in range(1, M+1):
    p += P[m]
    p = sorted(p, reverse=True)
    if p:
        ans += p[0]
        p.pop(0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    ab = sorted(ab)
    ans = 0

    for i in range(1, m + 1):
        idx = -1
        max_value = -1
        for j in range(len(ab)):
            if ab[j][0] <= i:
                if max_value <= ab[j][1]:
                    max_value = ab[j][1]
                    idx = j
            else:
                break

        if idx != -1:
            ans += max_value
            ab.pop(idx)

    print(ans)


if __name__ == '__main__':
    p_d()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in [0]*n]
l.sort(key=lambda x:x[0])
ans = 0
tmpl = []
flag = True

for d in range(1,m+1):
  while  len(l)>=1 and l[0][0] <= d:
    tmpl.append(l[0][1])
    del l[0]
  if len(tmpl) > 0:
    maxindex = tmpl.index(max(tmpl))
    ans += tmpl[maxindex]
    del tmpl[maxindex]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys
import heapq

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(-bi)
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        if not cur: cur= ref
        else: cur+= ref
        heapq.heapify(cur)
    #
    if not cur: continue
    tot+= heapq.heappop(cur)
#
print( -tot )

Submission status: Time Limit Exceeded

Solution code:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class PrimalDual:
    """
    最小費用流 ダイクストラ版
    """

    def __init__(self, graph=None, residual=None):
        """
        :param list of (list of (int, int, int)) graph: (to, cap, cost) の隣接リスト
        :param list of (list of (list of (int|list))) residual: (to, cap, cost, rev) の残余グラフ
        """
        assert (graph and not residual) or (not graph and residual)
        if graph:
            self.graph = self.residual_graph(graph)
        else:
            self.graph = residual

    @staticmethod
    def residual_graph(graph):
        """
        残余グラフ構築
        :param list of (list of (int, int, int)) graph: (to, cap, cost) の隣接リスト
        :rtype: list of (list of (list of (int|list)))
        :return: (to, cap, cost, rev) の残余グラフ
        """
        ret = [[] for _ in range(len(graph))]
        for v in range(len(graph)):
            for u, cap, cost in graph[v]:
                rev = [v, 0, -cost]
                edge = [u, cap, cost, rev]
                rev.append(edge)
                ret[v].append(edge)
                ret[u].append(rev)
        return ret

    def solve(self, from_v, to_v, flow):
        """
        :param int from_v:
        :param int to_v:
        :param int flow:
        :rtype: int
        """
        total_cost = 0
        prevv = [-1] * len(self.graph)
        preve = [-1] * len(self.graph)
        # ポテンシャル
        h = [0] * len(self.graph)
        remains = flow
        while remains > 0:
            dist = [float('inf')] * len(self.graph)
            dist[from_v] = 0
            heap = [(0, from_v)]

            # Dijkstra
            while heap:
                d, v = heapq.heappop(heap)
                if d > dist[v]:
                    continue
                for edge in self.graph[v]:
                    u, cap, cost, rev = edge
                    if cap > 0 and dist[v] + cost + h[v] - h[u] < dist[u]:
                        dist[u] = dist[v] + cost + h[v] - h[u]
                        prevv[u] = v
                        preve[u] = edge
                        heapq.heappush(heap, (dist[u], u))

            if dist[to_v] == float('inf'):
                # これ以上流せない
                break

            for i, d in enumerate(dist):
                h[i] += d

            # 最短路に流せる量
            flow = remains
            v = to_v
            while v != from_v:
                cap = preve[v][1]
                flow = min(cap, flow)
                v = prevv[v]

            # 最短路に flow だけ流す
            v = to_v
            while v != from_v:
                preve[v][1] -= flow
                preve[v][3][1] += flow
                v = prevv[v]

            remains -= flow
            total_cost += flow * h[to_v]
        return total_cost


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

S = M
T = M + 1
graph = [[] for _ in range(M + 2)]
for i in range(M):
    graph[i].append((T, 1, 0))
for i in range(M - 1):
    graph[i + 1].append((i, IINF, 0))
for a, b in AB:
    if M - a >= 0:
        graph[S].append((M - a, 1, -b))

ans = -PrimalDual(graph).solve(S, T, IINF)
print(ans)

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 i in range(1,M+1):
    #     DV[i].sort(reverse=True)
    #     DV[i] = DV[i][:M-i+1]
    ans = 0
    tmpL = []
    for l in DV:
        tmpL += l
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
    print(ans)
        
        



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

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] = collections.Counter(AB_dict[k])
#  for k in AB_dict.keys():
#      AB_dict[k].sort()
perr(AB_dict)

#  tmp = []
#  day = 1
#  ans = 0
#  crr = 0
#  while True:
#      if day == M + 1:
#          break

#      if crr < N:
#          if AB[crr][0] > day:
#              perr('nextday')
#              perr(tmp)
#              day += 1
#              if len(tmp) == 0:
#                  continue
#              tmp.sort()
#              ans += tmp.pop()
#          else:
#              perr('add')
#              tmp.append(AB[crr][1])
#              crr += 1
#      else:
#          if len(tmp) == 0:
#              break
#          tmp.sort()
#          for time in range(M-day+1):
#              ans += tmp.pop()
#              day += 1
        
#  print(ans)
#  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 = {}
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in keys:
        #  tmp.extend(AB_dict[i])
        for j in AB_dict[i].items():
            if j[0] in tmp.keys():
                tmp[j[0]] += j[1]
            else:
                tmp[j[0]] = j[1]
        #  tmp[len(tmp):] = AB_dict[i]
    perr('tmp')
    perr(tmp)
    if len(tmp) == 0:
        continue
    max_v = max(tmp.keys())
    #  tmp.sort()
    #  max_v = max(tmp)
    #  ans += max_v
    ans += max_v
    tmp[max_v] -= 1
    if tmp[max_v] == 0:
        del tmp[max_v]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys
import heapq

n,m= [ int(x) for x in sys.stdin.readline().split() ]
baito=[ [] for _ in range(m) ]
for _ in range(n):
    ai,bi = [ int(x) for x in sys.stdin.readline().split() ]
    ai-=1
    if ai<m: baito[ai].append(-bi)
#
tot=0
cur=[]
for i in range(m):
    ref= baito[i]
    if ref:
        if not cur: cur= ref
        else: cur+= ref
    #
    if not cur: continue
    heapq.heapify(cur)
    tot+= heapq.heappop(cur)
#
print( -tot )

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)]
rewards = sorted(set([a[1] for a in arbs]), reverse=True)
cands = {rw: [] for rw in rewards}
for arb in arbs:
    t = m - arb[0]
    if t >= 0:
        cands[arb[1]].append(t)
cands = {rw: sorted(d, reverse=True) for rw, d in cands.items()}
total_reward = 0
for day in range(m-1, -1, -1):
    for rw in rewards:
        if len(cands[rw]) > 0 and cands[rw][0] >= day:
            total_reward += rw
            cands[rw].pop(0)
            break

print(total_reward)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(N))
AB.append([0,0])
AB.sort()
p = 0
ans = 0
for i in range(M+1):
    while p<=N and (AB[p][0] <= i) :
        p += 1
    m = AB.index(max(AB[:p],key = lambda x:x[1]))
    ans += AB[m][1]
    AB[m] = [0,0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
absort=sorted(ab,key=lambda x:(x[0],-x[1]))

ans=0
temp=[]
for i in range(1,m+1):
    while absort:
        if absort[0][0]<=i:
            temp.append(absort[0][1])
            del absort[0]
        else:
            break
    if temp:
        tmpmax=max(temp)
        ans+=tmpmax
        temp.remove(tmpmax)

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)
points = list(range(M+1))

from  bisect import bisect_right

for a,b in AB:
    point = M - a
    i = bisect_right(points,point)
    if i > 0:
        days[points[i-1]] = b
        points.pop(i-1)
print(sum(days))

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
def main():
    n,m = map(int,input().split(' '))
    w = [list(map(int,input().split(' '))) for i in range(n)]
    w=sorted(w)
    ans = 0
    l = []
    tmp = 0
    for i in range(1,m+1):
        while w and w[0][0] <= i:
            hq.heappush(l,-w.pop(0)[1])
        if l:
            ans -=hq.heappop(l)
    print(ans)

if __name__ == '__main__':
    main()

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)

#  tmp = []
#  day = 1
#  ans = 0
#  crr = 0
#  while True:
#      if day == M + 1:
#          break

#      if crr < N:
#          if AB[crr][0] > day:
#              perr('nextday')
#              perr(tmp)
#              day += 1
#              if len(tmp) == 0:
#                  continue
#              tmp.sort()
#              ans += tmp.pop()
#          else:
#              perr('add')
#              tmp.append(AB[crr][1])
#              crr += 1
#      else:
#          if len(tmp) == 0:
#              break
#          tmp.sort()
#          for time in range(M-day+1):
#              ans += tmp.pop()
#              day += 1
        
#  print(ans)
#  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 = []
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in keys:
        #  tmp.extend(AB_dict[i])
        tmp[len(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:
import heapq

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

jobs = []
day2moneys = {}
for i in range(N):
    day,money = list(map(int, input().split()))

    if day in day2moneys:
        day2moneys[day].append(money)
    else:
        day2moneys[day] = [money]

for k,v in day2moneys.items():
    v.sort(reverse=True)

ans = 0
for i in range(1,M+1):
    max_money = 0
    max_day = None
    for j in range(1,i+1):
        if j in day2moneys and len(day2moneys[j])>0:
            # print(day2moneys[j])
            if max_money < day2moneys[j][0]:
                max_money = day2moneys[j][0]
                max_day = j
    if max_day != None:
        ans += max_money
        day2moneys[max_day].remove(day2moneys[max_day][0])
    # print(ans)
print(ans)

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 i in range(1,M+1):
        DV[i].sort(reverse=True)
        DV[i] = DV[i][:M-i+1]
    ans = 0
    tmpL = []
    for l in DV:
        tmpL += l
        tmpL.sort(reverse=True)
        ans += tmpL.pop(0)
    print(ans)
        
        



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

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.append([a,b])
l.sort()
l.append([0,0])
ans=0
k=[]
j=0
for i in range(1,m+1):
  while j<=n and l[j][0]<=i:
    k.append(l[j][1])
    j+=1
  if len(k)!=0:
  	ans+=max(k)
  	k.remove(max(k))
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):
    a,b = list(map(lambda x: int(x), input().split()))
    jobs.append([b,a])

# 貪欲解法
# 最終日から決める
jobs.sort()
jobs.reverse()
ans = 0
for i in range(m+1):
    # 給料大きい順にみて、振り込みがi+1以内なら働く
    for j in range(len(jobs)):
        if jobs[j][1] < i+1:
            ans += jobs[j][0]
            del jobs[j]
            break

            
print (ans)

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)

#  tmp = []
#  day = 1
#  ans = 0
#  crr = 0
#  while True:
#      if day == M + 1:
#          break

#      if crr < N:
#          if AB[crr][0] > day:
#              perr('nextday')
#              perr(tmp)
#              day += 1
#              if len(tmp) == 0:
#                  continue
#              tmp.sort()
#              ans += tmp.pop()
#          else:
#              perr('add')
#              tmp.append(AB[crr][1])
#              crr += 1
#      else:
#          if len(tmp) == 0:
#              break
#          tmp.sort()
#          for time in range(M-day+1):
#              ans += tmp.pop()
#              day += 1
        
#  print(ans)
#  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 = []
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in keys:
        tmp.extend(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:
import numpy as np
N,M = map(int,input().split())

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

work.append([10**8,0])
work = np.array(work)
sorted_work = work[np.argsort(work[:,0])]

l = []
ans = 0
index = 0
for i in range(1,M+1):
    while sorted_work[index,0] <= i:
        l.append(sorted_work[index,1])
        index += 1

    if len(l) != 0:    
        ans += max(l)
        l.remove(max(l))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [tuple(int(i) for i in input().split()) for _ in range(n)]
ab.sort(key=lambda x: x[1], reverse=True)
result = 0
for i in range(1, m + 1):
    value = [k for k in ab if k[0] <= i]
    if value:
        result += value[0][1]
        ab.remove(value[0])
print(result)

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)

#  tmp = []
#  day = 1
#  ans = 0
#  crr = 0
#  while True:
#      if day == M + 1:
#          break

#      if crr < N:
#          if AB[crr][0] > day:
#              perr('nextday')
#              perr(tmp)
#              day += 1
#              if len(tmp) == 0:
#                  continue
#              tmp.sort()
#              ans += tmp.pop()
#          else:
#              perr('add')
#              tmp.append(AB[crr][1])
#              crr += 1
#      else:
#          if len(tmp) == 0:
#              break
#          tmp.sort()
#          for time in range(M-day+1):
#              ans += tmp.pop()
#              day += 1
        
#  print(ans)
#  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 = []
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in 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:
import heapq
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
heapq.heapify(lst)
r = []
heapq.heapify(r)
ans = 0
d = 1

while True:
    while True:
        if len(lst) != 0:
            p_lst = heapq.heappop(lst)
            if p_lst[0] <= d:
                heapq.heappush(r, - p_lst[1])
            else:
                heapq.heappush(lst, p_lst)
                break
        else:
            break
    if len(r) != 0:
        ans += - heapq.heappop(r)
    d += 1
    if d > m:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())
validJobSalary = [[] for _ in range(M + 1)]  # a[k]には最終日のk日前時点で働いた場合に最終日までに報酬が得られる仕事の報酬リストが入っている
ans = 0
salaryForCurrentlyAvailableJobs = []
for line in sys.stdin:
    A, B = map(int, line.split())
    if A <= M:
        validJobSalary[A].append(B)

for salaryList in validJobSalary:
    salaryForCurrentlyAvailableJobs.extend(salaryList)
    if salaryForCurrentlyAvailableJobs:
        highest = max(salaryForCurrentlyAvailableJobs)
        ans += highest
        salaryForCurrentlyAvailableJobs.remove(highest)

print(ans)