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:
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**9+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)
    
    
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[0]+x[1]+1)/x[0])

INF = 10**9+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)
    
    
for j in range(50):
    if dp[N1][j]>T:break    
    # a>0をi店舗めぐった後に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[0]+x[1]+1)/x[0])

INF = 10**9+7

dp = [INF]*50
dp[0] = 0
ans = 0
for i in range(49):
    if dp[i]>T:break
    # a>0をi店舗めぐった後にa=0を何店舗めぐれるか
    num0 = bisect_right(b_ruiseki, T - dp[i])
    ans = max(ans, i + num0)
    if i>=N1:
        break
    dp[i+1] = (dp[i]+1)*ab1[i][0] + ab1[i][1] + 1
    
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]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

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

INF = 10**9+7

dp = [INF]*50
dp[0] = 0
ans = 0
for i in range(49):
    if dp[i]>T:break
    # a>0をi店舗めぐった後にa=0を何店舗めぐれるか
    num0 = bisect_right(b_ruiseki, T - dp[i])
    ans = max(ans, i + num0)
    if i>=N1:
        break
    dp[i+1] = (dp[i]+1)*ab1[i][0] + ab1[i][1] + 1
    
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]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

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

INF = 10**9+7

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

Submission status: Wrong Answer

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] * 31 
dp[0] = 0

for a, b in l_a1:
        for num in range(29, -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: Wrong Answer

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] * 31 
dp[0] = 0

for a, b in l_a1:
        for num in range(29, -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(len(dp))    
print(max(ans))

Submission status: Wrong Answer

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

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 = [INF for _ in range(30)]
dp[0] = 0

m = min(n+1, 30)

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

print(ans)

Submission status: Wrong Answer

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

m = min(n+1, 30)

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

print(ans)

Submission status: Wrong Answer

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

m = min(n+1, 30)

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

print(ans)

Submission status: Wrong Answer

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

m = min(n+1, 28)

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: 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):
    for count in range(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)
for count,t in enumerate(dp[-1]):
    if t > T:
        break
    v = bisect.bisect_right(a0sum,T-t)
    ans = max(ans, v + count)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect
from itertools import accumulate
import numpy as np

n, t, *ab = map(int, sys.stdin.buffer.read().split())
constant = []
variable = []
for a, b in zip(ab[0::2], ab[1::2]):
    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 = np.full(t2, INF, dtype=np.int64)
dp[0] = 1
for _, a, b in variable:
    ndp = (a + 1) * dp + b + 1
    dp[1:] = np.minimum(dp[1:], ndp[:-1])
    dp = dp[dp <= t]

const_acc = np.cumsum(constant)
extra = np.searchsorted(const_acc, t - dp, side='right')
print((np.arange(len(extra)) + extra).max())

Submission status: Wrong Answer

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])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[0]/(x[1]+1))
shop_a0 = sorted(shop_a0)

dp = [10**10 for _ in range(30)]
dp[0] = 0

m = min(n+1, 30)

for j in range(m):
    for a, b in shop:
        dp[j] = min(dp[j], dp[j-1] + 1 +
                    a*(dp[j-1]+1) + b)

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

ans = min(n, ans)
print(ans)

Submission status: Wrong Answer

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])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[0]/(x[1]+1))
shop_a0 = sorted(shop_a0)

dp = [10**10 for _ in range(30)]
dp[0] = 0

for j in range(30):
    for a, b in shop:
        dp[j] = min(dp[j], dp[j-1] + 1 +
                    a*(dp[j-1]+1) + b)

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

ans = min(n, ans)
print(ans)

Submission status: Wrong Answer

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(1, 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 = bisect_right(ss, t)

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

print(ans)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)
VISIT_MAX = int(math.log(T_MAX, 2))

def main():
    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)):
        if len(dp) < VISIT_MAX + 1:
            dp_ = dp + [INF]
        for c in range(1, len(dp_)):
            a, b = nzshops[i]
            x = dp[c - 1] + 1
            dp_[c] = min(dp_[c], x + x * a + b)
        dp = dp_

    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)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys
import math
import itertools
import bisect

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

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

    shops.sort(key=lambda x: 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.log(T_MAX, 2)) 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: Wrong Answer

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

import sys
import math
import itertools
import bisect

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

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

    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.log(T_MAX, 2)) 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)

    ans = 0
    for c in range(len(dp[-1])):
        time = dp[-1][c]
        ans_tmp = c
        if time <= T:
            for _, v in shops[nnz:]:
                time += (1 + v)
                if time <= T:
                    ans_tmp += 1
                else:
                    break
            ans = max(ans, ans_tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys
import math
import itertools
import bisect

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

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

    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.log(T_MAX, 2)) 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: Wrong Answer

Solution code:
import numpy as np
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)
    else:
        tmp.append(float(0))
        l_a1.append(tmp)

l_a0 = np.array(l_a0)
l_a1 = np.array(l_a1)

if len(l_a0) == 0:
    for i in range(len(l_a1)):
        l_a1[i][2] = float(l_a1[i][0]/(l_a1[i][1]+1))
    l_a1 = l_a1[np.argsort(l_a1[:, 2])[::-1]]
    
    ans = 0
    tmp = 0
    for i in range(len(l_a1)):
        if tmp + 1 + l_a1[i][0]*(tmp + 1) + l_a1[i][0] <= t:
            tmp += 1 + l_a1[i][0]*(tmp + 1) + l_a1[i][0]
            ans += 1
        
    print(ans)    
            
elif len(l_a1) == 0:
    l_a0 = l_a0[np.argsort(l_a0[:, 1])]
    ans = 0
    tmp = 0
    for i in range(len(l_a0)):
        if tmp + 1 + l_a0[i][1] <= t:
            tmp += l_a0[i][1]
            ans += 1
        
    print(ans)        

else:
    l_a0 = l_a0[np.argsort(l_a0[:, 1])]
    for i in range(len(l_a1)):
        l_a1[i][2] = float(l_a1[i][0]/(l_a1[i][1]+1))
        l_a1 = l_a1[np.argsort(l_a1[:, 2])[::-1]]   
    
    dp = [[float('inf')] * 4 for i in range(len(l_a1) + 1)]
    dp[0][0] = 0
    for i in range(1,len(l_a1)+1):
        for j in range(4):
            dp[i][j] = min(dp[i-1][j],(dp[i-1][j-1] + 1 + l_a1[i-1][0]*(dp[i-1][j-1] + 1)+l_a1[i-1][1]))
    ans = 0
    for i in range(4):
        judge = dp[-1][i]
        if judge >= t:
         break
        tmp = i
        for j in range(len(l_a0)):
            if judge + 1 + l_a0[j][1] <= t:
                judge += l_a0[j][1]
                tmp += 1
            else:
             break
        if tmp >= ans:
            ans = tmp
      
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shop_a = []
    shop_b = []
    shopsA0 = []

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b+1)
        else:
            shop_a.append(a)
            shop_b.append(b)

    shop_a = np.array(shop_a, dtype=np.int64)
    shop_b = np.array(shop_b, dtype=np.int64)
    key = shop_a / (shop_b+1)
    sort_index = np.argsort(key)[::-1]
    shop_a = shop_a[sort_index]
    shop_b = shop_b[sort_index]

    DP = np.full(29, t+10, dtype=np.int64)
    DP[0] = 0

    for a, b in zip(shop_a, shop_b):
        np.minimum(DP[1:], (DP[:-1] + 1) * (a + 1) + b, out=DP[1:])

    cumA0 = np.cumsum(shopsA0, dtype=np.int64)

    DP = DP[DP <= t]
    DPA0 = np.searchsorted(cumA0, t - DP, side='right')
    ans = np.arange(len(DP)) + DPA0
    print(ans.max())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shop_a = []
    shop_b = []
    shopsA0 = []

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b+1)
        else:
            shop_a.append(a)
            shop_b.append(b)

    shop_a = np.array(shop_a, dtype=np.int64)
    shop_b = np.array(shop_b, dtype=np.int64)
    key = shop_a / (shop_b+1)
    sort_index = np.argsort(key)[::-1]
    shop_a = shop_a[sort_index]
    shop_b = shop_b[sort_index]

    print(1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = []

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b+1)
        else:
            shops.append([a/(b + 1), a, b])

    shops.sort(reverse=True)
    shopsA0.sort()

    print(1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = []

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b+1)
        else:
            shops.append([a/(b + 1), a, b])

    shops.sort(reverse=True)
    shopsA0.sort()
    
    print(1)


if __name__ == 'main':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

n, t = map(int, input().split())
shops = []
shopsA0 = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b+1)
    else:
        shops.append([a/(b + 1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t+10]*30, dtype=np.uint32)
DP[0] = 0

for _, a, b in shops:
    np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

n, t = map(int, input().split())
shops = []
shopsA0 = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b+1)
    else:
        shops.append([a/(b + 1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t+10]*30, dtype=np.uint32)
DP[0] = 0

for _, a, b in shops:
    np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


n, t = map(int, input().split())
shops = np.array([list(map(int, input().split())) for _ in range(n)], dtype=np.uint32)

A0 = shops[:, 0] == 0
A1 = shops[:, 0] != 0

shopsA0 = shops[A0][:, 1] + 1
shopsA0.sort()

shops = shops[A1]
keys = shops[:, 0] / (shops[:, 1]+1)
sort_idx = np.argsort(keys)[::-1]
shops = shops[sort_idx]

DP = np.array([t+10]*30, dtype=np.uint32)
DP[0] = 0

for a, b in shops:
    np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


n, t = map(int, input().split())
shops = []
shopsA0 = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b+1)
    else:
        shops.append([a/(b+1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t+10] * 30, dtype=np.int64)
DP[0] = 0

for _, a, b in shops:
    np.minimum(DP[1:], (DP[:-1])*(a+1) + a + b, out=DP[1:])
    
cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


n, t = map(int, input().split())
shops = []
shopsA0 = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b+1)
    else:
        shops.append([a/(b+1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t+10] * 30, dtype=np.int64)
DP[0] = 0

for i in range(min(len(shops), 30)):
    _, a, b = shops[i]
    np.minimum(DP[1:], (DP[:-1])*(a+1) + a + b, out=DP[1:])
    
cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


n, t = map(int, input().split())
shops = []
shopsA0 = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shopsA0.append(b+1)
    else:
        shops.append([a/(b+1), a, b])

shops.sort(reverse=True)
shopsA0.sort()

DP = np.array([t+10] * 30, dtype=np.int64)
DP[0] = 0

for _, a, b in shops:
    np.minimum(DP[1:], (DP[:-1])*(a+1) + a + b, out=DP[1:])

cumA0 = np.cumsum(shopsA0, dtype=np.int64)

DP = DP[DP <= t]
DPA0 = np.searchsorted(cumA0, t-DP, side='right')
ans = np.arange(len(DP)) + DPA0
print(ans.max())

Submission status: Wrong Answer

Solution code:

N, T = map(int, input().split())
X = []
for _ in range(N):
    a, b = map(int, input().split())
    X.append((a,b))

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

dp = [[0]+[T+2]*29 for _ in range(N+1)]
bs = []
fi=0
for i, (a, b) in enumerate(X):
    if a==0:
        bs.append(b)
        continue
    for j in range(1, 30):
#        if j==1:
#            print(a*(dp[i][j-1]+1)+b)
        dp[i+1][j] = min(min(dp[i][j], a*(dp[i][j-1]+1)+b), T+1)
    fi = i+1

#print(dp)

bs.sort()
bbs = [0]
for i, b in enumerate(bs):
    bbs.append(bbs[-1]+bs[i]+1)
bbs.append(10**18)


#print(dp[fi], bbs)
r=0
for i in range(30):
    if dp[fi][i] > T:
        break
    nt = T-dp[fi][i]
#    print(nt)
    for j, b in enumerate(bbs):
#        print(1, b)
        if b > nt:
            break
    r=max(r, i+j-1)
print(r)