Problem:


Score : 400 points

Problem Statement

There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.

You can take and complete at most one of these jobs in a day.

However, you cannot retake a job that you have already done.

Find the maximum total reward that you can earn no later than M days from today.

You can already start working today.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i \leq 10^5

1 \leq B_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the maximum total reward that you can earn no later than M days from today.

Sample Input 1

3 4
4 3
4 1
2 2

Sample Output 1

5

You can earn the total reward of 5 by taking the jobs as follows:

Take and complete the first job today. You will earn the reward of 3 after four days from today.

Take and complete the third job tomorrow. You will earn the reward of 2 after two days from tomorrow, that is, after three days from today.

Sample Input 2

5 3
1 2
1 3
1 4
2 1
2 3

Sample Output 2

10

Sample Input 3

1 1
2 1

Sample Output 3

0



Sample input:
3 4
4 3
4 1
2 2


Sample output:
5

Submission status: Wrong Answer

Solution code:
#input = raw_input
import numpy as np

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

#not_done = [True for _ in range(M)]

counts = [0 for _ in range(M)]
#cumsum_counts = np.zeros(M, dtype=int)

all_sum = 0

ue_end_i = M-1
for A, B in pairs:
    if A > M:
        continue
    ue_start_i = M-A+1
    if ue_start_i <= ue_end_i:
        ue_limit = ue_end_i - ue_start_i + 1
        ue_sum = sum(counts[ue_start_i:])
        #ue_sum = cumsum_counts[ue_start_i]
        hamidashi = max(ue_sum - ue_limit, 0)
    else:
        # ue_start_i == M
        ue_sum = 0
        hamidashi = 0
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi # 0 ~ M-A
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni

    if aki >= 1:
        out += B
        counts[M-A] += 1
        #cumsum_counts[M-A:] += 1
        all_sum += 1

print(out)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
jobs = []
for n in range(N):
    A, B = map(int, input().split())
    jobs.append([M-A, B])

jobs.sort(key=lambda x: x[0])
jobs.sort(key=lambda x: -x[1])
# print(jobs)

r = 0
# jd = -1
dd = 0
count = 0
for n in range(N):
    # print("jd="+str(jd))
    # print("==")
    # print("dd="+str(dd))
    # print("jobs["+str(n)+"][0]="+str(jobs[n][0]))
    if jobs[n][0] < 0:
        # print("jobs[n][0]<0")
        continue
    if jobs[n][0] < dd:
        # print("jobs[n][0]>dd")
        continue
    # print("r+="+str(jobs[n][1]))
    # jd = jobs[n][0]
    r += jobs[n][1]
    dd += 1


print(r)

Submission status: Wrong Answer

Solution code:
#input = raw_input
import numpy as np

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

#not_done = [True for _ in range(M)]

counts = [0 for _ in range(M)]
cumsum_counts = np.zeros(M, dtype=int)

all_sum = 0

ue_end_i = M-1
for A, B in pairs:
    if A > M:
        continue
    ue_start_i = M-A+1
    if ue_start_i <= ue_end_i:
        ue_limit = ue_end_i - ue_start_i + 1
        #ue_sum = sum(counts[ue_start_i:])
        ue_sum = cumsum_counts[ue_start_i]
        hamidashi = max(ue_sum - ue_limit, 0)
    else:
        # ue_start_i == M
        ue_sum = 0
        hamidashi = 0
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi # 0 ~ M-A
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni

    if aki >= 1:
        out += B
        #counts[M-A] += 1
        cumsum_counts[M-A:] += 1
        all_sum += 1

print(out)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
mix_list = sorted([list(map(int, input().split())) for _ in range(n)],
                 key=lambda x:(x[0], -x[1]))
first = mix_list[0][0]

a_list = [x[0] for x in mix_list]
b_list = [x[1] for x in mix_list]

idx = 0
idx_list = [a_list.index(i) for i in range(first, m+1) if i in a_list]

h = []
score = 0
for i in range(first, m+1):
  # hの更新があるかどうか
  if idx < len(idx_list):
    if i >= a_list[idx_list[idx]]:
      if idx < len(idx_list)-1:
        start = idx_list[idx]
        end = idx_list[idx+1]
    # 最後の日数の場合
      else:
        start = idx_list[idx]
        end = n
    
      idx += 1
      h = h + b_list[start:end]

  # リストの中から最大値を取ってくる
  if len(h) != 0:
    h_max = max(h)
    score += h_max
    h.remove(h_max)
  else:
    continue

print(score)

Submission status: Wrong Answer

Solution code:
n,d = list(map(int, input().split(" ")))
works = sorted([ list(map(int, input().split(" "))) for _ in range(n) ], reverse=True)
money = 0

candi_n = 0
candi_m = 0
j = 0
chosen = []
while(0<d):
    searching_j = True
    for i in range(j,n):
        if i in chosen:
            continue
        if searching_j and works[i][0] < d:
            searching_j = False
            j = i
        if candi_m < works[i][1]:
            candi_n = i
            candi_m = works[i][1]
    chosen.append(candi_n)
    money += candi_m
    candi_m = 0
    d -= 1

print(money)

Submission status: Wrong Answer

Solution code:
input = raw_input

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

#not_done = [True for _ in range(M)]

counts = [0 for _ in range(M)]
all_sum = 0

ue_end_i = M-1
for A, B in pairs:
    if A > M:
        continue
    ue_start_i = M-A+1
    if ue_start_i <= ue_end_i:
        ue_limit = ue_end_i - ue_start_i + 1
        ue_sum = sum(counts[ue_start_i:])
        hamidashi = max(ue_sum - ue_limit, 0)
    else:
        # ue_start_i == M
        ue_sum = 0
        hamidashi = 0
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi # 0 ~ M-A
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni

    if aki >= 1:
        out += B
        #print(A, B)
        #not_done[i] = False
        #break
        counts[M-A] += 1
        all_sum += 1

print(out)

Submission status: Wrong Answer

Solution code:
import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)
                else:
                    break
    return ans

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

Submission status: Wrong Answer

Solution code:
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_map = {}
max_sort_list = [0]

def insert_max_sort(b):
    for idx in range(len(max_sort_list)):
        if b > max_sort_list[idx]:
            max_sort_list.insert(idx,b)
            if len(max_sort_list) > M:
                max_sort_list.pop()
            break

for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    insert_flag = True
    if a > M or b < max_sort_list[len(max_sort_list)-1]:
        continue
    if a in each_days_map.keys():
        for idx in range(len(each_days_map[a])):
            if b > each_days_map[a][idx]:
                each_days_map[a].insert(idx,b)
                if len(each_days_map[a]) > (M - a + 1):
                    removed_num = each_days_map[a][len(each_days_map[a])-1]
                    each_days_map[a].pop()
                    max_sort_list.remove(removed_num)
                insert_max_sort(b)
                insert_flag = False
                break
        if insert_flag and M > len(each_days_map[a]) and (M - a + 1) > len(each_days_map[a]):
            each_days_map[a].append(b)
            insert_max_sort(b)
    else:
        each_days_map[a] = [b]
        insert_max_sort(b)
print(sum(max_sort_list))

Submission status: Wrong Answer

Solution code:
import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)
                else:
                    break
    return ans

Submission status: Wrong Answer

Solution code:
# 3.4.3

import re
from collections import deque
from functools import reduce
from itertools import permutations
from math import pi
from operator import itemgetter
from operator import mul
from operator import xor
from os import linesep
from queue import PriorityQueue
from sys import stdin


def rline() -> str:
    return stdin.readline().strip()


def rlines(hint: int = 1):
    ret = ['' for i in range(hint)]
    for i in range(hint):
        ret[i] = rline()
    return ret


def htokens(hint: int = 1):
    lns = rlines(hint)
    ret = list(map(lambda ln: ln.split(), lns))
    return ret


def vtokens(hint: int = 1):
    m, _ = htokens()
    wint = len(m)
    ret = [[None] * hint for i in range(wint)]
    for y in range(hint):
        if y != 0:
            m, _ = htokens()
        # convert horizontal to vertical
        x = 0
        for v in m:
            ret[x][y] = v
            x += 1
    # if return value has one and only one element(list),
    if wint == 1:
        # then add an empty list.
        ret.append([])
    return ret


def rint(radix: int = 10) -> int:
    return int(rline(), radix)


def hints(hint: int = 1, radix: int = 10):
    ret = htokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def vints(hint: int = 1, radix: int = 10):
    ret = vtokens(hint)
    for i in range(len(ret)):
        ret[i] = list(map(lambda v: int(v, radix), ret[i]))
    return ret


def mat(hint: int, wint: int):
    return [[None]*wint for i in range(hint)]


def filllist(lst, value: int) -> None:
    # destructive.
    for i in range(len(lst)):
        lst[i] = value


def isprime(n: int) -> bool:
    if n <= 1:
        return False
    if n in (2, 3, 5):
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    lst = int(n**0.5)
    f = 5
    while f <= lst:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True


def strmat(matrix, lnsep: str = linesep, fieldsep: str = ' ') -> str:
    return lnsep.join(map(lambda row: fieldsep.join(map(str, row)), matrix))


def strbool(boolval: int) -> str:
    return ['No', 'Yes'][boolval]


def solve() -> None:
    # read here
    (n, m) = hints()[0]
    ab_s = hints(n)

    # solve here

    # delay asc, prize desc
    ab_s.sort(key=itemgetter(1), reverse=True)
    ab_s.sort(key=itemgetter(0), reverse=False)

    ans = 0
    tasks = PriorityQueue(n)
    for t in range(m + 1):
      ans = 1

    # print here
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
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 BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


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

AB.sort(key=lambda ab: (-ab[1], ab[0]))
bit = BinaryIndexedTree(size=M)

ans = 0
for a, b in AB:
    if M - a < 0:
        continue
    # 入れられる？
    cap = M - a - bit.sum(M - a) + 1
    if cap > 0:
        ans += b
        bs = bit.sum(M - a)
        # どこに入れよう？
        ok = 0
        ng = M - a + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if bit.sum(mid) == bs:
                ok = mid
            else:
                ng = mid
        bit.add(ok, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi])
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)
                else:
                    break
    return ans

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
select = [0] * n
jobs = [tuple(map(int, input().split())) for i in range(n)]
jobs.sort(key=itemgetter(1), reverse=True)
jobs.sort(key=itemgetter(0))
ans = 0
limit = jobs[0][0]
max_tmp = 0
max_index = -1
i = 0
while limit <= m:
    if limit >= jobs[i][0] and select[i] == 0:
        if max_tmp < jobs[i][1]:
            max_tmp = jobs[i][1]
            max_index = i
    else:
        ans += max_tmp
        select[max_index] = 1
        limit += 1
        max_tmp = 0
        max_index = -1
        i = 0
    i += 1
    if i == n:
        i = 0
        ans += max_tmp
        limit += 1
print(ans)

Submission status: Wrong Answer

Solution code:
input = raw_input

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

#not_done = [True for _ in range(M)]

counts = [0 for _ in range(M)]
all_sum = 0
for A, B in pairs:
    if A > M:
        continue
    ue_limit = M -1 - (M-A+1) + 1 if M-A+1 <= M -1 else 0 # M-A+1 ~ M-1 
    ue_sum = sum(counts[M-A+1:])
    hamidashi = max(ue_sum - ue_limit, 0)
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni
    #print(cur_limit, sudeni, aki, counts, pairs)
    if aki >= 1:
        out += B
        #print(A, B)
        #not_done[i] = False
        #break
    counts[M-A] += 1
    all_sum += 1

print(out)

Submission status: Wrong Answer

Solution code:
import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi])
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    print(ai, bi)
                else:
                    break
    return ans

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

Submission status: Wrong Answer

Solution code:
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 BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


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

AB.sort(key=lambda ab: (-ab[1], ab[0]))
bit = BinaryIndexedTree(size=M)

ans = 0
for a, b in AB:
    if M - a < 0:
        continue
    # 入れられる？
    cap = M - a - bit.sum(M - a) + 1
    if cap > 0:
        ans += b
        # どこに入れよう？
        ok = 0
        ng = M - a + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if M - mid - bit.sum(mid) + 1 <= cap:
                ok = mid
            else:
                ng = mid
        bit.add(ok, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
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 BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


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

AB.sort(key=lambda ab: (-ab[1], ab[0]))
bit = BinaryIndexedTree(size=M)

ans = 0
for a, b in AB:
    if M - a < 0:
        continue
    # 入れられる？
    cap = M - a - bit.sum(M - a) + 1
    if cap > 0:
        ans += b
        # どこに入れよう？
        ok = 0
        ng = M - a + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if M - a - bit.sum(mid) + 1 <= cap:
                ok = mid
            else:
                ng = mid
        bit.add(ok, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
n, m = map(int, input().split())
B = [[] for _ in range(m+1)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m: B[a] += [-b]
print(B)
C = []
s = 0
for i in range(m+1):
    for b in B[i]: heappush(C, b)
    if C: s += heappop(C)
print(-s)

Submission status: Wrong Answer

Solution code:
input = raw_input

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

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

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

#not_done = [True for _ in range(M)]

counts = [0 for _ in range(M)]
all_sum = 0
for A, B in pairs:
    if A > M:
        continue
    ue_limit = M - (M-A+1) 
    ue_sum = sum(counts[M-A+1:])
    hamidashi = max(ue_sum - ue_limit, 0)
    #print("hamidashi", hamidashi)

    cur_limit = M- A + 1 - hamidashi
    sudeni = all_sum - ue_sum
    aki = cur_limit - sudeni
    #print(cur_limit, sudeni, aki, counts, pairs)
    if aki >= 1:
        out += B
        #print(A, B)
        #not_done[i] = False
        #break
    counts[M-A] += 1
    all_sum += 1

print(out)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x:-x[1])
ans=0
for i in range(m):
    ltmp=[j for j in l if j[0]<=i+1]
    if len(ltmp)>0:
        ans+=ltmp[0][0]
        l.remove(ltmp[0])
print(ans)

Submission status: Wrong Answer

Solution code:
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_map = {}
max_sort_list = [0]

def insert_max_sort(b):
    for idx in range(len(max_sort_list)):
        if b > max_sort_list[idx]:
            max_sort_list.insert(idx,b)
            if len(max_sort_list) > M:
                max_sort_list.pop()

for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a > M or b < max_sort_list[len(max_sort_list)-1]:
        break
    if a in each_days_map.keys():
        for idx in range(len(each_days_map[a])):
            if b > each_days_map[a][idx]:
                each_days_map[a].insert(idx,b)
                for imax in range(len(max_sort_list)):
                    if b > max_sort_list[idx]:
                        max_sort_list.insert(idx,b)
                        if len(max_sort_list) > M:
                            max_sort_list.pop()
                if len(each_days_map[a]) > (M - a + 1):
                    each_days_map[a].pop()
                break
        if M > len(each_days_map[a]) and (M - a + 1) > len(each_days_map[a]):
            each_days_map[a].append(b)
            insert_max_sort(b)
    else:
        each_days_map[a] = [b]
        insert_max_sort(b)
print(sum(max_sort_list))

Submission status: Wrong Answer

Solution code:
NM = input()
N = int(NM.split(' ')[0])
M = int(NM.split(' ')[1])
each_days_map = {}
max_sort_list = [0]

def insert_max_sort(b):
    for idx in range(len(max_sort_list)):
        if b > max_sort_list[idx]:
            max_sort_list.insert(idx,b)
            if len(max_sort_list) > M:
                max_sort_list.pop()

for i in range(N):
    ab = input()
    a = int(ab.split(' ')[0])
    b = int(ab.split(' ')[1])
    if a > M and b < max_sort_list[len(max_sort_list)-1]:
        break
    if a in each_days_map.keys():
        for idx in range(len(each_days_map[a])):
            if b > each_days_map[a][idx]:
                each_days_map[a].insert(idx,b)
                for imax in range(len(max_sort_list)):
                    if b > max_sort_list[idx]:
                        max_sort_list.insert(idx,b)
                        if len(max_sort_list) > M:
                            max_sort_list.pop()
                if len(each_days_map[a]) > (M - a + 1):
                    each_days_map[a].pop()
                break
        if M > len(each_days_map[a]) and (M - a + 1) > len(each_days_map[a]):
            each_days_map[a].append(b)
            insert_max_sort(b)
    else:
        each_days_map[a] = [b]
        insert_max_sort(b)
print(sum(max_sort_list))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

# nData = [[ 0 for i in range(3)]for j in range(N)]
nData = [ 0 for i in range(M+1)]
nAns = 0

for i in range(N):
  TmpA, TmpB=map(int,input().split())
  TmpMin=1000001
  TmpMap=1000001
  Flag=0
  for j in range(M-TmpA+1):
    TmpC = M-TmpA-j
    TmpE = nData[TmpC]
#    print(TmpC)
    if TmpE==0:
      nData[TmpC]=TmpB
      Flag=1
      nAns += TmpB
      break
    if TmpE < TmpMin:
      TmpMin=TmpE
      TmpMap=TmpC
  if Flag==0 and TmpB > TmpMin:
    nData[TmpMap]=TmpB
    nAns += (TmpB - TmpMin)

# print(nData)

print(nAns)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: x[0])
ab.sort(key = lambda x: -x[1])
cnt, ans = 0, 0
# print(ab)
bit = BIT(M)
for a, b in ab:
    # print([bit.sum(i) for i in range(1, M+1)])
    if M-a >= 0 and bit.sum(M-a+1) <= M-a:
        ans += b
        bit.add(M-a+1, 1)
        cnt += 1
        if cnt == M:
            break
# print([bit.sum(i) for i in range(1, M+1)])
# print()
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
job = []
for i in range(n):
    a, b = map(int, input().split())
    if n > m:
        job.append([b, a])
    else:
        job.append([a, b])
list.sort(job, reverse=True)

a = 0
if n > m:
    d = 0
    for j in job:
        if d + j[1] < m:
            a = a + j[0]
            d = d + 1
else:
    d = 0
    for j in job:
        if d + j[0] < m:
            a = a + j[1]
            d = d + 1
print(a)

Submission status: Wrong Answer

Solution code:
import heapq
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:
    heapq.heappush(k, l[j][1])
    j+=1
  if len(k)!=0:
  	ans+=k[-1]
  	k.pop(-1)
print(ans)

Submission status: Wrong Answer

Solution code:
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 BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


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

AB.sort(key=lambda ab: (-ab[1], ab[0]))
bit = BinaryIndexedTree(size=M)

ans = 0
for a, b in AB:
    # 入れられる？
    if M - a < 0:
        continue
    cap = M - a - bit.sum(M - a) + 1
    if cap > 0:
        ans += b
        # どこに入れよう？
        ok = 0
        ng = M - a + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if M - a - bit.sum(mid) + 1 == cap:
                ok = mid
            else:
                ng = mid
        bit.add(ok, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
def p_d():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]
    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)

Submission status: Wrong Answer

Solution code:
import bisect
n, m = [int(i) for i in input().split()]
d = []
for i in range(n):
    a, b = [int(_) for _ in input().split()]
    d.append([a, b])

d.sort(reverse=True)
l = [-1 for i in range(m+1)]
for i in range(n):
    if d[i][0] <= m and l[d[i][0]] == -1:
        l[d[i][0]] = i
ans = 0
cand = []
key = []
for i in range(1, m+1):
    if l[i] != -1:
        idx = bisect.bisect_left(cand, d[l[i]][1])
        if idx == len(cand):
            ans += d[l[i]][1]
            if l[i] + 1 < n and d[l[i]+1][0] == d[l[i]][0]:
                idx = bisect.bisect_left(cand, d[l[i]+1][1])
                cand.insert(idx, d[l[i]+1][1])
                key.insert(idx, i)
                l[i] += 1
        else:
            if len(cand) > 0:
                ans += cand[-1]
                if l[key[-1]] + 1 < n and d[l[key[-1]]+1][0] == d[l[key[-1]]][0]:
                    idx = bisect.bisect_left(cand, d[l[key[-1]]+1][1])
                    cand.insert(idx, d[l[key[-1]+1]][1])
                    key.insert(idx, key[-1])
                    l[key[-1]] += 1
                del cand[-1]
                del key[-1]
    else:
        if len(cand) > 0:
            ans += cand[-1]
            if l[key[-1]] + 1 < n and d[l[key[-1]] + 1][0] == d[l[key[-1]]][0]:
                idx = bisect.bisect_left(cand, d[l[key[-1]] + 1][1])
                cand.insert(idx, d[l[key[-1] + 1]][1])
                key.insert(idx, key[-1])
                l[key[-1]] += 1
            del cand[-1]
            del key[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
# import bisect
N, M = map(int, input().split())
ABs = [list(map(int, input().split())) for _ in range(N)]

lists = [[] for _ in range(10**5 + 1)]
availables = []
for A, B in ABs:
    heapq.heappush(lists[A], -1 * B)
    # bisect.insort(lists[A], B)

ans = 0
for i in range(1, M + 1):
    # for b in lists[i]:
    #     bisect.insort(availables, b)
    availables = list(heapq.merge(availables, lists[i]))
    if availables:
        ans -= heapq.heappop(availables)

print(ans)

Submission status: Wrong Answer

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 = []
d = 1
flag = True

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