Problem p03733 (python)

Fixed submission:
# -*- coding: utf-8 -*-
def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

ipt = input_str(2)
N, T = [int(i) for i in ipt[0]]
t = sorted([int(i) for i in ipt[1]])

total = 0
for i, ti in enumerate(t[:-1]):
    if t[i+1] - t[i] > T:
        total += T
    else:
        total += t[i+1] - t[i]

print total + T

Buggy submission (verdict: Runtime Error):
#-*- coding: utf-8 -*-

def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]


def input_str(row):
    res = []
    for _ in xrange(row):
        res.append(raw_input().split())
    return res


N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Buggy submission (verdict: Runtime Error):
#-*- coding: utf-8 -*-
def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

Buggy submission (verdict: Runtime Error):
import collections
import functools
import time

class memoized(object):
    def __init__(self, func):
       self.func = func
       self.cache = {}

    def __call__(self, *args):
       if not isinstance(args, collections.Hashable):
          return self.func(*args)

       if args in self.cache:
          return self.cache[args]

       else:
          value = self.func(*args)
          self.cache[args] = value
          return value

    def __repr__(self):
       return self.func.__doc__

    def __get__(self, obj, objtype):
       return functools.partial(self.__call__, obj)

def knapsack(items, maxweight):
    @memoized
    def bestvalue(i, j):
        if i == 0: return 0
        value, weight = items[i - 1]
        if weight > j:
            return bestvalue(i - 1, j)
        else:
            return max(bestvalue(i - 1, j),
                       bestvalue(i - 1, j - weight) + value)

    j = maxweight
    result = []
    for i in xrange(len(items), 0, -1):
        if bestvalue(i, j) != bestvalue(i - 1, j):
            result.append(items[i - 1])
            j -= items[i - 1][1]
    result.reverse()
    return bestvalue(len(items), maxweight), result

def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
start = time.time()
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack(items, W)[0]
print time.time() - start

Buggy submission (verdict: Runtime Error):
import collections
import functools

class memoized(object):
    '''Decorator. Caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned
    (not reevaluated).
    '''
    def __init__(self, func):
       self.func = func
       self.cache = {}
    def __call__(self, *args):
       if not isinstance(args, collections.Hashable):
          # uncacheable. a list, for instance.
          # better to not cache than blow up.
          return self.func(*args)
       if args in self.cache:
          return self.cache[args]
       else:
          value = self.func(*args)
          self.cache[args] = value
          return value
    def __repr__(self):
       '''Return the function's docstring.'''
       return self.func.__doc__
    def __get__(self, obj, objtype):
       '''Support instance methods.'''
       return functools.partial(self.__call__, obj)

def knapsack(items, maxweight):
    """
    Solve the knapsack problem by finding the most valuable
    subsequence of `items` subject that weighs no more than
    `maxweight`.

    `items` is a sequence of pairs `(value, weight)`, where `value` is
    a number and `weight` is a non-negative integer.

    `maxweight` is a non-negative integer.

    Return a pair whose first element is the sum of values in the most
    valuable subsequence, and whose second element is the subsequence.

    >>> items = [(4, 12), (2, 1), (6, 4), (1, 1), (2, 2)]
    >>> knapsack(items, 15)
    (11, [(2, 1), (6, 4), (1, 1), (2, 2)])
    """

    # Return the value of the most valuable subsequence of the first i
    # elements in items whose weights sum to no more than j.
    @memoized
    def bestvalue(i, j):
        if i == 0: return 0
        value, weight = items[i - 1]
        if weight > j:
            return bestvalue(i - 1, j)
        else:
            return max(bestvalue(i - 1, j),
                       bestvalue(i - 1, j - weight) + value)

    j = maxweight
    result = []
    for i in xrange(len(items), 0, -1):
        if bestvalue(i, j) != bestvalue(i - 1, j):
            result.append(items[i - 1])
            j -= items[i - 1][1]
    result.reverse()
    return bestvalue(len(items), maxweight), result

def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack(items, W)[0]