Problem p02750 (python)

Fixed submission:
INF = 10 ** 10
N = 100
n, T = map(int, raw_input().split())

stores = []
zs = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    if a == 0:
        zs.append(b)
    else:
        stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)
stores.append((INF, INF))
zs.sort()

m = len(zs)

for i in xrange(1, m):
    zs[i] += zs[i - 1]

dp = [ [INF for i in xrange(N)] for j in xrange(2) ]
dp[0][0] = 0
res = 0

n = len(stores)

p = 0
for i in xrange(n):
    q = p ^ 1
    dp[q] = [INF for j in xrange(N)]

    a, b = stores[i]
    for j in xrange(N):
        dp[q][j] = min(dp[q][j], dp[p][j])
        if dp[p][j] == -INF:
            continue
        if j + 1 < N:
            t = dp[p][j] + 1
            dp[q][j + 1] = min(dp[q][j + 1], dp[p][j] + 1 + a * t + b)
            if dp[q][j + 1] <= T:
                res = max(res, j + 1)
    for j in xrange(N):
        if dp[q][j] > T:
            continue
        rem = T - dp[q][j] - 1
        l, r = 0, m - 1
        while l <= r:
            mid = (l + r) / 2
            if zs[mid] + mid <= rem:
                res = max(res, j + mid + 1)
                l = mid + 1
            else:
                r = mid - 1
    p = q
print res

Buggy submission (verdict: Runtime Error):
INF = 10 ** 10
N = 100
n, T = map(int, raw_input().split())

stores = []
zs = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    if a == 0:
        zs.append(b)
    else:
        stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

dp = [ [INF for i in xrange(N)] for j in xrange(2) ]
dp[0][0] = 0
res = 0

p = 0
for i in xrange(n):
    q = p ^ 1
    dp[q] = [INF for j in xrange(N)]

    a, b = stores[i]
    for j in xrange(N):
        dp[q][j] = min(dp[q][j], dp[p][j])
        if dp[p][j] == -INF:
            continue
        if j + 1 < N:
            t = dp[p][j] + 1
            dp[q][j + 1] = min(dp[q][j + 1], dp[p][j] + 1 + a * t + b)
            if dp[q][j + 1] <= T:
                res = max(res, j + 1)
    p = q
print res

Buggy submission (verdict: Runtime Error):
INF = 10 ** 10
N = 33
n, T = map(int, raw_input().split())

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

dp = [ [INF for i in xrange(N)] for j in xrange(2) ]
dp[0][0] = 0

p = 0
for i in xrange(n):
    q = p ^ 1
    dp[q] = [INF for j in xrange(N)]

    a, b = stores[i]
    for j in xrange(N):
        dp[q][j] = min(dp[q][j], dp[p][j])
        if dp[p][j] == -INF:
            continue
        if j + 1 < N:
            t = dp[p][j] + 1
            dp[q][j + 1] = min(dp[q][j + 1], dp[p][j] + 1 + a * t + b)
            if dp[q][j + 1] <= T:
                res = j + 1
    p = q
print res

Buggy submission (verdict: Runtime Error):
INF = 10 ** 10
n, t = map(int, raw_input().split())

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

dp = [ [INF for i in xrange(30)] for j in xrange(2) ]
dp[0][0] = 0

p = 0
for i in xrange(n):
    q = p ^ 1
    dp[q] = [INF for i in xrange(30)]

    a, b = stores[i]
    for j in xrange(30):
        dp[q][j] = dp[p][j]
        if dp[p][j] == -INF:
            continue
        if j + 1 < 30:
            t = dp[p][j] + 1
            dp[q][j + 1] = min(dp[q][j + 1], dp[p][j] + 1 + a * t + b)
            if dp[q][j + 1] <= t:
                res = j + 1
    p = q
print res

Buggy submission (verdict: Runtime Error):
INF = 10 ** 10
n, t = map(int, raw_input().split())

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

def multi(s1, s2):
    a1, b1 = s1
    a2, b2 = s2

    a3 = a1 + a2 + a1 * a2
    b3 = b1 + 1 + a2 * b1 + a2 + b2

    a3 = min(INF, a3)
    b3 = min(INF, b3)
    return (a3, b3)

rev = stores[:]
for i in xrange(n - 2, -1, -1):
    rev[i] = multi(rev[i], rev[i + 1])

cnt = 0
tick = 1
ptr = 0
qtr = 0
res = 0
while tick <= t and ptr < n:
    qtr = max(qtr, ptr)
    while True:
        (a, b) = rev[qtr]
        u = a * tick + b
        if tick + u <= t:
            res = max(res, ptr + n - qtr)
            break
        else:
            qtr += 1

    (a, b) = stores[ptr]
    #print (a, b)
    ptr += 1

    tt = a * tick + b
    if tick + tt > t:
        break
    tick += tt + 1
    #print tick, t, a, b, ptr, n
print res

Buggy submission (verdict: Runtime Error):
n, t = map(int, raw_input().split())

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

def multi(s1, s2):
    a1, b1 = s1
    a2, b2 = s2

    a3 = a1 + a2 + a1 * a2
    b3 = b1 + 1 + a2 * b1 + a2 + b2
    return (a3, b3)

rev = stores[:]
for i in xrange(n - 2, -1, -1):
    rev[i] = multi(rev[i], rev[i + 1])

cnt = 0
tick = 1
ptr = 0
res = 0
while tick <= t and ptr < n:
    l, r = ptr, n
    while l <= r:
        m = (l + r) >> 1
        (a, b) = rev[m]
        u = a * tick + b
        #print tick, u, tick + u
        if tick + u <= t:
            res = max(res, ptr + n - m)
            r = m - 1
        else:
            l = m + 1

    (a, b) = stores[ptr]
    #print (a, b)
    ptr += 1

    tt = a * tick + b
    if tick + tt > t:
        break
    tick += tt + 1
    #print tick, t, a, b, ptr, n
print res