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: Runtime Error

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

import sys
import math
import itertools

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

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

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in memo:
            return memo[i, t]

        h = i - 1
        s = int((t - shops[h][1]) / (shops[h][0] + 1)) - 1
        x = max(dp(h, s) + 1, dp(h, t)) if s >= 0 else dp(h, t)
        memo[i, t] = x
        return x

    print(dp(N, T))
    #print(sorted(memo.items()))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 = []
for i, (a, b) in enumerate(X):
    if a==0:
        bs.append(b)
        continue
    for j in range(1, 30):
#        if j==1:
#            print(a*(dp[i][j-1]+1)+b)
        dp[i+1][j] = min(min(dp[i][j], a*(dp[i][j-1]+1)+b), T+1)
    fi = i+1

#print(dp)

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


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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ cin >> p.first >> p.second; return s;}
#define all(a) begin(a),end(a)
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}

int main()
{
    ll N, T; cin >>N>>T;
    vpll AB(N); cin >> AB;
    sort(all(AB), [](const pll& x, const pll& y){
        // if (x.first == 0 && y.first == 0) {
        //     return x.second < y.second;
        // }
        // if (x.first == 0) {
        //     return false;
        // }
        // if (y.first == 0) {
        //     return true;
        // }
        ll p = y.first * (x.second+1);
        ll q = x.first * (y.second+1);
        return p < q;
    });

    ll ans = 0;
    unordered_map<ll, ll> dp;
    dp[0] = 0;
    rep(i, N) {
        vpll update;
        for (auto it = dp.begin(); it != dp.end(); it++) {
            ll t = it->first;
            ll c = it->second;
            ll next_t = t + 1 + AB[i].first * (t + 1) + AB[i].second;
            ll next_c = c + 1; 
            if (next_t <= T) {
                update.push_back(make_pair(next_t, next_c));
            }
        }
        for (const auto&  u : update) {
            if (dp[u.first] < u.second) {
                dp[u.first] = u.second;
                chmax(ans, u.second);
            }
        }
    }

    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;


int N, T;
vector<int> a, b;
vector<vector<int>> dp;
const int INF = 1e9 + 1;


void input() {
    cin >> N >> T;
    a = b = vector<int>(N);
    rep(i, N) cin >> a[i] >> b[i];
}


bool judge(int x, vector<int> &pl, vector<int> &bsum) {
    if (x < pl.size() && pl[x] <= T) return true;
    for (int i = 0; i < min(x, int(pl.size())); i++) {
        int n = x - i;
        if (n < bsum.size() && pl[i] + bsum[n] <= T) return true;
    }
    return false;
}


int main() {
    input();
    vector<int> zb, pa, pb;
    rep(i, N) {
        if (a[i] == 0) {
            zb.push_back(b[i]);
        } else {
            pa.push_back(a[i]);
            pb.push_back(b[i]);
        }
    }
    sort(zb.begin(), zb.end());
    vector<int> bsum;
    bsum.push_back(0);
    for (int v : zb) bsum.push_back(bsum.back() + v + 1);
    int zn = bsum.size(), pn = pa.size();
    int n = min(pn, int(log2(T + 1)));
    dp = vector<vector<int>>(pn + 1, vector<int>(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 1; i <= pn; i++) {
        dp[i][0] = 0;
        for (int j = 1; j <= i; j++) {
            int x = min(INF, (dp[i-1][j-1] + 1) * pa[i-1] + pb[i-1]);
            dp[i][j] = min(x, dp[i-1][j]);
        }
    }
    int left = 0, right = N + 1;
    while (right - left > 1) {
        int x = (left + right) / 2;
        if (judge(x, dp[pn], bsum)) {
            left = x;
        } else {
            right = x;
        }
    }
    cout << left << endl;
}

Submission status: Runtime Error

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

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

  for ai, bi in abx:
    dp = hoge(prev_dp, ai, bi)
    prev_dp = 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: Runtime Error

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]*T1
    i = 2
    dp[0] = 0
    for ai, bi in S:
        ti = dp[0]
        for j in range(1, i):
            tj = (ti+1)*ai + 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: Runtime Error

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

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

    N2 = len(calc)
    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
    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: Runtime Error

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

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: Runtime Error

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')
    for _ in range(28):
        for i in range(N):
            if C[i][1] == 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
    a = 0
    for i in range(N):
        if C[i][1] != 0:
            break
        else:
            tmp += (C[i][2]+1)
            if tmp <= T+0.5:
                a += 1
    print(max(ans,a))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    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

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 = j + 1
    p = q
print res

Submission status: Runtime Error

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

import sys
import math
import itertools


def main():
    N, T = map(int, sys.stdin.readline().split())
    As, Bs = map(list, zip(*(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))))

    # dp[i + 1][t] := i番目までの店のうち時間 t を超えないように訪問できる店の数
    # dp[i + 1][t] | int((t - Bs[i]) / As[i]) - 1 >= 0 = max(dp[i][int((t - Bs[i]) / As[i]) - 1] + 1, dp[i][t])
    #              | otherwise                         = dp[i][t]

    memo = {}

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in memo:
            return memo[i, t]

        h = i - 1

        tpre = int((t - Bs[h]) / (As[h] + 1)) - 1
        if tpre >= 0:
            x = memo[i, t] = max(dp(h, tpre) + 1, dp(h, t))
            return x
        else:
            x = memo[i, t] = dp(h, t)
            return dp(h, t)

    print(dp(N, T))
    #print(memo)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:



def dp(items, size_limit):
    n = len(items)
    flag = [[10**10]*(size_limit+1)for i in range(n+1)]
    table = [[0]*(size_limit+1)for i in range(n+1)]
    for i in range(1,n+1):
        target = items[i-1]
        w = target[0] * i + target[1] + 1
        for j in range(1,size_limit+1):
            yellow = table[i-1][j]
            table[i][j] = yellow
            if w > size_limit+0.5:
                continue
            pink = table[i-1][j-w]
            include_this = w + pink
            table[i][j] = max(yellow, include_this)
            flag[i][j] = include_this > yellow
    res = 0
    i = n
    j = size_limit
    while i > 0 and j > 0:
        if flag[i][j] is True:
            res += 1
            j -= w
        i -= 1
    return res

n, t = map(int, input().split(' '))
a = [list(map(int, input().split(' '))) for _ in range(n)]
print(dp(a,t))

Submission status: Runtime Error

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

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    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(30)] for j in xrange(2) ]
dp[0][0] = 0

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

    a, b = stores[i]
    for j in xrange(30):
        dp[q][j] = dp[p][j]
        if dp[p][j] == -INF:
            continue
        if j + 1 < 30:
            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 = j + 1
    p = q
print res

Submission status: Runtime Error

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

a, b = [0] * N, [0] * N

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

# greedfy
visited = [False] * N
t = 0
count = 0

while t < T + 0.5 and not all(visited):
  t += 1  # move
  if not t < T + 0.5:
    break
  costs = [(i * t + j, i, idx) for (idx, (i, j, v)) in enumerate(zip(a, b, visited)) if v == False]
  minCost, _, minIdx = sorted(costs)
  t += minCost
  if not t < T + 0.5:
    break
  visited[minIdx] = True
  #print(minCost, minIdx, visited)
  count += 1

print(count)

Submission status: Runtime Error

Solution code:
n,T=map(int,input().split())
INF=float('inf')
a0=[INF]
a1=[]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if a==0:
        a0.append(b)
    else:
        a1.append((a,b))
a0.sort(key=lambda x:-x)
while 1:
    if a0[-1]<=T//2:
        T-=a0.pop()+1
        ans+=1
    else:
        break
while T>0:
    a1.sort(key=lambda x:(T-x[1])//x[0])
    t=(T-a1[-1][1])//a1[-1][0]
    if T-a0[-1]>=t:
        T-=1+a0.pop()
        ans+=1
    else:
        T=t
        a1.pop()
        ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import deque


n = int(input())

info = [list(map(int, input().split())) for i in range(n - 1)]
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[root] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
    if visited[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

num1 = n // 3 
num2 = n // 3
num3 = n // 3
if n % 3 >= 1:
   num1 += 1
if n % 3 >= 2:
   num2 += 1
    
ans = [0] * n

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)
        
if cnt0 <= num3:
    for i in range(n):
        if visited[i] == 0:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  

elif cnt1 <= num3:
    for i in range(n):
        if visited[i] == 1:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  
else:
    num147 = 0
    num258 = 0
    num369 = 0
    for i in range(n):
        if visited[i] == 0:
            num = num147 * 3 + 1
            if num > n:
                num = num369 * 3 + 3
                ans[i] = num
                if num > n:
                    print(-1)
                    exit()
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 1, 4, 7, 10, ...
            set1.remove(num)
            num147 += 1
        else:
            num = num258 * 3 + 2 
            if num > n:
                num = num369 * 3 + 3
                if num > n:
                    print(-1)
                    exit()
                ans[i] = num
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 2, 5, 8, 11, ...
            set2.remove(num)
            num258 += 1
     
    for i in range(n):
        if ans[i] == 0:
            if set1:
                ans[i] = set1.pop()
            elif set2:
                ans[i] = set2.pop()
            elif set3:
                ans[i] = set3.pop()
print(*ans)

Submission status: Runtime Error

Solution code:
n,T=map(int,input().split())
INF=float('inf')
a0=[INF]
a1=[]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if a==0:
        a0.append(b)
    else:
        a1.append((a,b))
a0.sort(reverse==True)
while 1:
    if a0[-1]<=T//2:
        T-=a0.pop()+1
        ans+=1
    else:
        break
while T>0:
    a1.sort(key=lambda x:(T-x[1])//x[0])
    t=(T-a1[-1][1])//a1[-1][0])
    if T-a0[-1]<=t:
        T-=1+a0.pop()
        ans+=1
    else:
        T=t
        a1.pop()
        ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
def main():
    N,T = map(int,input().split())
    C = np.array([list(map(int,input().split(" "))) for _ in range(N)])
    t1 = 0
    t2 = float('inf')
    loop = set([i for i in range(N)])
    ans = 0
    while loop:
        for v in loop:
            a,b = C[v]
            if t2 > (a+1)*(t1+1)+b:
                use = {v}
                t2 = (a+1)*(t1+1)+b
        if t2 > T+0.5:
            break
        ans += 1
        t1 = int(t2)
        t2 = float('inf')
        loop -= use
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

t = 0
t += 1
i = 0
while True:
    tt = ab[i][0] * t + ab[i][1]
    t += tt

    #print('i:' + str(i) + ' t:' + str(t))
    if t > T:
        break

    i += 1
    t += 1


print(i)

Submission status: Runtime Error

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

def get_shortest_shop(t, shops):
    shortest_i = 0
    shortest_t = shops[0][0]*t + shops[0][1]

    for i, l in enumerate(shops):
        shop_t = l[0]*t + l[1]
        if shortest_t > shop_t:
            shortest_t = shop_t
            shortest_i = i
    
    return shortest_i, shortest_t


n, t_limit = map(int, input().split())
shops = []
for _ in range(n):
    shops.append(list(map(int, input().split())))

t = 1
shop_limit = 0
while t_limit > t:
    shortest_i, shortest_t = get_shortest_shop(t, shops)
    if t_limit >= t + shortest_t:
        t = t + shortest_t + 1
        del shops[shortest_i]
        shop_limit += 1
    else:
        break

print(shop_limit)

Submission status: Runtime Error

Solution code:
n,T=map(int,input().split())
ck=[]
times=[]
l=[]
t=0
s=0
count=0
for i in range(n):
    ak,bk=list(map(str,input().split()))
for i in range(n):
    l=[ak[i],bk[i]]
    ck.append(l)
nck=sorted(ck,reverse=True)
for i in range(n):
    for i in range(n):
        t+=1
        s=t*int(nck[i-1][0])+int(nck[i-1][1])
        t+=s
        count+=1
        if t>T:
            t-=s
            n-=1
            times.append(count)
            nck.remove(nck[0])
            break
print(max(times))

Submission status: Runtime Error

Solution code:
N,T = map(int, input().split())
a = [-1 for i in range(N)]
b = [-1 for i in range(N)]
dplist ={}


for i in range(N):
    a[i],b[i] = map(int, input().split())
c = zip(a,b)
c = sorted(c)

a,b = zip(*c)

def dynamic(n,t):
    global a
    global b
    global N
    global T 
    global dplist
    remained = T+0.5-t

    

    if n == N-1:
        res =0
    elif remained < a[n]*(t+1)+b[n]+1:
        res = dynamic(n+1,t)
    else:
        res = max(dynamic(n+1,t), dynamic(n+1,t+a[n]*(t+1)+b[n]+1)+1)

    dplist[(n,t)] = res
    return res

print(dynamic(0,0))

Submission status: Runtime Error

Solution code:
N = input()
N, T = N.split(' ')
T = int(T) + 0.5

ab = []
for i in list(range(int(N))):
    tmp = input()
    tmp = tmp.split(' ')

    ab.append({'a': int(tmp[0]), 'b': int(tmp[1])})

ab.sort(key=lambda x: (x['a'], x['b']), reverse=True)

ans = []
t = 0
before_c = 0
after_c = 0
i = 0
cond = True
check = False

while cond:
    while t <= T and len(ab) > i:
        t += 1
        while (ab[i]['a'] * t + ab[i]['b']) > T and len(ab) > i:
            i += 1
            check = True
        if check and len(ab) > i:
            check = False
            break
        t += ab[i]['a'] * t + ab[i]['b']
        if t <= T:
            after_c += 1
        i += 1
    if before_c <= after_c:
        before_c = after_c
        after_c = 0
    else:
        cond = False
    if len(ab) > 0:
        ab.pop(0)
    elif len(ab) is 0:
        break
    i = 0
    t = 0
print(before_c)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
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())

t=0
n=N
yet_arrived_store = list(range(N))
while t <= T:
        t+=1

        c = [] * n
        m=0
        for i in yet_arrived_store:
                c[m] = [a[i] * t + b[i], 1.0/(a[i]+1), i]
                m+=1

        c.sort()

        j=0
        while (j < n-1) and (c[j][2] not in yet_arrived_store):
                j += 1

        t+=c[j][0]

        if t > T:
                break

        next_arrived_store = c[j][2]
        yet_arrived_store.remove(next_arrived_store)
        n-=1

        if (n == 0):
                break

print(N-len(yet_arrived_store))

Submission status: Runtime Error

Solution code:
N,T = map(int, input().split())
a = [-1 for i in range(N)]
b = [-1 for i in range(N)]
dplist ={}


for i in range(N):
    a[i],b[i] = map(int, input().split())
c = zip(a,b)
c = sorted(c)

a,b = zip(*c)

def dynamic(n,t):
    global a
    global b
    global N
    global T 
    global dplist
    remained = T+0.5-t

    

    if n == N :
        res =0
    elif remained < a[n]*(t+1)+b[n]+1:
        res = dynamic(n+1,t)
    else:
        res = max(dynamic(n+1,t), dynamic(n+1,t+a[n]*(t+1)+b[n]+1)+1)

    dplist[(n,t)] = res
    return res

print(dynamic(0,0))

Submission status: Runtime Error

Solution code:
from operator import itemgetter


def calc(item, t):
    return sorted([[i[0], i[1], i[0] * t + i[1]] for i in item], key=itemgetter(2))

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

p = []
for n in range(N):
   a, b = map(int, input().strip().split())
   p.append([a, b, a+b])

p_sort = sorted(p, key=itemgetter(2))

max_count = 0
t_count = 1

item = p_sort.pop(0)
if max_count == 0 and T <= item[2]:
    print(max_count)

else:
    while True:
        t_count += item[2]
        if T + 0.5 <= t_count:
            break
        max_count += 1
        t_count += 1
        p_sort = calc(p_sort, t_count)
        item = p_sort.pop(0)

print(max_count)

Submission status: Runtime Error

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

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    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)

def multi(s1, s2):
    a1, b1 = s1
    a2, b2 = s2

    a3 = a1 + a2 + a1 * a2
    b3 = b1 + 1 + a2 * b1 + a2 + b2

    a3 = min(INF, a3)
    b3 = min(INF, b3)
    return (a3, b3)

rev = stores[:]
for i in xrange(n - 2, -1, -1):
    rev[i] = multi(rev[i], rev[i + 1])

cnt = 0
tick = 1
ptr = 0
qtr = 0
res = 0
while tick <= t and ptr < n:
    qtr = max(qtr, ptr)
    while True:
        (a, b) = rev[qtr]
        u = a * tick + b
        if tick + u <= t:
            res = max(res, ptr + n - qtr)
            break
        else:
            qtr += 1

    (a, b) = stores[ptr]
    #print (a, b)
    ptr += 1

    tt = a * tick + b
    if tick + tt > t:
        break
    tick += tt + 1
    #print tick, t, a, b, ptr, n
print res

Submission status: Runtime Error

Solution code:
N,T = map(int, input().split())
a = [-1 for i in range(N)]
b = [-1 for i in range(N)]
dplist ={}


for i in range(N):
    a[i],b[i] = map(int, input().split())
c = zip(a,b)
c = sorted(c)

a,b = zip(*c)

def dynamic(n,t):
    global a
    global b
    global N
    global T 
    global dplist
    remained = T+0.5-t

    if (n,t)in dplist:
        return dplist[(n,t)]

    if n == N :
        res =0
    elif remained < a[n]*(t+1)+b[n]+1:
        res = dynamic(n+1,t)
    else:
        res = max(dynamic(n+1,t), dynamic(n+1,t+a[n]*(t+1)+b[n]+1)+1)

    dplist[(n,t)] = res
    return res

print(dynamic(0,0))

Submission status: Runtime Error

Solution code:
N,T = map(int, input().split())
a = [-1 for i in range(N)]
b = [-1 for i in range(N)]
dplist ={}


for i in range(N):
    a[i],b[i] = map(int, input().split())
c = zip(a,b)
c = sorted(c)

a,b = zip(*c)

def dynamic(n,t):
    global a
    global b
    global N
    global T 
    global dplist
    remained = T+0.5-t

    if (n,t)in dplist:
        return dplist[(n,t)]

    if n == N :
        res =0
    elif remained < a[n]*t+b[n]+1:
        res = dynamic(n+1,t)
    else:
        res = max(dynamic(n+1,t), dynamic(n+1,t+a[n]*t+b[n]+1)+1)

    dplist[(n,t)] = res
    return res

print(dynamic(0,0))

Submission status: Runtime Error

Solution code:
N,T  = int(input().split())
a = []
b = []
c = []
for i in range(N):
    a[i] , b[i] = int(input().split())
    c[i] = a[i] + b[i]
min_time = []

min_time[0] = 0

for t in range(1, T+1):

    for j in range(N):
        c[j] = a[j] * t + b[j]

    min_time[t] = min_time[t-1] + min(c)

    
print(min_time[T])

Submission status: Runtime Error

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

ab = []

class MyClass:
    def __init__(self, a, b): 
        self.a = a     
        self.b = b

    def calc(self, t):   
        #print("a: {}, b: {}".format(a,b))
        n = self.a * t + self.b
        return n

    def disp(self):
        print(self.a, self.b)

if __name__ == "__main__":

    for i in range(N):
        a, b = map(int, input().split())
        ab.append(MyClass(a, b))

    cnt = 0
    t = 0

    while True:
        t = t + 1
        T = T - 1

        tmp = 100000000

        for i in ab:
            if i.calc(t) < tmp:
                tmp = i.calc(t)
                tmp_i = i

        ab.remove(tmp_i)

        T = T - tmp
        if T < 0:
            break

        cnt = cnt + 1

        if len(ab) == 0:
            break
    print(cnt)

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())
a = []
b = []
for i in range(0, N):
  ai, bi = map(int, input().split())
  a.append(ai)
  b.append(bi)

t = 0
n = 0
visited = set()
while(True):
  next_min_cost = T*2
  for i in range(0, len(a)):
    if(i in visited):
      continue
    tmp = 1 + a[i] * (t+1) + b[i]
    if (tmp < next_min_cost):
      next_min_cost = tmp
      next_min_idx = i
  if (t + next_min_cost > T):
    break
  n = n + 1
  visited.add(next_min_idx)
  t += next_min_cost
  #print('visit', next_min_idx, next_min_cost, t)

print(n)

Submission status: Runtime Error

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

if not AB1:
    raise

def sort_func(ab0, ab1):
    a0, b0 = ab0
    a1, b1 = ab1
    return a1*b0 - a0*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)

Submission status: Runtime Error

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

def main(N, T, lst_shop):

    dp  = [[0] * (T+10) for i in range(2)]
    ans = 0

    for i in range(N):
        
        if i % 2 == 0:
            idx      = 0
            idx_next = 1
        else:
            idx      = 1
            idx_next = 0

        for t in range(T):

            t_need = lst_shop[i][0] * t + lst_shop[i][1] + 1

            try:
                dp[idx_next][t+t_need] = max(dp[idx][t] + 1, dp[idx][t])
            except IndexError:
                pass
                
            # if t >= t_need:
            #     dp[idx_next][t] = max(dp[idx][t-t_need] + 1, dp[idx][t])
            # else:
            #     dp[idx_next][t] = dp[idx][t]

            ans = max(ans, dp[idx_next][t])
        
        for t in range(T): dp[idx][t] = 0

    return ans

if __name__ == "__main__":

    answer = main(N, T, lst_shop)
    print(answer)