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: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/hitachi2020/submissions/10704509

def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a / (b + 1), a, b))  # namedtupleやめた,sort_key,coef,const

    ps.sort(key=itemgetter(0), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for _, coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = {0}
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: continue  # le->lt
        while cnt > 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        ans.add(visited + cnt)
    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a / (b + 1), a, b))  # namedtupleやめた,sort_key,coef,const

    ps.sort(key=itemgetter(0), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for _, coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = max(k for k in range(L + 1) if dp[k] <= T)
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: continue  # le->lt
        while cnt >= 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        if cnt == 0:
            break  # 途中で離脱するようにした
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  # namedtupleやめた,coef,const

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = max(k for k in range(L + 1) if dp[k] <= T)
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: continue  # le->lt
        while cnt >= 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        if cnt == 0:
            break  # 途中で離脱するようにした
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  # namedtupleやめた,coef,const

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = -1
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: continue  # le->lt
        while cnt >= 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import namedtuple
    import sys
    input = sys.stdin.readline

    Param = namedtuple('Param', 'coef const')

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append(Param(coef=a, const=b))

    ps.sort(key=lambda p: p.coef / (p.const + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for p in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (p.coef + 1) + p.const
            )
            # dp[visited] + 1 + (dp[visited] + 1) * p.coef + p.const

    def accumulate(a):
        s = 0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = -1
    cur = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: continue  # le->lt
        while cur >= 0 and acc[cur] > rest:  # bisect_right->しゃくとり
            cur -= 1
        cnt = cur + 1
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_right
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Param = namedtuple('Param', 'coef const')

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        p = Param(coef=a, const=b)
        if a == 0:
            coef_0.append(p)
        else:
            ps.append(p)

    ps.sort(key=lambda p: p.coef / (p.const + 1), reverse=True)
    coef_0.sort(key=attrgetter('const'))

    dp = [inf] * (L + 1)
    dp[0] = 0
    for p in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                dp[visited] + 1 + (dp[visited] + 1) * p.coef + p.const
            )

    def accumulate(a):
        s = 0
        for x in a:
            s += x.const + 1
            yield s

    *acc, = accumulate(coef_0)

    ans = -1
    for visited in range(L + 1):
        rest = T - dp[visited]
        if rest < 0: continue  # le->lt
        cnt = bisect_right(acc, rest)
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
N,T = 20000, 10 ** 9
arr = np.random.randint(0, 10 ** 3, size = (N+1,2)).astype(np.int32)

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

perm = [0] + list(ab_arr.argsort()[::-1]+1)
perm[20000]
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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
DP[0][0]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(29):
    for j in range(k):
        for l in range(j+1,k+1):
            nt=nexttime(DP[i][j],M[l-1][0],M[l-1][1])
            if nt<DP[i+1][l]:
                DP[i+1][l]=nt
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
DP[0][0]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(1,30):
    for j in range(k+1):
        a,b=M[j-1]
        for l in range(j):
            nt=nexttime(DP[i-1][l],a,b)
            if nt<DP[i][j]:
                DP[i][j]=nt
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)

Submission status: Time Limit Exceeded

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 = (10 ** 9).bit_length() + 2
# dp[i][x]: i まで見て、x こ使うときの t の最小値
dp = np.full((idx_zero + 1, MAX_COUNT), IINF, dtype=int)
dp[:, 0] = 1
for x in range(MAX_COUNT - 1):
    dp[1:, x + 1] = dp[:-1, x] * A[:idx_zero] + B[:idx_zero]
    dp[:, x + 1] = np.minimum.accumulate(dp[:, x + 1])
    dp[:, x + 1] = np.minimum(dp[:, x + 1], T + 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: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right

N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
#%%
b0 = []
ab1 = []
for a,b in ab:
    if a==0:
        b0.append(b+1)
    else:
        ab1.append([a/(b+1), a, b+1])

N0 = len(b0)
N1 = len(ab1)

b0.sort()
if N0>0:
    b_ruiseki = [0]*N0
    b_ruiseki[0] = b0[0]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

ab1.sort(reverse = True)

INF = T + 100

dp = [[INF]*31 for _ in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    # dp[i+1][j] : 0~i番目までの店を見て，j個選ぶときの最小時間
    
    for j in range(31):
        if j>i+1:break
        if j==0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-1] + (dp[i][j-1]+1)*ab1[i][1]+ab1[i][2])

for j in range(31):
    if dp[N1][j]>T:break    
    # a>0をj店舗めぐった後にa=0を何店舗めぐれるか
    num0 = bisect_right(b_ruiseki, T - dp[N1][j])
    ans = max(ans, j + num0)
        
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [0] + [float('inf')] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [float('inf')] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""
AB.sort(key=lambda x: (-x[0], x[1]))

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append((a, b))
a0.sort()

nab.sort(key=lambda x: ((x[1] + 1) / x[0]))

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [0] + [float('inf')] * 29
for index, (a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [float('inf')] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                                   dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""
AB.sort(key=lambda x: (-x[0], x[1]))

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append((a, b))
a0.sort()

nab.sort(key=lambda x: ((x[1] + 1) / x[0]))

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [[0] + [float('inf')] * 29 for _ in range(len(nab) + 1)]
for index, (a, b) in enumerate(nab):
    # print(a, b)
    for count in range(1, 29):
        dp[index + 1][count] = min(dp[index][count],
                                   dp[index][count - 1] + 1 + (dp[index][count - 1] + 1) * a + b)

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp[-1]):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""
AB.sort(key=lambda x: (-x[0], x[1]))

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append((a, b))
a0.sort()

nab.sort(key=lambda x: ((x[1] + 1) / x[0]))

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [[0] + [float('inf')] * 30 for _ in range(len(nab) + 1)]
for index, (a, b) in enumerate(nab):
    # print(a, b)
    for count in range(1, 31):
        dp[index + 1][count] = min(dp[index][count],
                                   dp[index][count - 1] + 1 + (dp[index][count - 1] + 1) * a + b)

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp[-1]):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N, T = map(int, input().split())
a = np.array([0 for i in range(N)])
b = [0 for i in range(N)]
for i in range(N):
  a[i], b[i] = map(int, input().split())
idx_a = np.argsort(a)[::-1]
count_t = 0
count_max = 0
for a_list in itertools.permutations(idx_a):
  count_t = 0
  count_s = 0
  for i in a_list:
    if count_t + 1 > T + 0.5 or count_t + 1 + a[i]*(count_t + 1) + b[i] > T + 0.5:
      break
    count_t += 1
    count_t += a[i]*count_t + b[i]
    count_s += 1
    if count_s > count_max:
      count_max = count_s
print(count_max)

Submission status: Time Limit Exceeded

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(n+1)] for __ in range(30)]
dp[0][0] = 0

m = min(n+1, 30)

for j in range(m):
    for i in range(n):
        dp[j][i+1] = min(dp[j][i], dp[j-1][i] + 1 +
                         shop[i][0]*(dp[j-1][i]+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(m):
    if t - dp[i][n] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[i][n]) + i)

print(ans)

Submission status: Time Limit Exceeded

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[L][i] == float('inf'):
            break
        else:
            time_cnt = dp[L][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + 1 + t_b <= T:
                    time_cnt += 1 + t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    # input
    N, T = map(int, input().split())
    a, b = [0] * N, [0] * N
    for i in range(N):
        a[i], b[i] = map(int, input().split())

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

    # dp
    dp = [[float('inf') for _ in range(N + 2)] for _ in range(N + 1)]  # dp[for i shops][passed j shops] := min time
    dp[0][0] = 0
    for i in range(N):
        for j in range(N + 1):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T + 0.5:
                    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]

    # print answer
    for i in range(N + 1):
        if dp[N][i + 1] == float('inf'):
            print(i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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(30)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for j in range(m):
    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(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Submission status: Time Limit Exceeded

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(min(n+1, 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(min(n+1, 30)):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Submission status: Time Limit Exceeded

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(min(n+1, 50)):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Submission status: Time Limit Exceeded

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]*(n+1) 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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Store:
    def __init__(self,a,b):
        self.a=a
        self.b=b

    def __eq__(self, other):
        return (self.b+1)*other.a==self.a*(other.b+1)

    def __lt__(self, other):
        return (self.b+1)*other.a<self.a*(other.b+1)

    def __le__(self, other):
        return (self.b+1)*other.a<=self.a*(other.b+1)

    def __gt__(self, other):
        return (self.b+1)*other.a>self.a*(other.b+1)

    def __ge__(self, other):
        return (self.b+1)*other.a>=self.a*(other.b+1)

from itertools import accumulate
from bisect import bisect
def main():
    inf=10**9+7
    n,t=MI()
    ab=LLI(n)
    ss=[]
    a0=[]
    for a,b in ab:
        if a==0:a0.append(b+1)
        else:ss.append(Store(a,b))
    n=len(ss)
    ss.sort()
    dp=[[inf]*31 for _ in range(n+1)]
    dp[0][0]=0
    for i,s in enumerate(ss):
        a,b=s.a,s.b
        for j in range(30):
            pre=dp[i][j]
            if pre==inf:continue
            nt=a*(pre+1)+b+pre+1
            if nt<=t:dp[i+1][j+1]=min(dp[i+1][j+1],nt)
            dp[i+1][j]=min(dp[i+1][j],pre)
    a0.sort()
    a0=[b for b in accumulate(a0)]
    ans=0
    for j in range(30):
        val=dp[n][j]
        if val==inf:continue
        ans=max(ans,bisect(a0,t-dp[n][j])+j)
    print(ans)

main()

Submission status: Time Limit Exceeded

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 = [[float('inf')]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(min(i+2, 30)):
        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: Time Limit Exceeded

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 = [[float('inf')]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(min(i+2, 50)):
        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)