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: Wrong Answer

Solution code:
from operator import itemgetter
import bisect


n, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
INF = t + 1
LIMIT = 60

# mrkt_a0: a == 0 の店
# mrkt_others: a != 0 の店
mrkt_a0 = []
mrkt_others = []

for i in range(n):
    a, b = info[i]
    if a == 0:
        mrkt_a0.append((a, b))
    else:
        comp = 1 / (1 + b)
        mrkt_others.append((a, b, comp))

mrkt_a0.sort(key=itemgetter(1))
mrkt_others.sort(key=itemgetter(2), reverse=True)

# mrkt_a0について
# もしmarkt_a0を尋ねるなら尋ねるのを後回しにしたほうが良い
times_a0 = [0]
for a, b in mrkt_a0:
    times_a0.append(times_a0[-1] + 1 + b)

# mrkt_othersについて
len_others = len(mrkt_others)
dp = [[INF] * LIMIT for i in range(len_others + 1)]
dp[0][0] = 0

for i in range(len_others):
    a, b, _ = mrkt_others[i]
    for cnt in range(LIMIT):
        # i番目の店を尋ねないとき
        dp[i + 1][cnt] = min(dp[i][cnt], dp[i + 1][cnt])
        # i番目の店を尋ねるとき
        if cnt + 1 < LIMIT:
            dp[i + 1][cnt + 1] = min(a * (dp[i][cnt] + 1) + b + dp[i][cnt] + 1, dp[i + 1][cnt + 1])

ans = 0
for cnt in range(LIMIT):
    if dp[-1][cnt] == t + 1:
        continue
    nokori = t - dp[-1][cnt]
    cnt_a0 = bisect.bisect_right(times_a0, nokori) - 1
    ans = max(ans, cnt + cnt_a0)
print(ans)

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
shop=[]
easyshop=[]
for i in range(N):
    a,b=map(int,input().split())
    A,B=a+1,a+b+1
    if A==1:
        easyshop.append(B)
    else:
        shop.append(((A-1)/B,A,B))

shop.sort(reverse=True)
easyshop.sort()

if shop:
    dp=[0,shop[0][2]]
    for i in range(1,len(shop)):
        ndp=[]
        val,A,B=shop[i]
        for j in range(len(dp)):
            t=min(A*dp[j-1]+B,dp[j])
            if T>=t:
                ndp.append(t)
            else:
                break
        else:
            t=A*dp[-1]+B
            if T>=t:
                ndp.append(t)
        dp=ndp

    import bisect
    id=bisect.bisect_right(dp,T)
    ans=id-1
    if not easyshop:
        print(ans)
    else:
        n=len(easyshop)
        for i in range(1,n):
            easyshop[i]+=easyshop[i-1]
        for i in range(n):
            id=bisect.bisect_right(dp,T-easyshop[i])
            ans=max(ans,id+i)
        print(ans)
else:
    import bisect
    n=len(easyshop)
    for i in range(1,n):
        easyshop[i]+=easyshop[i-1]
    ans=bisect.bisect_right(easyshop,T)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
shop=[]
for i in range(N):
    a,b=map(int,input().split())
    A,B=a+1,a+b+1
    if B==1:
        shop.append((0,A,B))
    else:
        shop.append((A/(B-1),A,B))

shop.sort(reverse=True)

dp=[0,shop[0][2]]
for i in range(1,N):
    ndp=[]
    val,A,B=shop[i]
    for j in range(len(dp)):
        t=min(A*dp[j-1]+B,dp[j])
        if T>=t:
            ndp.append(t)
        else:
            break
    else:
        t=A*dp[-1]+B
        if T>=t:
            ndp.append(t)
    dp=ndp

for i in range(len(dp)-1,-1,-1):
    if T>=dp[i]:
        print(i)
        break

Submission status: Wrong Answer

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)
shop_0.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: Wrong Answer

Solution code:
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)
shop.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: Wrong Answer

Solution code:
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)
shop.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+1] = min(dp[i+1][j+1], dp[i][j] + dp[i][j]*(shop[i][0])+shop[i][1]+1)
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])


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: Wrong Answer

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())
    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], t + 1 + a * (t + 1) + b)
        # print(a, b, dp)

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

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab0 = []
ab1 = []
for i in range(n):
  if ab[i][0] == 0:
    ab0.append(ab[i])
  else:
    ab1.append(ab[i])
ab0.sort(key = lambda x:x[1])
ab1.sort(key = lambda x:x[0]/(x[1]+1),reverse=True)
n = len(ab1)
dp = [[10**10 for i in range(31)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0] = 0
for i in range(1,n+1):
  a,b = ab1[i-1]
  for j in range(1,31):
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1+a*(dp[i-1][j-1]+1)+b)
m = len(ab0)
ans = 0
for j in range(31):
  if dp[n][j] > t:
    continue
  tmp = j
  ttmp = t-dp[n][j]
  i = 0
  while i <= m-1 and ttmp >= ab[i][1]+1:
    ttmp -= ab[i][1]+1
    tmp += 1
    i += 1
  ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab0 = []
ab1 = []
for i in range(n):
  if ab[i][0] == 0:
    ab0.append(ab[i])
  else:
    ab1.append(ab[i])
ab0.sort(key = lambda x:x[1])
ab1.sort(key = lambda x:x[0]/(x[1]+1),reverse=True)
n = len(ab1)
dp = [[10**10 for i in range(31)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0] = 0
for i in range(1,n+1):
  a,b = ab1[i-1]
  for j in range(1,31):
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1+a*(dp[i-1][j-1]+1)+b)
m = len(ab0)
ans = 0
for j in range(31):
  if dp[n][j] > t:
    continue
  tmp = j
  ttmp = t-dp[n][j]
  i = 0
  while i <= m-1 and ttmp >= ab[i][1]:
    ttmp -= ab[i][1]+1
    tmp += 1
    i += 1
  ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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
        cnt = bisect_right(acc, rest)
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())

# Nは店舗数
# Tは閉店時刻

ab = [map(int, input().split()) for _ in range(N)]
a, b = [list(i) for i in zip(*ab)]

close_time = T + 0.5
shop = [0] * N

t = 0

for i in range(N):
  if t > close_time:
    break
      
  t += 1
  t += a[i] * t + b[i]
  shop[i] = 1
    
print(sum(shop))

Submission status: Wrong Answer

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)

time = 0
cur = 0
n_store = 0
hist = []
go = True
time_list = arr[:,1]
pre_time = 0
while go:
    if len(hist) == N:
        break
    time += 1
    time_list += arr[:,0] * (time - pre_time)
    tmp = np.argsort(time_list)
    i = 1
    while True:
        if tmp[i] in hist:
            i+=1
            continue
        else:
            hist.append(tmp[i])
            pre_time = time
            time += time_list[tmp[i]]

            if time >= T + 0.5:
                go = False
                break
            else:
                n_store += 1
                break

print(n_store)

Submission status: Wrong Answer

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)

time = 0
cur = 0
n_store = 0
hist = []
go = True
while go:
    if len(hist) == N:
        break
    time += 1
    time_list = arr[:,0] * time + arr[:,1]
    tmp = np.argsort(time_list)
    i = 1
    while True:
        if tmp[i] in hist:
            i+=1
            continue
        else:
            hist.append(tmp[i])
            time += time_list[tmp[i]]
            if time > T + 0.5:
                go = False
                break
            else:
                n_store += 1
                break

print(n_store)

Submission status: Wrong Answer

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+=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: Wrong Answer

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+=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: Wrong Answer

Solution code:
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
    if x==1:
        return (1<<16)+y
    else:
        return (y+1)/(x-1)

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: Wrong Answer

Solution code:
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
    if x==1:
        return (1<<16)+y
    else:
        return (y+1)/(x-1)

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

k=0
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: Wrong Answer

Solution code:
import sys
from bisect import bisect_right
 
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N)]

b0 = []
ab1 = []

#aが0とそれ以外で分ける
for a,b in ab:
    if a == 0:
        #+1は店間の移動を先に考慮
        b0.append(b+1)
    else:
        ab1.append([(b+1)/a, a, b])

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

b0.sort()

#bは累積和で時間計算可能（最後にどこまで足せるかを調べる）
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 = []
#探索範囲が28店まででいいからソートする
ab1.sort()

INF = T + 100
 
dp = [[INF]*31 for i 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]+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: Wrong Answer

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')
A1 = A[:idx_zero]
B1 = B[:idx_zero]
B2 = np.msort(B[idx_zero:])

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):
    next_col = dp[:-1, x] * A1 + B1
    np.minimum(next_col, T + 1, out=next_col)
    np.minimum.accumulate(next_col, out=next_col)
    dp[1:, x + 1] = next_col

# idx_zero 以降で、B を小さい順に使えるだけ使う
cum = B2.cumsum()
counts = np.searchsorted(cum, T - dp[idx_zero], side='right')
ans = counts + np.arange(dp.shape[1])
print(ans[dp[idx_zero] <= T].max())

# print(cum)
# print(dp[idx_zero])
# print(counts)

Submission status: Wrong Answer

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, 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: Wrong Answer

Solution code:
#input
N, T = map(int, input().split())
T += 0.5

AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split())))

# process
AB0 = [(a, b) for (a, b) in AB if a == 0]
AB1 = [(a, b) for (a, b) in AB if a != 0]
comp0 = [(b, i) for i, (a, b) in enumerate(AB0)]
comp1 = [(a/(b+1), i) for i, (a, b) in enumerate(AB1)]
comp0.sort()
comp1.sort(reverse=True)

t = 0
ans = 0
for i in range(len(AB1)):
    a, b = AB1[comp1[i][1]]
    pt = t
    t += 1
    t += a*t+b
    if t > T:
        t = pt
        break
    ans += 1

for i in range(len(AB0)):
    _, b = AB0[comp0[i][1]]
    t += 1+b
    if t > T:
        break
    ans += 1

# output
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def get_shortest_shop(t, shops):
    shortest_i = 0
    shortest_t = shops[0][0]*t + shops[0][1]

    for i, l in enumerate(shops):
        shop_t = l[0]*t + l[1]
        if shortest_t > shop_t:
            shortest_t = shop_t
            shortest_i = i
    
    return shortest_i, shortest_t


n, t_limit = map(int, input().split())
shops = []
for _ in range(n):
    shops.append(list(map(int, input().split())))

t = 1
shop_limit = 0
while t_limit > t:
    shortest_i, shortest_t = get_shortest_shop(t, shops)
    if t_limit >= t + shortest_t:
        t = t + shortest_t + 1
        del shops[shortest_i]
        shop_limit += 1
        if len(shops) == 0:
            break
    else:
        break

print(shop_limit)

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from itertools import product
def resolve():
    N, T = lr()
    ab = []
    a0b = []
    for i in range(N):
        a, b = lr()
        if a >= 1:
            ab.append([a, b])
        else:
            a0b.append(b)
    ab = sorted(ab, key=lambda x: x[0]/(x[1]+1))[::-1]
    a0b = sorted(a0b)
    dp = defaultdict(lambda: 10**9+1)
    dp[0, 0] = 0
    for i, j in product(range(len(ab)), range(min(i+2, 29))):
        dp[i+1, j] = min(dp[i, j-1]+ab[i][0]*dp[i, j-1]+ab[i][1]+1, dp[i, j])
    ans = 0
    for j in range(29):
        t = dp[len(ab), j]
        if t <= T+0.5:
            tmp = 0
            for k in range(len(a0b)):
                t += a0b[k]+1
                if t > T+0.5:
                    break
                tmp += 1
            ans = max(ans, j+tmp)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from itertools import product
def resolve():
    N, T = lr()
    ab = []
    a0b = []
    for i in range(N):
        a, b = lr()
        if a >= 1:
            ab.append([a, b])
        else:
            a0b.append(b)
    ab = sorted(ab, key=lambda x: x[0]/(x[1]+1))[::-1]
    a0b = sorted(a0b)
    dp = defaultdict(lambda: 10**9+1)
    dp[0, 0] = 1
    for i, j in product(range(len(ab)), range(min(i+2, 29))):
        dp[i+1, j] = min(dp[i, j-1]+ab[i][0]*dp[i, j-1]+ab[i][1]+1, dp[i, j])
    ans = 0
    for j in range(29):
        t = dp[len(ab), j]
        if t <= T+0.5:
            tmp = 0
            for k in range(len(a0b)):
                t += a0b[k]
                if t > T+0.5:
                    break
                tmp += 1
            ans = max(ans, j+tmp)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from itertools import product
def resolve():
    N, T = lr()
    ab = []
    a0b = []
    for i in range(N):
        a, b = lr()
        if a >= 1:
            ab.append([a, b])
        else:
            a0b.append(b)
    ab = sorted(ab, key=lambda x: x[0]/(x[1]+1))[::-1]
    a0b = sorted(a0b)
    dp = defaultdict(lambda: 10**9+1)
    dp[0, 0] = 1
    for i, j in product(range(len(ab)), range(max(i+1, 29))):
        dp[i+1, j] = min(dp[i, j-1]+ab[i][0]*dp[i, j-1]+ab[i][1]+1, dp[i, j])
    ans = 0
    for j in range(29):
        t = dp[len(ab), j]
        if t <= T+0.5:
            tmp = 0
            for k in range(len(a0b)):
                t += a0b[k]
                if t >= T+0.5:
                    break
                tmp += 1
            ans = max(ans, j+tmp)
    print(ans)
resolve()

Submission status: Wrong Answer

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]+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: Wrong Answer

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)
    else:
        ab1.append([a,b])

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

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

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

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]+1)*(ab1[i][0]+1)+ab1[i][1]+1)

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: Wrong Answer

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)
    else:
        ab1.append([a,b])

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

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

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

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]+1)*ab1[i][0]+ab1[i][1]+1)

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: Wrong Answer

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)
    else:
        ab1.append([a,b])

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

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

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

INF = T + 100

dp = [[INF]*50 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(50):
        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]+1)*ab1[i][0]+ab1[i][1]+1)

for j in range(50):
    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: Wrong Answer

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)
    else:
        ab1.append([a,b])

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

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

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

INF = 10**18+7

dp = [[INF]*50 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(50):
        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]+1)*ab1[i][0]+ab1[i][1]+1)
    
#%%
ans = 0
for j in range(50):
    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: Wrong Answer

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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

n, t_limit = map(int, input().split())
ab = []
bias = []
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        bias.append(b)
    else:
        ab.append((a, b))
bias.sort()
cumsum = [0]
for item in bias:
    cumsum.append(cumsum[-1] + item)

ab.sort()
t = 1
stack = 0
ans = 0
while t < t_limit:
    choise = -1
    nt = t_limit
    for i, (a, b) in enumerate(ab):
        if a*t + b <= nt: 
            choise = i
            nt = a*t + b
    if choise != -1:
        ab.remove(ab[choise])
        t = nt
        stack += 1
        additional = bisect.bisect_right(cumsum, t_limit - t) - 1
        ret = stack + additional 
        ans = max(ans, ret)
        t += 1
    else:
        break
    
print(ans)