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: 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)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

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

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)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    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
        ans = max(ans, visited + cnt)
    print(ans) # setのminと逐次minどちらが速い


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

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

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
for i in range(k+1):
    DP[0][i]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(1,30):
    for j in range(1,k+1):
        nt=nexttime(DP[i-1][j-1],M[j-1][0],M[j-1][1])
        DP[i][j]=min(DP[i][j-1],nt)
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)

Submission status: Accepted

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

b0 = []
ab1 = []

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

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

b0.sort()

#bは累積和で時間計算可能（最後にどこまで足せるかを調べる）
if N0>0:
    b_ruiseki = [0]*N0
    b_ruiseki[0] = b0[0]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []
#探索範囲が28店まででいいからソートする
ab1.sort()

INF = T + 100
 
dp = [[INF]*31 for i in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    # dp[i+1][j] : 0~i番目までの店を見て，j個選ぶときの最小時間
    for j in range(31):
        if j > i+1:
            break
        if j == 0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-1]+1 + ab1[i][1]*(dp[i][j-1]+1) + ab1[i][2])

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

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# 解説

N, T = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)

# 移動時間を考えなくて良いようにする
A += 1
B += 1
T += 1

# 使う店を決めたとき、(a - 1) / b の大きい順に使うのが最適
I = np.argsort((A - 1) / B)[::-1]
A = A[I]
B = B[I]

idx_zero = np.searchsorted((A == 1).astype(int), 1, side='left')
A1 = A[:idx_zero]
B1 = B[:idx_zero]
B2 = np.msort(B[idx_zero:])

MAX_COUNT = (10 ** 9).bit_length() + 2
# dp[i][x]: i まで見て、x こ使うときの t の最小値
dp = np.full((idx_zero + 1, MAX_COUNT), T + 1, dtype=int)
dp[:, 0] = 1
for x in range(MAX_COUNT - 1):
    next_col = dp[:-1, x] * A1 + B1
    np.minimum(next_col, T + 1, out=next_col)
    np.minimum.accumulate(next_col, out=next_col)
    dp[1:, x + 1] = next_col

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

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from itertools import accumulate
def resolve():
    N, T = lr()
    ab = []
    a0b = [0]
    for i in range(N):
        a, b = lr()
        if a >= 1:
            ab.append([a, b])
        else:
            a0b.append(b+1)
    ab = sorted(ab, key=lambda x: x[0]/(x[1]+1))[::-1]
    a0b = sorted(a0b)
    dp = [T+1]*30
    dp[0] = 0
    for a, b in ab:
        for i in range(28, -1, -1):
            t = (a+1)*(dp[i]+1)+b
            if t < dp[i+1]:
                dp[i+1] = t
    ans = 0
    acc = list(accumulate(a0b))
    num = len(acc)-1
    for i in range(30):
        t = dp[i]
        if t > T+0.5:
            break
        while num > 0 and t+acc[num] > T+0.5:
            num -= 1
        ans = max(ans, i+num)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right

N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
#%%
b0 = []
ab1 = []
for a,b in ab:
    if a==0:
        b0.append(b+1)
    else:
        ab1.append([(b+1)/a, 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()

INF = T + 100

dp = [[INF]*31 for _ in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    # dp[i+1][j] : 0~i番目までの店を見て，j個選ぶときの最小時間
    
    for j in range(31):
        if j>i+1:break
        if j==0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], (dp[i][j-1]+1)*(ab1[i][1]+1)+ab1[i][2])

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

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
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店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Submission status: Accepted

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店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Submission status: Accepted

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)[::-1]:
        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: Accepted

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

m = min(n+1, 30)

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

print(ans)

Submission status: Accepted

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[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    # input
    N, T = map(int, input().split())
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = map(int, input().split())
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    # sort
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(range(L), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    # --- case a >= 1 --- #
    # dp[for i shops][passed j shops] := min time
    # j:29 for T < 10^9
    J_MAX = min(L + 1, 29)
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    # --- case a = 0 --- #
    ans = 0
    for i in range(J_MAX):
        if dp[L][i] == float('inf'):
            break
        else:
            time_cnt = dp[L][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + 1 + t_b <= T:
                    time_cnt += 1 + t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import math
import itertools
import bisect

INF = int(1e18)

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)

Submission status: Accepted

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)):
        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 = [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: Accepted

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

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

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

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[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 zshops))
    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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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