Problem p02750 (python)

Fixed submission:
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)

n, t = map(int, sys.stdin.readline().split())

nzshops = []
zshops = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    (zshops if a == 0 else nzshops).append((a, b))

nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
zshops.sort()

dp = [0]
for i in range(len(nzshops)):
    a, b = nzshops[i]
    dp.append(INF)
    for c in range(len(dp) - 1, 0, -1):
        x = dp[c - 1] + 1
        dp[c] = min(dp[c], x + x * a + b)
    for x in reversed(dp):
        if x < t:
            break
        dp.pop()

rs = list(itertools.accumulate(1 + b for _, b in zshops))
ans = max(c + bisect.bisect(rs, t - dp[c])
        for c in range(len(dp)) if dp[c] <= t)

print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    nnz = sum(1 for _ in itertools.takewhile(lambda x: x[0] > 0, shops))

    dp = [[0] + [INF] * int(math.log2(T_MAX)) for _ in range(nnz + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = shops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in shops[nnz:]))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)
    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
import itertools

def required_visit_time(t, shop):
    a, b = shop
    return int((t - b) / (a + 1)) - 1

# shops はソート済み
def calc_dp_time(T, shops):
    t = T
    for s in shops:
        t = required_visit_time(t, s)
    return t

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    dpmemo = None

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in dpmemo:
            return dpmemo[i, t]

        h = i - 1
        r = required_visit_time(t, shops[h])
        n = max(dp(h, r) + 1, dp(h, t)) if r >= 0 else dp(h, t)
        dpmemo[i, t] = n
        return n

    dpmax = sum(1 for _ in itertools.takewhile(lambda x: x[0] > 0, shops))

    # dp(dpmax, t) | t = T と同じ値を得られる最小の t を二分探索
    dpmemo = {}
    ans = dp(dpmax, T)
    l = 0
    r = T + 1
    while l + 1 < r:
        m = int((l + r) / 2)
        dpmemo = {}
        n = dp(dpmax, m)
        if n < ans:
            l = m
        else:
            r = m

    t = r
    for i in range(dpmax, N):
        _, b = shops[i]
        t += 1 + b
        if t > T:
            break
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
import itertools

def required_visit_time(t, shop):
    a, b = shop
    return int((t - b) / (a + 1)) - 1

# shops はソート済み
def calc_dp_time(T, shops):
    t = T
    for s in shops:
        t = required_visit_time(t, s)
    return t

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    dpmemo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in dpmemo:
            return dpmemo[i, t]

        h = i - 1
        r = required_visit_time(t, shops[h])
        n = max(dp(h, r) + 1, dp(h, t)) if r >= 0 else dp(h, t)
        dpmemo[i, t] = n
        return n

    dpmax = sum(1 for _ in itertools.takewhile(lambda x: x[0] > 0, shops))

    # dp(dpmax, t) | t = T と同じ値を得られる最小の t を二分探索
    ans = dp(dpmax, T)
    l = 0
    r = T + 1
    while l + 1 < r:
        m = int((l + r) / 2)
        n = dp(dpmax, m)
        if n < ans:
            l = m
        else:
            r = m

    t = r
    for i in range(dpmax, N):
        _, b = shops[i]
        t += 1 + b
        if t > T:
            break
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
import itertools

def required_visit_time(t, shop):
    a, b = shop
    return int((t - b) / (a + 1)) - 1

# shops はソート済み
def calc_dp_time(T, shops):
    t = T
    for s in shops:
        t = required_visit_time(t, s)
    return t

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    dpmemo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in dpmemo:
            return dpmemo[i, t]

        h = i - 1
        r = required_visit_time(t, shops[h])
        n = max(dp(h, r) + 1, dp(h, t)) if r >= 0 else dp(h, t)
        dpmemo[i, t] = n
        return n

    #
    # 解に含まれ得る a=0 要素を二分探索
    #
    dpmax = sum(1 for _ in itertools.takewhile(lambda x: x[0] > 0, shops))
    l = dpmax
    r = N + 1
    while l + 1 < r:
        m = int((l + r) / 2)
        if calc_dp_time(T, shops[dpmax:m]) < 0:
            r = m
        else:
            l = m

    ans = 0
    for i in range(l, dpmax - 1, -1):
        t = calc_dp_time(T, shops[dpmax:i])
        n = dp(dpmax, t) + (i - dpmax)
        if n <= ans:
            break
        ans = n

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    memo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in memo:
            return memo[i, t]

        h = i - 1
        s = int((t - shops[h][1]) / (shops[h][0] + 1)) - 1
        x = max(dp(h, s) + 1, dp(h, t)) if s >= 0 else dp(h, t)
        memo[i, t] = x
        return x

    print(dp(N, T))
    #print(sorted(memo.items()))

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
import math
import itertools


def main():
    N, T = map(int, sys.stdin.readline().split())
    As, Bs = map(list, zip(*(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))))

    # dp[i + 1][t] := i番目までの店のうち時間 t を超えないように訪問できる店の数
    # dp[i + 1][t] | int((t - Bs[i]) / As[i]) - 1 >= 0 = max(dp[i][int((t - Bs[i]) / As[i]) - 1] + 1, dp[i][t])
    #              | otherwise                         = dp[i][t]

    memo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in memo:
            return memo[i, t]

        h = i - 1

        tpre = int((t - Bs[h]) / (As[h] + 1)) - 1
        if tpre >= 0:
            x = memo[i, t] = max(dp(h, tpre) + 1, dp(h, t))
            return x
        else:
            x = memo[i, t] = dp(h, t)
            return dp(h, t)

    print(dp(N, T))
    #print(memo)

if __name__ == '__main__':
    main()