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

Solution (Python):
def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


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

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

    shopsA0.sort()
    shops.sort(reverse=True, key=lambda x: x[0]/(x[1]+1))


    DP = [t+10] * 30
    DP[0] = 0

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

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A = 28
    for count, spend_time in enumerate(cumA0):
        residue = t - spend_time
        if residue < 0:
            break
        while DP[count_A] > residue:
            count_A -= 1
        ans.append(count_A + count)
    print(max(ans))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


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

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

    shopsA0.sort()
    shops.sort(reverse=True, key=lambda x: x[0]/(x[1]+1))


    DP = [t+10] * 30
    DP[0] = 0

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

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


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

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

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


    DP = [t+10] * 30
    DP[0] = 0

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

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


if __name__ == '__main__':
    main()

Solution (Python):

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):


        dp[i+1][j] = min(min(dp[i][j], (a+1)*(dp[i][j-1]+1)+b), T+1)
    fi = i+1



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



r=0
for i in range(30):
    if dp[fi][i] > T:
        break
    nt = T-dp[fi][i]

    for j, b in enumerate(bbs):

        if b > nt:
            break
    r=max(r, i+j-1)
print(r)

Solution (Python):
"""
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]
for i in azero:
    dsum.append(dsum[-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)

Solution (Python):
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]
    dp[i][0] = 0
    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)

Solution (Python):
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])


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)


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

print(ans)

Solution (Python):
def solve(n, t, ab_list):
    a0b_list = [ab[1] for ab in ab_list if ab[0] == 0]
    apb_list = [ab for ab in ab_list if ab[0] > 0]
    a0b_list = sorted(a0b_list)
    apb_list = sorted(apb_list, key=lambda x: - x[0] / (x[1] + 1))
    
    m = len(apb_list)
    dp = [[t + 1] * 30 for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = 0
    for i in range(m):
        for k in range(1, 30):
            ti = dp[i][k - 1] + 1
            a, b = apb_list[i]
            dp[i + 1][k] = min(dp[i][k], ti + a * ti + b)
    a0b_list_cum_sum = [0]
    s = 0
    for b in a0b_list:
        s += b + 1
        a0b_list_cum_sum.append(s)

    res = 0

    for k in range(len(a0b_list_cum_sum)):
        for p in range(30):
            if dp[m][p] + a0b_list_cum_sum[k] <= t:
                res = max(res, k + p)

    return res


def main():
    n, t = map(int, input().split())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    res = solve(n, t, ab_list)
    print(res)


def test():
    assert solve(3, 7, [[2, 0], [3, 2], [0, 3]]) == 2
    assert solve(1, 3, [[0, 3]]) == 0
    assert solve(5, 21600, [[2, 14], [3, 22], [1, 3], [1, 10], [1, 9]]) == 5


if __name__ == "__main__":
    test()
    main()

Solution (Python):
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 + 1)
                l = mid + 1
            else:
                r = mid - 1
    p = q
print res

Solution (Python):
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), reverse=True)
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)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

INF = 10**18+3
N, T = map(int, readline().split())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
ABzero = [b for a, b in AB if a == 0]
ABnonzero = [(a, b) for a, b in AB if a]
ABnonzero.sort(key = lambda x: (x[1]+1)/x[0])


dp = [0]
for a, b in ABnonzero:
    dp2 = dp + [INF]
    for j in range(1, len(dp2)):
        dp2[j] = min(dp2[j], (dp[j-1]+1)*(a+1)+b)
    dp = [d for d in dp2 if d <= T]

ABzero.sort()
dpzero = [0] + [b+1 for b in ABzero]
for i in range(1, len(dpzero)):
    dpzero[i] += dpzero[i-1]

DP = [INF]*(N+1)
for i in range(len(dp)):
    for j in range(len(dpzero)):
        DP[i+j] = min(DP[i+j], dp[i] + dpzero[j])

DP = [d for d in DP if d <= T]
print(max(0, len(DP)-1))

Solution (Python):
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=cmp_to_key(sort_func))
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)