Problem:


Score : 800 points

Problem Statement

There are N stores called Store 1, Store 2, \cdots, Store N. Takahashi, who is at his house at time 0, is planning to visit some of these stores.

It takes Takahashi one unit of time to travel from his house to one of the stores, or between any two stores.

If Takahashi reaches Store i at time t, he can do shopping there after standing in a queue for a_i \times t + b_i units of time. (We assume that it takes no time other than waiting.)

All the stores close at time T + 0.5. If Takahashi is standing in a queue for some store then, he cannot do shopping there.

Takahashi does not do shopping more than once in the same store.

Find the maximum number of times he can do shopping before time T + 0.5.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

0 \leq a_i \leq 10^9

0 \leq b_i \leq 10^9

0 \leq T \leq 10^9

Input

Input is given from Standard Input in the following format:

N T
a_1 b_1
a_2 b_2
\vdots
a_N b_N

Output

Print the answer.

Sample Input 1

3 7
2 0
3 2
0 3

Sample Output 1

2

Here is one possible way to visit stores:

From time 0 to time 1: in 1 unit of time, he travels from his house to Store 1.

From time 1 to time 3: for 2 units of time, he stands in a queue for Store 1 to do shopping.

From time 3 to time 4: in 1 unit of time, he travels from Store 1 to Store 3.

From time 4 to time 7: for 3 units of time, he stands in a queue for Store 3 to do shopping.

In this way, he can do shopping twice before time 7.5.

Sample Input 2

1 3
0 3

Sample Output 2

0

Sample Input 3

5 21600
2 14
3 22
1 3
1 10
1 9

Sample Output 3

5

Sample Input 4

7 57
0 25
3 10
2 4
5 15
3 22
2 14
1 15

Sample Output 4

3



Sample input:
3 7
2 0
3 2
0 3


Sample output:
2

Submission status: Time Limit Exceeded

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

Solution code:
import sys
from bisect import bisect
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    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 = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = (a + 1) * dp[j] + b + 1
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    k = bisect(const_acc, remaining)
    ans = max(ans, i + k)

print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math
import itertools
import bisect

INF = int(1e18)

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

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

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)
    
    shopsA0.sort()

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

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

    DP = np.array([t+10]*29, dtype=np.int64)
    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())


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

n, t = map(int, input().split())
shops = [list(map(int, input().split())) for _ in range(n)]
shops.sort(reverse=True, key=lambda x: x[0]/(x[1]+1))
shops = np.array(shops, dtype=np.int64)

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

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

shops = shops[A1]

DP = np.array([t+10]*30, dtype=np.int64)
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: Time Limit Exceeded

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

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

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]+1)*(a+1)+b, out=DP[1:])

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

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

Submission status: Time Limit Exceeded

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

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に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

"""
import sys
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:
        continue

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

Submission status: Time Limit Exceeded

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に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

"""
import sys
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")] * 30
dp[0] = 0

for k,a,b in kab:

    for i in range(28,-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(30):

    if dp[i] > T:
        continue

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

def get_input():
  n, t = map(int, input().split())

  ab = [list(map(int, input().split())) for _ in range(n)]
  ab0 = sorted(
    [[ai, bi] for ai, bi in ab if ai == 0], 
    key=lambda abi: abi[1]
  )
  abx = sorted(
    [[ai, bi] for ai, bi in ab if ai != 0], 
    key=lambda abi: abi[0] / (1+abi[1]), 
    reverse=True
  )

  return t, ab0, abx

def hoge(prev_dp, a, b, t):
  dp = [float("inf")] * 29
  for j in range(29):
    dp[j] = min(dp[j], prev_dp[j])
    if j != 28 and prev_dp[j] < t:
      dp[j+1] = (1 + a) * (1 + prev_dp[j]) + b
  return dp

def main():

  t, ab0, abx = get_input()

  len_ab0 = len(ab0)
  cum_ab0 = [sum(b + 1 for a, b in ab0[0:i+1]) for i in range(len_ab0)]

  dp = [float("inf")] * 29
  dp[0] = 0

  for ai, bi in abx:
    new_dp = hoge(dp, ai, bi, t)
    dp = new_dp

  ans = 0
  for j, t_x in enumerate(dp):
    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)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def get_input():
  n, t = map(int, input().split())

  ab = [list(map(int, input().split())) for _ in range(n)]
  ab0 = sorted(
    [[ai, bi] for ai, bi in ab if ai == 0], 
    key=lambda abi: abi[1]
  )
  abx = sorted(
    [[ai, bi] for ai, bi in ab if ai != 0], 
    key=lambda abi: abi[0] / (1+abi[1]), 
    reverse=True
  )

  return t, ab0, abx

def hoge(prev_dp, a, b):
  dp = [float("inf")] * 29
  for j in range(29):
    dp[j] = min(dp[j], prev_dp[j])
    if j != 28:
      dp[j+1] = (1 + a) * (1 + prev_dp[j]) + b
  return dp

def main():

  t, ab0, abx = get_input()

  len_ab0 = len(ab0)
  cum_ab0 = [sum(b + 1 for a, b in ab0[0:i+1]) for i in range(len_ab0)]

  dp = [float("inf")] * 29
  dp[0] = 0

  for ai, bi in abx:
    new_dp = hoge(dp, ai, bi)
    dp = new_dp

  ans = 0
  for j, t_x in enumerate(dp):
    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)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def main():

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

  ab = [list(map(int, input().split())) for _ in range(n)]
  ab0 = [[ai, bi] for ai, bi in ab if ai == 0]
  abx = [[ai, bi] for ai, bi in ab if ai != 0]

  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)


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ab = [list(map(int, input().split())) for _ in range(n)]
ab0 = [[ai, bi] for ai, bi in ab if ai == 0]
abx = [[ai, bi] for ai, bi in ab if ai != 0]
    
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: Time Limit Exceeded

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

Solution code:
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))
    # DP
    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()

Submission status: Time Limit Exceeded

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

shop = [tuple(map(int, input().split())) for i in range(n)]

heavy = [s for s in shop if s[0] != 0]
light = [s[1] + 1 for s in shop if s[0] == 0]

light.sort()

from functools import cmp_to_key

def cmp(p, q):
    (ap, bp) = p
    (aq, bq) = q
    ap += 1
    aq += 1
    bp += 1
    bq += 1
    l = aq * bp + bq
    r = ap * bq + bp
    if l < r:return -1
    if l == r:return 0
    if l > r: return 1

heavy = sorted(heavy, key=cmp_to_key(cmp))

dp = [1<<40] * 33
dp[0] = 0
for (a, b) in heavy:
    for i in range(32, 0, -1):
        dp[i] = min(dp[i], (dp[i-1] + 1) *  (a+1) + b)

light_cnt = 0
light_sum = 0

ans = 0
for i in range(32, -1, -1):
    if dp[i] > T:continue
    rest = T - dp[i]
    while light_cnt < len(light) and light_sum + light[light_cnt] <= rest:
        light_sum += light[light_cnt]
        light_cnt += 1
    ans = max(ans, i + light_cnt)
    
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

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

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

    dq = deque()
    dq.append((0, 0, set()))
    ans = 0
    while dq:
        ti, ci, si = dq.pop()

        if ti > T:
            continue

        if ci > ans:
            ans = ci

        tj = ti + 1
        for i in range(N):
            if i in si:
                continue
            ai, bi = S[i]
            tk = tj + ai*tj + bi
            if tk > T:
                continue
            sj = si.copy()
            sj.add(i)
            dq.append((tk, ci+1, sj))
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

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

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

    dq = deque()
    dq.append((0, 0, set()))
    ans = 0
    while dq:
        ti, ci, si = dq.pop()

        if ti > T:
            continue

        if ci > ans:
            ans = ci

        tj = ti + 1
        for i in range(N):
            if i in si:
                continue
            ai, bi = S[i]
            sj = si.copy()
            sj.add(i)
            dq.append((tj + ai*tj + bi, ci+1, sj))
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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


# t = (a + 1)*(t + 1) + b
# t = (t - b) // (a + 1) - 1

ts = [(0, set())]
anses = []
while len(ts) > 0:
  t, se = ts.pop(0)
  if t <= T:
    anses.append(len(se))
  # print(t,se)
  for i, (a, b) in enumerate(ab):
    if not i in se:
      ts.append(((a + 1) * (t + 1) + b, se | {i}))

print(max(anses))

Submission status: Time Limit Exceeded

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

import itertools
max_shop_num = 0
# print(list(itertools.permutations(list(range(N)))))
for route in itertools.permutations(list(range(N))):
    shop_num = 0
    t = 0
    for i in list(route):
        t += 1
        a, b = shops[i]
        tmp_t = t + a * t + b
        if tmp_t > T+0.5:
            if max_shop_num < shop_num:
                max_shop_num = shop_num
            break
        else:
            t = tmp_t
            shop_num += 1
    else:
        if max_shop_num < shop_num:
            max_shop_num = shop_num

print(max_shop_num)

Submission status: Accepted

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 = a / (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: Accepted

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):
            if T>=easyshop[i]:
                id=bisect.bisect_right(dp,T-easyshop[i])
                ans=max(ans,id+i)
            else:
                break
        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: Accepted

Solution code:
def examA():
    S = SI()
    if len(S)%2==1:
        print("No")
        return
    for i in range(len(S)//2):
        if S[i*2:i*2+2]!="hi":
            print("No")
            return
    print("Yes")
    return

def examB():
    a, b, M = LI()
    A = LI()
    B = LI()
    D = [LI()for _ in range(M)]
    ans = min(A) + min(B)
    for x,y,c in D:
        cur = A[x-1]+B[y-1]-c
        ans = min(ans,cur)
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    #print(L)
    odd = 0
    for l in L:
        if l==-1:
            print(-1)
            return
        if l%2==1:
            odd += 1
    G = []
    if odd*2<N:
        for i in range(N):
            if L[i]%2==1:
                G.append(i)
    else:
        for i in range(N):
            if L[i]%2==0:
                G.append(i)

    used = [False]*(N+1)
    ans = [0]*N
    if N//3>=len(G):
        cur = 3
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    else:
        cur = 1
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
            if cur>N:
                cur = 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    print(" ".join(map(str,ans)))
    return

def examD():
    N, T = LI()
    A = []
    A0 = []
    for _ in range(N):
        a, b = LI()
        if a==0:
            A0.append(b)
        else:
            A.append((a/(b+1),a,b))
    A.sort(reverse=True)
    n = len(A)
    S = min(31,n)
    dp = [[inf]*(n+1) for _ in range(S+1)]
    dp[0][0] = 0
    for i,(_,a,b) in enumerate(A):
        for j in range(S):
            now = dp[j][i] + 1
            dp[j][i+1] = min(dp[j][i+1],dp[j][i])
            if now==inf:
                continue
            dp[j+1][i+1] = min(dp[j+1][i+1],now+a*now+b)
    #print(dp)
    dp0 = [0]*(len(A0)+1)
    A0.sort()
    for i,b in enumerate(A0):
        dp0[i+1] = dp0[i]+b+1
    ans = 0
    for i in range(S+1):
        t = T - min(dp[i])
        if t<0:
            break
        cur = (bisect.bisect_right(dp0,t)-1) + i
        if ans<cur:
            ans = cur
    print(ans)
    return

def examE():
    N, M = LI()
    H = 2**N-1; W = 2**M -1
    ans = [[0]*W for _ in range(H)]
    for h in range(H):
        flagh = False
        for m in range(1,11)[::-1]:
            if (h+1)%(2**m)==0:
                flagh = 2**m*2
        for w in range(W):
            flagw = False
            for m in range(1,11)[::-1]:
                if (w+1)%(2**m)==0:
                    flagw = 2 ** m * 2
            if flagh and flagw:
                continue
            ans[h][w] = 1
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

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

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]+1)*(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: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from bisect import bisect_right
from itertools import accumulate
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 + 1) <= a1 * (b2 + 1) else 1

def resolve():
    n, T = map(int, input().split())
    AB = []
    zero = []
    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0:
            AB.append((a, b))
        else:
            zero.append(b + 1)

    AB.sort(key = cmp_to_key(cmp))
    zero.sort()
    zero = list(accumulate(zero))

    max_store = 30
    dp = [T + 1] * max_store
    dp[0] = 0
    for a, b in AB:
        for i in range(max_store - 2, -1, -1):
            t = dp[i]
            dp[i + 1] = min(dp[i + 1], (a + 1) * (t + 1) + b)

    res = 0
    for i in range(max_store):
        t = dp[i]
        if t > T:
            break
        rest = T - t
        res = max(res, i + bisect_right(zero, rest))

    print(res)
resolve()

Submission status: Accepted

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][1])
  else:
    ab1.append(ab[i])
ab0.sort()
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
  anstmp = j
  ttmp = t-dp[n][j]
  i = 0
  while i <= m-1 and ttmp >= ab0[i]+1:
    ttmp -= ab0[i]+1
    anstmp += 1
    i += 1
  ans = max(ans,anstmp)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/hitachi2020/submissions/10704509
# PyPyなら通る

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

    inf = 1 << 30
    L = 30

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

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

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

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            cand = (dp[visited] + 1) * (coef + 1) + const
            if dp[visited + 1] > cand:
                dp[visited + 1] = cand  # 不等式で評価する

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

    *acc, = accumulate(coef_0)

    ans = 0
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  # le->lt,continue->break,restは狭義単調減少
        while cnt > 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        visited += cnt
        if visited > ans:
            ans = visited  # 関数呼び出しとどちらが速いか(set->maxよりは逐次が速かった）
    print(ans)


if __name__ == '__main__':
    main()