Problem p02948 (python)

Fixed submission:
import heapq


class Job:

    def __repr__(self):
        return "%d,%d".format(self.days, self.reward)

    def __lt__(self, other):
        return self.reward < other.reward

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days

N, M = list(map(int, input().split()))
h = []
jobs = []

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.append(Job(job_id=i, reward=B, days=A))


jobs = sorted(jobs, key=lambda j: j.days)
idx = 0
c = 0

for i in range(1, M+1):
    while idx < N and jobs[idx].days <= i:
        heapq.heappush(h, -jobs[idx].reward)
        idx += 1

    if len(h) != 0:
        c += -heapq.heappop(h)

print(c)

Buggy submission (verdict: Runtime Error):
import heapq


class Job:

    def __repr__(self):
        return f'{self.days},{self.reward}'

    def __lt__(self, other):
        return self.reward < other.reward

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days

N, M = list(map(int, input().split()))
h = []
jobs = []

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.append(Job(job_id=i, reward=B, days=A))


jobs = sorted(jobs, key=lambda j: j.days)
idx = 0
c = 0

for i in range(1, M+1):
    while idx < N and jobs[idx].days <= i:
        heapq.heappush(h, -jobs[idx].reward)
        idx += 1

    if len(h) != 0:
        c += -heapq.heappop(h)

print(c)

Buggy submission (verdict: Runtime Error):
import math
from itertools import accumulate


class Job:

    def __repr__(self):
        return f'{self.reward},{self.days}'

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days


def dfs(memo, jobs, remaing_days):
    reward = 0

    key = str(jobs)

    if key in memo[remaing_days]:
        # print('return memo')
        return memo[remaing_days][key]

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(memo, remaining_jobs, remaing_days - 1)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    memo[remaing_days][key] = reward

    return reward


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

memo = { day: {}  for day in range(M+1) }

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(job_id=i, reward=B, days=A))

print(dfs(memo, jobs, M))

Buggy submission (verdict: Runtime Error):
import math
from itertools import accumulate


class Job:

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days


def dfs(jobs, remaing_days):
    reward = 0

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


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

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(job_id=i, reward=B, days=A))

print(dfs(jobs, M))

Buggy submission (verdict: Runtime Error):
class Job:

    def __init__(self, reward, days):
        self.reward = reward
        self.days = days


def dfs(jobs, remaing_days, selected_jobs):
    reward = 0

    # print(jobs, remaing_days)

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            next_selected_jobs = selected_jobs | set([job])
            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1, next_selected_jobs)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


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

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(reward=B, days=A))

print(dfs(jobs, M, set()))

Buggy submission (verdict: Runtime Error):
class Job:

    def __repr__(self):
        return f'Job(reward={self.reward}, days={self.days})'

    def __init__(self, reward, days):
        self.reward = reward
        self.days = days


def dfs(jobs, remaing_days, selected_jobs):
    reward = 0

    # print(jobs, remaing_days)

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            next_selected_jobs = selected_jobs | set([job])
            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1, next_selected_jobs)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


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

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(reward=B, days=A))

print(dfs(jobs, M, set()))

Buggy submission (verdict: Runtime Error):
import math
from itertools import accumulate
from typing import List, Set


class Job:

    def __repr__(self):
        return f'Job(reward={self.reward}, days={self.days})'

    def __init__(self, reward: int, days: int):
        self.reward = reward
        self.days = days


def dfs(jobs: Set[Job], remaing_days: int, selected_jobs: Set[Job]) -> int:
    reward = 0

    # print(jobs, remaing_days)

    if remaing_days == 0:
        return 0

    for job in jobs:
        if job.days <= remaing_days:
            # print(
            #     f'trying {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

            next_selected_jobs = selected_jobs | set([job])
            remaining_jobs = jobs - set([job])
            new_reward = job.reward + \
                dfs(remaining_jobs, remaing_days - 1, next_selected_jobs)

            # if reward < new_reward:
            #     print(
            #          f'pickup {job} sum: {new_reward} remaing_days:{remaing_days} selected:{selected_jobs}')
            reward = max(reward, new_reward)
        # else:
        #     print(
        #         f'fail to pickup {job} sum: {reward} remaing_days:{remaing_days} selected:{selected_jobs}')

    return reward


N, M = list(map(int, input().split()))
jobs: Set[Job] = set()

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.add(Job(reward=B, days=A))

print(dfs(jobs, M, set()))