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:

"""
Writer: SPD_9X2

dpか?(なるほど)
左からi番目までの店でk個行くと決めた時の最小の時間？

at+b と xt+y があった時、at+bを先に取ったほうが最終的に小さくなる条件は
頑張って手計算すると
x/(1+y) < a/(1+b) なので、a/(1+b)が大きい方から貪欲していくのが正解っぽい？

→ただの貪欲は×
ただ、いくつか取るやつを選べば、その中では↑の式によって最適な取り方が決まる

→a/(1+b)の大きい方からしかとらないので、その順で使う、使わないでdpする
→O(N**2)

どうやってdpするか…

=========答えを見た========
a != 0なら指数関数的に増えるので、(最低で2倍)
回る店の数はせいぜい30にしかならない。
よって、a != 0に関して回る店の数とその最小値をdpした後、a == 0に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

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

kab = []
azero = []

for i in range(N):

    a,b = map(int,input().split())

    if a == 0:
        azero.append(b)
    else:
        k = a/(1+b)
        kab.append([-1*k,a,b])


nt = 0
kab.sort()
dp = [float("inf")] * 29
dp[0] = 0

for k,a,b in kab:

    for i in range(27,-1,-1):

        dp[i+1] = min(dp[i+1] , 1 + dp[i] + a*(1+dp[i]) + b )

azero.sort()
dsum = [0] * (len(azero)+1)
for j,i in enumerate(azero):
    if j != 0:
        dsum[j] = dsum[j-1] + 1 + i

ans = 0
import bisect
for i in range(29):

    if dp[i] > T:
        break

    else:
        ans = max(i + bisect.bisect_right(dsum,T-dp[i]) - 1 , ans )
    
print (ans)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2

dpか?(なるほど)
左からi番目までの店でk個行くと決めた時の最小の時間？

at+b と xt+y があった時、at+bを先に取ったほうが最終的に小さくなる条件は
頑張って手計算すると
x/(1+y) < a/(1+b) なので、a/(1+b)が大きい方から貪欲していくのが正解っぽい？

→ただの貪欲は×
ただ、いくつか取るやつを選べば、その中では↑の式によって最適な取り方が決まる

→a/(1+b)の大きい方からしかとらないので、その順で使う、使わないでdpする
→O(N**2)

どうやってdpするか…

=========答えを見た========
a != 0なら指数関数的に増えるので、(最低で2倍)
回る店の数はせいぜい30にしかならない。
よって、a != 0に関して回る店の数とその最小値をdpした後、a == 0に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

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

kab = []
azero = []

for i in range(N):

    a,b = map(int,input().split())

    if a == 0:
        azero.append(b)
    else:
        k = a/(1+b)
        kab.append([-1*k,a,b])


nt = 0
kab.sort()
dp = [float("inf")] * 29
dp[0] = 0

for k,a,b in kab:

    for i in range(27,-1,-1):

        dp[i+1] = min(dp[i+1] , 1 + dp[i] + a*(1+dp[i]) + b )

azero.sort()
dsum = [0] * len(azero)
for j,i in enumerate(azero):
    dsum[j] = dsum[j-1] + 1 + i

ans = 0
import bisect
for i in range(29):

    if dp[i] > T:
        break

    else:
        ans = max(i + bisect.bisect_right(dsum,T-dp[i]) - 1 , ans )
    
print (ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 12
N = 40
m = len(ab)
dp = [[INF for _ in range(N)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    a, b = ab[i-1][1], ab[i-1][2]
    for j in range(1, N):
        tmp = 1 + dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], tmp + (a * tmp + b))
ans = 0
for i in range(N):
    time = dp[-1][i]
    ans_tmp = i
    if time <= t:
        for v in a0:
            time += (1 + v)
            if time <= t:
                ans_tmp += 1
            else:
                break
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

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

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

time=0
get =0

while(time<T):
    time+=1
    if len(a)==0:
        break
    # if(time>T or len(a)==0):
    #     break
    need = list(map(lambda x,y:x*time+y,a,b))
    print need
    mini= min(need)
    time+=mini
    go=[i for i, x in enumerate(need) if x == mini]#get list to minimum
    gomin=[a[go[i]] for i in range(len(go))]
    # for i in range(len(go)):#make list a
    #     gomin.append(a[go[i]])
    go = gomin.index(min(gomin))#find a minimum index
    del a[go]
    del b[go]
    # if(time>T):
    #     break
    get+=1

print get

Submission status: Wrong Answer

Solution code:
inp=list(map(int,input().split(" ")))
N=inp[0]
T=inp[1]+0.5

a=[0]*N
b=[0]*N
for i in range(N):
    inp=list(map(int,input().split(" ")))
    a[i]=inp[0]
    b[i]=inp[1]


time=0
get =0

while(1):
    time+=1
    if(time>T or len(a)==0):
        break
    need=list(map(lambda x,y:x*time+y,a,b))
    mini=min(need)
    time+=mini
    go=[i for i, x in enumerate(need) if x == mini]#get list to minimum
    gomin=[]
    for i in range(len(go)):#make list a
        gomin.append(a[go[i]])
    go=gomin.index(max(gomin))#find a max index
    del a[go]
    del b[go]
    if(time>T):
        break
    get+=1

print(get)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 12
N = 40
m = len(ab)
dp = [[INF for _ in range(N)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, N):
        tmp = 1 + dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], tmp + (ab[i-1][1] * tmp + ab[i-1][2]))
ans = 0
for i in range(N):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        for v in a0:
            time += (1 + v)
            if time <= t:
                ans_tmp += 1
            else:
                break
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 12
N = 40
m = len(ab)
dp = [[INF for _ in range(N)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, N):
        tmp = dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], 1 + tmp + (ab[i-1][1] * (1 + tmp) + ab[i-1][2]))
ans = 0
for i in range(N):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        for v in a0:
            time += (1 + v)
            if time <= t:
                ans_tmp += 1
            else:
                break
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 12
N = 40
m = len(ab)
dp = [[INF for _ in range(N)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, N):
        tmp = dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], 1 + tmp + (ab[i-1][1] * tmp + ab[i-1][2]))
ans = 0
for i in range(N):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        for v in a0:
            time += (1 + v)
            if time <= t:
                ans_tmp += 1
            else:
                break
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 12
m = len(ab)
dp = [[INF for _ in range(29)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, 29):
        tmp = dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], 1 + tmp + (ab[i-1][1] * tmp + ab[i-1][2]))
ans = 0
for i in range(29):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        for v in a0:
            time += (1 + v)
            if time <= t:
                ans_tmp += 1
            else:
                break
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
inp=list(map(int,input().split(" ")))
N=inp[0]
T=inp[1]+0.5

a=[0]*N
b=[0]*N
for i in range(N):
    inp=list(map(int,input().split(" ")))
    a[i]=inp[0]
    b[i]=inp[1]


time=0
get =0

while(1):
    time+=1
    if(time>T or len(a)==0):
        break
    need=list(map(lambda x,y:x*time+y,a,b))
    mini=min(need)
    time+=mini
    go=[i for i, x in enumerate(need) if x == mini]
    gomin=[]
    for i in range(len(go)):
        gomin.append(a[go[i]])
    go=gomin.index(min(gomin))
    del a[go]
    del b[go]
    if(time>T):
        break
    get+=1

print(get)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 19
m = len(ab)
dp = [[INF for _ in range(29)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, 29):
        tmp = dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], 1 + tmp + (ab[i-1][1] * tmp + ab[i-1][2]))
ans = 0
for i in range(29):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        cnt = t - time
        for v in a0:
            cnt -= (1 + v)
            if cnt >= 0:
                ans_tmp += 1
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 16
m = len(ab)
dp = [[INF for _ in range(29)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, 29):
        tmp = dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], 1 + tmp + (ab[i-1][1] * tmp + ab[i-1][2]))
ans = 0
for i in range(29):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        cnt = t - time
        for v in a0:
            cnt -= (1 + v)
            if cnt >= 0:
                ans_tmp += 1
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

n, t = map(int, input().split())
ab = []
a0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        a0.append(b)
    else:
        ab.append([(a / (b + 1)), a, b])
a0.sort()
ab.sort(reverse=True)

INF = 10 ** 9
m = len(ab)
dp = [[INF for _ in range(29)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
    for j in range(1, 29):
        tmp = dp[i-1][j-1]
        dp[i][j] = min(dp[i-1][j], 1 + tmp + (ab[i-1][1] * tmp + ab[i-1][2]))
ans = 0
for i in range(29):
    time = dp[-1][i]
    if time <= t:
        ans_tmp = i
        cnt = t - time
        for v in a0:
            cnt -= (1 + v)
            if cnt >= 0:
                ans_tmp += 1
        ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

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

zero = []
non_zero = []

for _ in range(n):
	a, b = map(int, input().split())
	if a == 0:
		zero.append(b)
	else:
		non_zero.append((a, b))

zero.sort()
if not zero:
	z_cum = []
else:
	z_cum = [zero[0] + 1]
	for i in range(1, len(zero)):
		z_cum.append(z_cum[-1] + zero[i] + 1)


non_zero.sort(key=lambda x: (x[1]+1)/x[0])
#print(non_zero)

l = len(non_zero)
k = min(30, l)

INF = 10**10
dp = [[INF for _ in range(k+1)] for _ in range(l+1)]
dp[0][0] = 0
for i in range(l):
	a, b = non_zero[i]
	dp[i+1][0] = 0
	for j in range(1, k+1):
		dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 + a * (dp[i][j-1] + 1) + b)
#print(dp)

ans = 0
cur = 0
for i in range(k+1):
	if dp[l][i] > T:
		break
	while cur < len(z_cum) and dp[l][i] + z_cum[cur] <= T :
		cur += 1
	ans = max(ans, i + cur)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
def input():
	return sys.stdin.buffer.readline()[:-1]

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

zero = []
non_zero = []

for _ in range(n):
	a, b = map(int, input().split())
	if a == 0:
		zero.append(b)
	else:
		non_zero.append((a, b))

zero.sort()
if not zero:
	z_cum = []
else:
	z_cum = [zero[0] + 1]
	for i in range(1, len(zero)):
		z_cum.append(z_cum[-1] + zero[i] + 1)


non_zero.sort(key=lambda x: Fraction(x[1]+1, x[0]))
#print(non_zero)

l = len(non_zero)
k = min(30, l)

INF = 10**10
dp = [[INF for _ in range(k+1)] for _ in range(l+1)]
dp[0][0] = 0
for i in range(l):
	a, b = non_zero[i]
	dp[i+1][0] = 0
	for j in range(1, k+1):
		dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 + a * (dp[i][j-1] + 1) + b)
#print(dp)

ans = 0
cur = 0
for i in range(k+1):
	if dp[l][i] > T:
		break
	while cur < len(z_cum) and dp[l][i] + z_cum[cur] <= T :
		cur += 1
	ans = max(ans, i + cur)

print(ans)

Submission status: Wrong Answer

Solution code:
inp=list(map(int,input().split(" ")))
N=inp[0]
T=inp[1]+0.5

a=[0]*N
b=[0]*N
for i in range(N):
    inp=list(map(int,input().split(" ")))
    a[i]=inp[0]
    b[i]=inp[1]


time=0
get =0

while(1):
    time+=1
    if(time>T or len(a)==0):
        break
    need=list(map(lambda x,y:x*time+y,a,b))
    mini=min(need)
    time+=mini
    go=(need.index(mini))
    del a[go]
    del b[go]
    if(time>T):
        break
    get+=1

print(get)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, T = iim()
    S = []
    S0 = []
    for i in range(N):
        a, b = iim()
        (S0 if a == 0 else S).append((a, b))
    S.sort(reverse=True)
    S0.sort()

    N1 = N + 1
    T1 = T + 1
    dp = [T1]*min(T1, N1)
    i = 2
    dp[0] = 0
    for ai, bi in S+S0:
        ti = dp[0]
        for j in range(1, i):
            tj = (ti + 1)*(ai + 1) + bi

            if tj > T:
                break
            ti = dp[j]

            dp[j] = min(ti, tj)
        else:
            i += 1
        #print("1", (ai, bi), dp[:i])


    print(i-2)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
from bisect import bisect
def input():
	return sys.stdin.buffer.readline()[:-1]

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

zero = []
non_zero = []

for _ in range(n):
	a, b = map(int, input().split())
	if a == 0:
		zero.append(b)
	else:
		non_zero.append((a, b))

zero.sort()
z_cum = [0]
for i in range(len(zero)):
	z_cum.append(z_cum[-1] + zero[i] + 1)


non_zero.sort(key=lambda x: Fraction(x[1]+1, x[0]))
#print(non_zero)

l = len(non_zero)
k = min(30, l)

INF = 10**10
dp = [[INF for _ in range(k+1)] for _ in range(l+1)]
dp[0][0] = 0
for i in range(l):
	a, b = non_zero[i]
	dp[i+1][0] = 0
	for j in range(1, k+1):
		dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 + a * (dp[i][j-1] + 1) + b)
#print(dp)

ans = 0
for i in range(1, k+1):
	if dp[l][i] > T:
		break
	sect = bisect(z_cum, T - dp[l][i])
	ans = max(ans, i + sect-1)

print(ans)

Submission status: Wrong Answer

Solution code:
inp=list(map(int,input().split(" ")))
N=inp[0]
T=inp[1]

a=[0]*N
b=[0]*N
for i in range(N):
    inp=list(map(int,input().split(" ")))
    a[i]=inp[0]
    b[i]=inp[1]


time=0
get =0

while(1):
    time+=1
    if(time>T or len(a)==0):
        break
    need=list(map(lambda x,y:x*time+y,a,b))
    mini=min(need)
    time+=mini
    go=(need.index(mini))
    del a[go]
    del b[go]
    if(time>T):
        break
    get+=1

print(get)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, T = iim()
    S = [list(iim()) for i in range(N)]

    N1 = N + 1
    T1 = T + 1
    dp = [T1]*N1
    i = 2
    S.sort(reverse=True)
    dp[0] = 0
    for ai, bi in S:
        ti = dp[0] + 1
        for j in range(1, i):
            tj = ti*(ai + 1) + bi

            if tj > T:
                break
            ti = dp[j]

            dp[j] = min(ti, tj)
            ti += 1
        else:
            i += 1
        #print("1", (ai, bi), dp[:i])


    print(i-2)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def main():
    inf = 10 ** 15

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

    calc0 = []
    calc = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            calc0.append(b)
        else:
            calc.append((a, b))

    calc.sort(key=lambda e: -e[0] / (e[1] + 1))
    calc0.sort()

    dp = [[inf] * (N + 1) for _ in range(N)]

    for i in range(N):
        dp[i][0] = 0

    N2 = len(calc)
    if N2 == 0:
        i = 0
        t = 0
        for e in calc0:
            t += e + 1
            if t > T:
                break
            i += 1
        print(i)
        exit()

    a, b = calc[0]
    dp[0][1] = 1 + a + b

    for i in range(1, N2):
        a, b = calc[i]
        for j in range(1, min(i + 2, N2 + 1)):
            t = dp[i-1][j-1]
            dp[i][j] = min(dp[i - 1][j], t + 1 + a * (t + 1) + b)

    max_i = 0
    if N2 > 0:
        for i, t in enumerate(dp[N2 - 1]):
            if t <= T:
                for e in calc0:
                    t += e + 1
                    if t > T:
                        break
                    i += 1
                max_i = i

    print(max_i)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)

def chkonly(tm, T, N, a, b):
    cnt=0
    i=0
    mise=0
    while i<N:
        if tm+a[i]*max(1,tm)+b[i]<=T:
            if cnt==0:
                cnt=1
                mise=i
            else:
                break
        i+=1
    return (mise,True) if cnt==1 else (mise,False)

def getmise(T, N, a, b):
    ok=-1
    ng=T
    while ng-ok>1:
        mid=(ok+ng)//2
        mise,flag=chkonly(mid, T, N, a, b)
        if flag:
            ok=mid
        else:
            ng=mid
    return ok,mise

def solve(N, T, a, b):
    ans=0
    limit=T
    while limit>0:
        ok,mise=getmise(limit, N, a, b)
        if ok==0:
            break
        if ok>=1:
            ans+=1
            limit=ok
            a[mise]=2**31-1
            b[mise]=2**31-1
        else:
            break
    print(ans)



# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, T, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

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

ab0 = []
abx = []

for _ in range(n):
  a, b = map(int, input().split())
  if a == 0:
    ab0.append([a,b])
  else:
    abx.append([a,b])
    
ab0.sort(key=lambda abi: abi[1])
len_ab0 = len(ab0)
cum_ab0 = [sum(b + 1 for a, b in ab0[0:i+1]) for i in range(len_ab0)]

abx.sort(key=lambda abi: abi[0] / (1+abi[1]), reverse=True)
len_abx = len(abx)

dp = [[float("inf")] * 29 for _ in range(len_abx + 1)]
dp[0][0] = 0

for i, (ai, bi) in enumerate(abx):
  for j in range(29):
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    if j != 28:
      dp[i+1][j+1] = (1 * ai) * (1 + dp[i][j]) + bi

ans = 0
for j, t_x in enumerate(dp[len_abx]):
  if t_x <= t:
    val_0 = bisect.bisect_right(cum_ab0, t - t_x, lo=0, hi=len_ab0)
    if j + val_0 > ans:
      ans = j + val_0

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N,T = map(int,input().split())
    C = [[0,0,0] for _ in range(N)]
    for i in range(N):
        a,b = map(int,input().split(" "))
        c = a/(b+1)
        C[i] = [c,a,b]
    C.sort()
    C.reverse()
    C = np.array(C)
    ans = 0
    dp = [[0]+[float('inf') for _ in reversed(range(min(i+1,28)))] for i in range(N)]

    for i in range(N):
        for j in range(1,min(28,i+1)):
            _,a,b = C[i]
            if a == 0:
                break
            dp[i][j] = min(dp[i][j],(a+1)*(dp[i][j-1])+b)
    for i,v in enumerate(dp[-1]):
        if v <= T+0.5:
            ans = i+1        
    tmp = min(dp[-1])
    aans = dp[-1].index(tmp)+1
    for i in reversed(range(N)):
        _,a,b = C[i]
        if a != 0:
            break
        else:
            tmp += b
            if tmp <= T+0.5:
                aans += 1
    print(max(ans,aans))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N,T = map(int,input().split())
    C = [[0,0,0] for _ in range(N)]
    for i in range(N):
        a,b = map(int,input().split(" "))
        c = a/(b+1)
        C[i] = [c,a,b]
    C.sort()
    C.reverse()
    C = np.array(C)
    ans = 0
    dp = [[0]+[float('inf') for _ in reversed(range(min(i+1,28)))] for i in range(N)]

    for i in range(N):
        for j in range(1,min(28,i+1)):
            _,a,b = C[i]
            if a == 0:
                break
            dp[i][j] = min(dp[i][j],(a+1)*(dp[i][j-1])+b)
    for i,v in enumerate(dp[-1]):
        if v <= T+0.5:
            ans = i+1        
    tmp = 0
    anns = 0
    for i in range(N):
        _,a,b = C[i]
        if a != 0:
            continue
        else:
            tmp += (C[i][2]+1)
            if tmp <= T+0.5:
                anns += 1
    print(max(ans,anns))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, T = iim()
    S = [list(iim()) for i in range(N)]

    N1 = N + 1
    T1 = T+1
    dp, dp2 = [T1]*N1, [T1]*N1
    i = 2
    dp[0] = dp2[0] = 0
    for ai, bi in S:
        for j in range(1, i):
            tj = (dp[j-1]+1)*ai + bi
            if tj >= T:
                break

            dp2[j] = min(dp2[j], tj)
        else:
            i += 1
        #print("1", dp)
        #print("2", dp2)

        dp, dp2 = dp2, dp


    print(i-2)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#D
n,T=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(n):
    a[i],b[i]=map(int,input().split())
# print("a",a,"b",b)

shop=0
time=0
x=list(range(n))
# print(x)
while time<T+0.5:
    time+=1#移動
    # print(x)
    #時間を取得(残り店n-1)最小時間を求める
    mint=a[x[0]]*time+b[x[0]]
    popi=0
    # print(time)
    for i in range(len(x)):
        t=a[x[i]]*time+b[x[i]]
        # print(x[i],t,mint)
        if mint>t:
            # print("t",i)
            popi=i
            mint=t
    time+=mint#待ち時間
    if time<T+0.5:
        # print("shop:",x[popi])
        x.pop(popi)
        shop+=1
    else:
        break
    if not x:
        break
    # print("a",a,"b",b)

print(shop)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10
N = 100
n, T = map(int, raw_input().split())

stores = []
zs = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    if a == 0:
        zs.append(b)
    else:
        stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)
stores.append((INF, INF))
zs.sort()

m = len(zs)

for i in xrange(1, m):
    zs[i] += zs[i - 1]

dp = [ [INF for i in xrange(N)] for j in xrange(2) ]
dp[0][0] = 0
res = 0

n = len(stores)

p = 0
for i in xrange(n):
    q = p ^ 1
    dp[q] = [INF for j in xrange(N)]

    a, b = stores[i]
    for j in xrange(N):
        dp[q][j] = min(dp[q][j], dp[p][j])
        if dp[p][j] == -INF:
            continue
        if j + 1 < N:
            t = dp[p][j] + 1
            dp[q][j + 1] = min(dp[q][j + 1], dp[p][j] + 1 + a * t + b)
            if dp[q][j + 1] <= T:
                res = max(res, j + 1)
    for j in xrange(N):
        if dp[q][j] > T:
            continue
        rem = T - dp[q][j] - 1
        l, r = 0, m - 1
        while l <= r:
            mid = (l + r) / 2
            if zs[mid] + mid <= rem:
                res = max(res, j + mid)
                l = m + 1
            else:
                r = m - 1
    p = q
print res

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, T = iim()
    S = [list(iim()) for i in range(N)]

    N1 = N + 1
    T1 = T+1
    dp, dp2 = [T1]*N1, [T1]*N1
    lj = 2
    dp[0] = dp2[0] = 0
    for i, (ai, bi) in enumerate(S):
        for j in range(1, lj):
            dp2[j] = min(dp2[j], (dp[j-1]+1)*ai + bi)
        #print("1", dp)
        #print("2", dp2)

        k = 1
        for j in range(1, lj):
            dj = dp2[j]
            if dj < T:
                dp[k] = dp2[j]
                k += 1
        lj = k + 1

    print(lj-2)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10
N = 100
n, T = map(int, raw_input().split())

stores = []
zs = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    if a == 0:
        zs.append(b)
    else:
        stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

dp = [ [INF for i in xrange(N)] for j in xrange(2) ]
dp[0][0] = 0
res = 0

n = len(stores)

p = 0
for i in xrange(n):
    q = p ^ 1
    dp[q] = [INF for j in xrange(N)]

    a, b = stores[i]
    for j in xrange(N):
        dp[q][j] = min(dp[q][j], dp[p][j])
        if dp[p][j] == -INF:
            continue
        if j + 1 < N:
            t = dp[p][j] + 1
            dp[q][j + 1] = min(dp[q][j + 1], dp[p][j] + 1 + a * t + b)
            if dp[q][j + 1] <= T:
                res = max(res, j + 1)
    p = q
print res

Submission status: Wrong Answer

Solution code:
import bisect
n,T=map(int,input().split())
ab=[]
a0=[-1]
for _ in range(n):
    a,b=map(int,input().split())
    if a==0:
        a0.append(b)
    else:
        ab.append([a,b])
a0.sort()
a0_l=len(a0)
for i in range(a0_l-1):
    a0[i+1]+=a0[i]+1
ab.sort()
ab_l=len(ab)
ab_used=[0]*ab_l
ab_memo=[1]
t=1
while t<=T+2:
    w=-1
    m=float("INF")
    for i in range(ab_l):
        if ab_used[i]==0 and (w==-1 or ab[i][0]*t+ab[i][1]<=m):
            w=i
            m=ab[i][0]*t+ab[i][1]
    if w==-1:
        break
    else:
        t+=m+1
        ab_memo.append(t)
        ab_used[w]=1
ans=0
for i in range(a0_l):
    if a0[i]<=T-1:
        ans_=i+bisect.bisect_right(ab_memo,T-a0[i])-1
        ans=max(ans,ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import cmp_to_key
import itertools

N, T = map(int, readline().split())
m = map(int, read().split())
AB0 = []
AB1 = []
for a,b in zip(m,m):
    if a == 0:
        AB0.append(b)
    else:
        AB1.append((a,b))

def sort_func(ab0, ab1):
    a0, b0 = ab0
    a1, b1 = ab1
    return a1*(1+b0) - a0*(1+b1)

AB0.sort()
AB1.sort(key=lambda x: x[0] / (x[1] + 1))
AB0, AB1

def compute_0():
    INF = T + 1
    dp = [INF] * 40
    dp[0] = 0
    for a,b in AB1:
        for n in range(39, -1, -1):
            if dp[n] > T:
                continue
            x = (dp[n] + 1) * (a + 1) + b
            if x < dp[n+1]:
                dp[n+1] = x
    return dp

def compute_1():
    return [0] + list(itertools.accumulate(x + 1 for x in AB0))

dp0 = compute_0()
dp1 = compute_1()

R = len(dp1) - 1
answer = 0
for i,x in enumerate(dp0):
    if x > T:
        break
    while x + dp1[R] > T:
        R -= 1
    value = i + R
    if answer < value:
        answer = value

print(answer)

Submission status: Wrong Answer

Solution code:
N, T = map(int,input().split())
list_ = [list(map(int,input().split())) for i in range(N)]

t = 0
limit = T + 0.5
num = 0

def judge_min_time(array, t):
    """その時間での最小の待ち時間とインデックスを返す"""
    min_time = float("inf")
    for i in range(len(array)):
        min_time = min(min_time, array[i][0]*t + array[i][1])
        if min_time == array[i][0]*t + array[i][1]:
            idx = i
    return min_time, idx
        
while t < limit:
    if not list_:
        break
    t += 1
    time, idx = judge_min_time(list_, t)
    t += time
    if t <limit:
        num += 1
        list_.pop(idx)
    
print(num)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N,T = map(int,input().split())
    C = [[0,0,0] for _ in range(N)]
    for i in range(N):
        a,b = map(int,input().split(" "))
        c = a/(b+1)
        C[i] = [c,a,b]
    C.sort()
    C = np.array(C)
    t1 = 0
    t2 = float('inf')
    ans = 0
    for _ in range(28):
        for i in range(N):
            _,a,b = C[i]
            if a == 0:
                continue
            else:
                t2 = min(t2,(a+1)*(t1+1)+b)
        if t2 <= T+0.5:
            ans += 1
            t1 = int(t2)
            t2 = float('inf')
        else:break
    tmp = 0
    anns = 0
    for i in range(N):
        _,a,b = C[i]
        if a != 0:
            break
        else:
            tmp += (C[i][2]+1)
            if tmp <= T+0.5:
                anns += 1
    print(max(ans,anns))