Problem:


Score : 800 points

Problem Statement

There are N stores called Store 1, Store 2, \cdots, Store N. Takahashi, who is at his house at time 0, is planning to visit some of these stores.

It takes Takahashi one unit of time to travel from his house to one of the stores, or between any two stores.

If Takahashi reaches Store i at time t, he can do shopping there after standing in a queue for a_i \times t + b_i units of time. (We assume that it takes no time other than waiting.)

All the stores close at time T + 0.5. If Takahashi is standing in a queue for some store then, he cannot do shopping there.

Takahashi does not do shopping more than once in the same store.

Find the maximum number of times he can do shopping before time T + 0.5.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

0 \leq a_i \leq 10^9

0 \leq b_i \leq 10^9

0 \leq T \leq 10^9

Input

Input is given from Standard Input in the following format:

N T
a_1 b_1
a_2 b_2
\vdots
a_N b_N

Output

Print the answer.

Sample Input 1

3 7
2 0
3 2
0 3

Sample Output 1

2

Here is one possible way to visit stores:

From time 0 to time 1: in 1 unit of time, he travels from his house to Store 1.

From time 1 to time 3: for 2 units of time, he stands in a queue for Store 1 to do shopping.

From time 3 to time 4: in 1 unit of time, he travels from Store 1 to Store 3.

From time 4 to time 7: for 3 units of time, he stands in a queue for Store 3 to do shopping.

In this way, he can do shopping twice before time 7.5.

Sample Input 2

1 3
0 3

Sample Output 2

0

Sample Input 3

5 21600
2 14
3 22
1 3
1 10
1 9

Sample Output 3

5

Sample Input 4

7 57
0 25
3 10
2 4
5 15
3 22
2 14
1 15

Sample Output 4

3



Sample input:
3 7
2 0
3 2
0 3


Sample output:
2

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, t = map(int, input().split())
shop = []
shop_0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shop_0.append((a, b))
        n -= 1
    else:
        shop.append((a, b))
shop.sort(key = lambda x: (x[0])/(1+x[1]), reverse = True)
shop0.sort(key = lambda x: x[1])

inf = 10**18
dp = [[inf for i in range(30)] for j in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(29):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + dp[i][j]*(shop[i][0])+shop[i][1]+1)



ans = 0
for i in range(30):
    tmp = i
    T = dp[n][i]
    if T > t:
        continue
    else:
        for j in range(len(shop_0)):
            if T+shop_0[j][1]+1 <= t:
                T += shop_0[j][1]+1
                tmp += 1
            else:
                break
    ans = max(tmp, ans)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import cmp_to_key
def cmp(store1, store2):
    if store1 == store2:
        return 0
    a1, b1 = store1
    a2, b2 = store2
    return -1 if a2 * (b1 + 1) <= a1 * (b2 + 1) else 1

def resolve():
    n, T = map(int, input().split())
    assert n <= 3000
    AB = [tuple(map(int, input().split())) for _ in range(n)]
    AB.sort(key = cmp_to_key(cmp))

    # dp[i][j] : i まで見て j 個到達するまでに掛かる最短時間
    dp = [T + 1] * (n + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(n - 1, -1, -1):
            t = dp[i]
            dp[i + 1] = min(dp[i + 1], (a + 1) * (t + 1) + b)

    for i in range(n, -1, -1):
        if dp[i] <= T:
            print(i)
            return
resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import cmp_to_key
def cmp(store1, store2):
    if store1 == store2:
        return 0
    a1, b1 = store1
    a2, b2 = store2
    return -1 if a2 * b1 <= a1 * b2 else 1

def resolve():
    n, T = map(int, input().split())
    assert n <= 3000
    AB = [tuple(map(int, input().split())) for _ in range(n)]
    AB.sort(key = cmp_to_key(cmp))

    # dp[i][j] : i まで見て j 個到達するまでに掛かる最短時間
    dp = [T + 1] * (n + 1)
    dp[0] = 0
    for a, b in AB:
        for i in range(n - 1, -1, -1):
            t = dp[i]
            dp[i + 1] = min(dp[i + 1], (a + 1) * (t + 1) + b)
        # print(a, b, dp)

    for i in range(n, -1, -1):
        if dp[i] <= T:
            print(i)
            return
resolve()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
import sys
sys.setrecursionlimit(10 ** 9)

N, T = list(map(int, input().split()))
arr = [[0,0]]+ [list(map(int, input().split())) for _ in range(N)]
arr= np.array(arr)

ab_arr = arr[1:,0] / ((arr)[1:,1]+1)


perm = np.array([0] + list(np.array(ab_arr).argsort()[::-1]+1))
dp = (np.zeros((N+1, min(N+1, int(np.log2(T))+2)))).astype(np.float32)
dp[1, 1] = arr[perm[1], 0] * 1 + arr[perm[1], 1] + 1
pos = int(np.log2(T))
for j in range(1, pos+2):
    tmp = np.minimum((dp[j-1:-1, j-1] + 1) * (arr[perm[j:], 0] + 1) + arr[perm[j:], 1], 10 ** 9 + 1)
    dp[j:,j] = np.minimum.accumulate(tmp)

dp = np.array(dp)
arr = np.array(arr)
b = np.sort(arr[arr[:,0] == 0, 1])
t = np.max(dp[N, dp[N,:] < T + 0.5])
n_stores = (dp[N, 1:] < T + 0.5).sum()
i = 1
for b_ in b[1:]:
    _t = t
    t += b_ + 1
    n_stores += 1
    if t > T + 0.5:
        t = _t
        n_stores -= 1
        break
print(n_stores)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
N, T = list(map(int, input().split()))
arr = [[0,0]]+ [list(map(int, input().split())) for _ in range(N)]
arr= np.array(arr)

ab_arr = arr[1:,0] / ((arr)[1:,1]+1)

perm = [0] + list(np.array(ab_arr).argsort()[::-1]+1)

dp = (np.zeros((N+1, min(N+1, int(np.log2(T))+1)))).astype(np.int64)
dp[1, 1] = arr[perm[1], 0] * 1 + arr[perm[1], 1] + 1
pos = int(np.log2(T))
for i in range(2,N+1):
    if i <= pos:
        dp[i,i] = dp[i-1, i-1] + (dp[i-1, i-1] + 1) * arr[perm[i], 0] + arr[perm[i], 1]
    tmp = np.minimum(dp[i - 1, 1: min(i, pos + 1)],
                     dp[i - 1, 0: min(i-1, pos)] + (dp[i - 1, 0: min(i-1, pos)]) * arr[perm[i]][0] + arr[perm[i]][1])
    dp[i,1:min(i,int(np.log2(T))+1)] = np.minimum(tmp, 10**9+1)

dp = np.array(dp)
arr = np.array(arr)
b = np.sort(arr[arr[:,0] == 0, 1])
t = np.max(dp[N, dp[N,:] < T + 0.5])
n_stores = (dp[N, 1:] < T + 0.5).sum()
i = 1
for b_ in b[1:]:
    _t = t
    t += b_ + 1
    n_stores += 1
    if t > T + 0.5:
        t = _t
        n_stores -= 1
        break
print(n_stores)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
N, T = list(map(int, input().split()))
arr = [[0,0]]+ [list(map(int, input().split())) for _ in range(N)]
arr= np.array(arr)
ab_arr = arr[1:,0] / (arr[1:,1]+1)

perm = [0] + list(ab_arr.argsort()[::-1]+1)
dp = np.zeros((N+1, min(N+1, int(np.log2(T))+1)))
dp[1,1] = arr[perm[1], 0] * 1 + arr[perm[1], 1] + 1

for i in range(2,N+1):
    for j in range(1, min(i+1,int(np.log2(T))+1)):
        if i == j:
            tmp = dp[i - 1, j - 1] + (dp[i - 1, j - 1] + 1) * arr[perm[i], 0] + arr[perm[i], 1]
            if tmp < 0:
                dp[i, j] = 10 ** 9
            else:
                dp[i, j] = tmp
        else:
            tmp1 = dp[i-1, j]
            tmp2 = dp[i-1, j-1] + (dp[i-1, j-1] + 1) * arr[perm[i], 0] + arr[perm[i], 1]
            if tmp1 < 0:
                tmp1 = 10 ** 9
            if tmp2 < 0:
                tmp2 = 10 ** 9
            dp[i,j] = np.min([10**9,tmp1, tmp2])

b = np.sort(arr[arr[:,0] == 0, 1])
t = np.max(dp[N, dp[N,:] < T + 0.5])
n_stores = (dp[N, 1:] < T + 0.5).sum()
i = 1
for b_ in b[1:]:
    _t = t
    t += b_ + 1
    n_stores += 1
    if t > T + 0.5:
        t = _t
        n_stores -= 1
        break
print(n_stores)

Submission status: Runtime Error

Solution code:
# coding: utf-8

import numpy as np
N, T = list(map(int, input().split()))
arr = [[0,0]]+ [list(map(int, input().split())) for _ in range(N)]
arr= np.array(arr).astype(np.int64)

ab_arr = arr[1:,0] / (arr[1:,1]+1)

perm = [0] + list(ab_arr.argsort()[::-1]+1)
dp = np.zeros((N+1, int(np.log2(T))+1)).astype(np.int64)
dp[1,1] = arr[perm[1], 0] * 1 + arr[perm[1], 1] + 1

for i in range(2,N+1):
    for j in range(1, min(i+1,int(np.log2(T))+1)):
        if i == j:
            dp[i, j] = min(10**9, dp[i - 1, j - 1] + (dp[i - 1, j - 1] + 1) * arr[perm[i], 0] + arr[perm[i], 1])
        else:
            dp[i,j] = np.min([10**9, dp[i-1, j],
                             dp[i-1, j-1] + (dp[i-1, j-1] + 1) * arr[perm[i], 0] + arr[perm[i], 1]])
b = np.sort(arr[arr[:,0] == 0, 1])
t = np.max(dp[N, dp[N,:] < T + 0.5])
n_stores = (dp[N, 1:int(np.log2(T))+1] < T + 0.5).sum()
i = 1
for b_ in b[1:]:
    _t = t
    t += b_ + 1
    n_stores += 1
    if t > T + 0.5:
        t = _t
        n_stores -= 1
        break
print(n_stores)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
N, T = list(map(int, input().split()))
arr = [[0,0]]+ [list(map(int, input().split())) for _ in range(N)]
arr= np.array(arr)

ab_arr = arr[1:,0] / (arr[1:,1]+1)

perm = [0] + list(ab_arr.argsort()[::-1]+1)

dp = np.zeros((N+1, N+1))
dp[1,1] = arr[perm[1], 0] * 1 + arr[perm[1], 1] + 1

for i in range(2,N+1):
    for j in range(1, min(i+1,int(np.log2(T))+1)):
        if i == j:
            dp[i, j] = dp[i - 1, j - 1] + (dp[i - 1, j - 1] + 1) * arr[perm[i], 0] + arr[perm[i], 1]
        else:
            dp[i,j] = np.min([dp[i-1, j],
                             dp[i-1, j-1] + (dp[i-1, j-1] + 1) * arr[perm[i], 0] + arr[perm[i], 1]])
b = np.sort(arr[arr[:,0] == 0, 1])
t = np.max(dp[N, dp[N,:] < T + 0.5])
n_stores = (dp[N, 1:int(np.log2(T))+1] < T + 0.5).sum()
i = 1
for b_ in b[1:]:
    _t = t
    t += b_ + 1
    n_stores += 1
    if t > T + 0.5:
        t = _t
        n_stores -= 1
        break
print(n_stores)

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split())
a=[]
b=[]
t=0
s=0
for _ in range(N):
	ai,bi=map(int,input().split())
    a.append(ai)
	b.append(bi)
    
while t<T+0.5 and len(a)>0:
	t=t+1
	q=9**99
	for i in range(len(a)):
		if t*a[i]+b[i]<q:
			q=t*a[i]+b[i]
			m=i
	a[m]=T
	t+=q
	if t<T+0.5:
		s=s+1
print(s)

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split())
a=[]
b=[]
t=0
s=0
for _ in range(N):
	ai,bi=map(int,input().split())	
    a.append(ai)
	b.append(bi)
    
while t<T+0.5 and len(a)>0:
	t=t+1
	q=9**99
	for i in range(len(a)):
		if t*a[i]+b[i]<q:
			q=t*a[i]+b[i]
			m=i
	a[m]=T
	t+=q
	if t<T+0.5:
		s=s+1
print(s)

Submission status: Runtime Error

Solution code:
N,T=map(int,input().split())
a=[]
b=[]
t=0
s=0
for _ in range(N):
	ai,bi=map(int,input().split())	a.append(ai)
	b.append(bi)
while t<T+0.5 and len(a)>0:
	t=t+1
	q=9**99
	for i in range(len(a)):
		if t*a[i]+b[i]<q:
			q=t*a[i]+b[i]
			m=i
	a[m]=T
	t+=q
	if t<T+0.5:
		s=s+1
print(s)

Submission status: Runtime Error

Solution code:
n,t = map(int,input().split())
shop_list = [list(map(int,input().split())) for _ in range(n)]

# aが大きい店は先に行った方がお得
shop_list.sort(reverse=True)

def solve(time,shop_idx):
    if len(shop_list) == shop_idx:
        return 0
    next_shop = shop_list[shop_idx]
    if next_shop[0]*time+next_shop[1]+time > t:
        return solve(time,shop_idx+1)
    else:
        return max(solve(time+1+next_shop[0]*time+next_shop[1],shop_idx+1)+1,solve(time,shop_idx+1))

print(solve(1,0))

Submission status: Runtime Error

Solution code:
n,t = map(int,input().split())
shop_list = [list(map(int,input().split())) for _ in range(n)]

# aが大きい店は先に行った方がお得
shop_list.sort(reverse=True)

def solve(time,shop_idx):
    if len(shop_list) == shop_idx:
        return 0
    next_shop = shop_list[shop_idx]
    if next_shop[0]*time+next_shop[1] > t-time-1:
        return solve(time,shop_idx+1)
    else:
        return max(solve(time+1+next_shop[0]*time+next_shop[1],shop_idx+1)+1,solve(time,shop_idx+1))

print(solve(0,0))

Submission status: Runtime Error

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 解説

N, T = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)

# 移動時間を考えなくて良いようにする
A += 1
B += 1
T += 1

# 使う店を決めたとき、(a - 1) / b の大きい順に使うのが最適
I = np.argsort((A - 1) / B)[::-1]
A = A[I]
B = B[I]

idx_zero = np.searchsorted((A == 1).astype(int), 1, side='left')
MAX_COUNT = 1 << ((2 * 10 ** 5).bit_length() + 2)
# dp[i][x]: i まで見て、x こ使うときの t の最小値
dp = np.full((idx_zero + 1, MAX_COUNT), IINF, dtype=int)
dp[0, 0] = 1
for i in range(len(dp) - 1):
    dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
    dp[i + 1, 1:] = np.minimum(dp[i + 1, 1:], dp[i, :-1] * A[i] + B[i])
    np.minimum(dp[i + 1], T + 1, out=dp[i + 1])

#: :type: list of int
B_A0 = np.msort(B[idx_zero:]).tolist()
ans = 0
# idx_zero 以降で、B を小さい順に使えるだけ使う
for cnt, t in enumerate(dp[idx_zero].tolist()):
    if t > T:
        break
    i = 0
    while i < len(B_A0) and t + B_A0[i] <= T:
        t += B_A0[i]
        i += 1
        cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 解説

N, T = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)

# 移動時間を考えなくて良いようにする
A += 1
B += 1
T += 1

# 使う店を決めたとき、(a - 1) / b の大きい順に使うのが最適
I = np.argsort((A - 1) / B)[::-1]
A = A[I]
B = B[I]

idx_zero = np.searchsorted((A == 1).astype(int), 1, side='left')
MAX_COUNT = 1 << ((2 * 10 ** 5).bit_length() + 2)
# dp[i][x]: i まで見て、x こ使うときの t の最小値
dp = np.full((idx_zero + 1, MAX_COUNT), IINF, dtype=int)
dp[0, 0] = 1
for i in range(len(dp) - 1):
    dp[i + 1, :] = np.minimum(dp[i + 1, :], dp[i, :])
    dp[i + 1, 1:] = np.minimum(dp[i + 1, 1:], dp[i, :-1] * A[i] + B[i])

#: :type: list of int
B_A0 = np.msort(B[idx_zero:]).tolist()
ans = 0
# idx_zero 以降で、B を小さい順に使えるだけ使う
for cnt, t in enumerate(dp[idx_zero].tolist()):
    if t > T:
        break
    i = 0
    while i < len(B_A0) and t + B_A0[i] <= T:
        t += B_A0[i]
        i += 1
        cnt += 1
    ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import sys
input = sys.stdin.readline
 
n,t = map(int,input().split())
l_a0 = []
l_a1 = []
 
for i in range(n):
    tmp = list(map(int,input().split()))
    if tmp[0] == 0:
        l_a0.append(tmp[1]+1)
    else:
        l_a1.append(tmp)
 
l_a0.sort()
l_a1.sort(reverse=True, key=lambda x: x[0]/(x[1]+1))

dp = [t*10] * 30 
dp[0] = 0

for a, b in l_a1:
        for num in range(30, -1, -1):
            candidate = (dp[num]+1) * (a+1) + b
            if candidate < dp[num+1]:
                dp[num+1] = candidate
dp = [i for i in dp if i <= t]

ans = [0]
for i in range(len(dp)):
    spendtime = dp[i]
    tmp = i
    for j in range(len(l_a0)):
        if spendtime + l_a0[j] <= t:
            spendtime += l_a0[j]
            tmp += 1
        else:
            break
    ans.append(tmp)
    
print(max(ans))

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
import sys
input = sys.stdin.readline
 
n,t = map(int,input().split())
l_a0 = []
l_a1 = []
 
for i in range(n):
    tmp = list(map(int,input().split()))
    if tmp[0] == 0:
        l_a0.append(tmp[1]+1)
    else:
        l_a1.append(tmp)
 
l_a0.sort()
l_a1.sort(reverse=True, key=lambda x: x[0]/(x[1]+1))

dp = [t*10] * 30 
dp[0] = 0

for a, b in l_a1:
        for num in range(28, -1, -1):
            candidate = (dp[num]+1) * (a+1) + b
            if candidate < dp[num+1]:
                dp[num+1] = candidate
dp = [i for i in dp if i <= t]

ans = [0]
for i in range(len(dp)):
    spendtime = dp[i]
    tmp = i
    for j in range(len(l_a0)):
        if spendtime + l_a0[j] <= t:
            spendtime += l_a0[j]
            tmp += 1
        else:
            break
    ans.append(tmp)
    
print(max(ans))

Submission status: Runtime Error

Solution code:
for a, b in shops:
        for num in range(28, -1, -1):
            candidate = (DP[num]+1) * (a+1) + b
            if candidate < DP[num+1]:
                DP[num+1] = candidate

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 31)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    # input
    N, T = map(int, input().split())
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = map(int, input().split())
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(range(L), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = min(L + 1, 29)
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[N][i] == float('inf'):
            break
        else:
            time_cnt = dp[N][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + t_b <= T:
                    time_cnt += t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    # input
    N, T = map(int, input().split())
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = map(int, input().split())
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(range(L), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = 29
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[N][i] == float('inf'):
            break
        else:
            time_cnt = dp[N][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + t_b <= T:
                    time_cnt += t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [t+1]*30
dp[0] = 0

for i in range(n):
    for j in range(30):
        dp[j] = min(dp[j], dp[j-1] + 1 +
                    shop[i][0]*(dp[j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(n+1):
    if t - dp[i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[i]) + i)

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[10**10]*30 for _ in range(n+1)]
dp[0][0] = 0


for j in range(30):
    for i in range(n):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(n+1):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[10**10]*50 for _ in range(n+1)]
dp[0][0] = 0


for j in range(min(n+1, 50)):
    for i in range(n):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(n+1):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = (a + 1) * dp[j] + b + 1
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

k = len(constant) - 1
for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    while const_acc[k] <= remaining:
        k -= 1
    ans = max(ans, i + k + 1)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b + 1))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = a * dp[j] + b
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    k = bisect(const_acc, remaining)
    ans = max(ans, i + k)

print(ans)

Submission status: Runtime Error

Solution code:
#!/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)

Submission status: Runtime Error

Solution code:
#!/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()

Submission status: Runtime Error

Solution code:
#!/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()

Submission status: Runtime Error

Solution code:
#!/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()

Submission status: Runtime Error

Solution code:
#!/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()