Problem:


Score : 300 points

Problem Statement

We have two desks: A and B. Desk A has a vertical stack of N books on it, and Desk B similarly has M books on it.

It takes us A_i minutes to read the i-th book from the top on Desk A (1 \leq i \leq N), and B_i minutes to read the i-th book from the top on Desk B (1 \leq i \leq M).

Consider the following action:

Choose a desk with a book remaining, read the topmost book on that desk, and remove it from the desk.

How many books can we read at most by repeating this action so that it takes us at most K minutes in total? We ignore the time it takes to do anything other than reading.

Constraints

1 \leq N, M \leq 200000

1 \leq K \leq 10^9

1 \leq A_i, B_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M

Output

Print an integer representing the maximum number of books that can be read.

Sample Input 1

3 4 240
60 90 120
80 150 80 150

Sample Output 1

3

In this case, it takes us 60, 90, 120 minutes to read the 1-st, 2-nd, 3-rd books from the top on Desk A, and 80, 150, 80, 150 minutes to read the 1-st, 2-nd, 3-rd, 4-th books from the top on Desk B, respectively.

We can read three books in 230 minutes, as shown below, and this is the maximum number of books we can read within 240 minutes.

Read the topmost book on Desk A in 60 minutes, and remove that book from the desk.

Read the topmost book on Desk B in 80 minutes, and remove that book from the desk.

Read the topmost book on Desk A in 90 minutes, and remove that book from the desk.

Sample Input 2

3 4 730
60 90 120
80 150 80 150

Sample Output 2

7

Sample Input 3

5 4 1
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000

Sample Output 3

0

Watch out for integer overflows.



Sample input:
3 4 240
60 90 120
80 150 80 150


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int, input().split())

A=list(map(int, input().split()))
B=list(map(int, input().split()))
cnt=0
cntmax=0
sumA=[0]
sumB=[0]
cntA=0
cntB=0

for i in range(N):
  cntA+=A[i]
  if cntA>K:
    break
  else:
    sumA.append(cntA)
for i in range(M):
  cntB+=B[i]
  if cntB>K:
    break
  else:
    sumB.append(cntB)
#print(sumA,sumB)

N=len(sumA)
M=len(sumB)

for i in range(N):
  for j in range(M):
    if sumA[i]+sumB[j]<=K:
      cnt=i+j
      if cnt>=cntmax:
        cntmax=cnt
    else:
      break
print(cntmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = deque(A)
B = deque(B)

ans = 0
left_time = K
while True:
    # 本が両方の机からなくなったら終了
    if len(A) == 0 and len(B) == 0:
        break

    # Aだけ本が残っている場合
    if len(A) != 0 and len(B) == 0:
        val = A.popleft()
    # Bだけ本が残っている場合
    elif len(A) == 0 and len(B) != 0:
        val = B.popleft()
    else:
        n_A = 0
        sum_A = 0
        for a in A:
            if sum_A >= left_time:
                break
            n_A += 1
            sum_A += a
        n_B = 0
        sum_B = 0
        for b in B:
            if sum_B >= left_time:
                break
            n_B += 1
            sum_B += b
        if n_A >= n_B:
            val = A.popleft()
        else:
            val = B.popleft()
    left_time -= val
    if left_time < 0:
        break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')

n, m, k = rm()
a = rl()
b = rl()

cnt = 0
lena = len(a)
lenb = len(b)
dp = [[inf]*(lenb + 1) for _ in range(lena + 1)]
dp[0][0] = 0
dp[0][1] = b[0]
dp[1][0] = a[0]

for i in range(lena):
    for j in range(lenb):
        dp[i][j+1] = dp[i][j] + b[j]
        dp[i+1][j] = dp[i][j] + a[i]
        if dp[i][j+1] <= k or dp[i+1][j] <= k:
            cnt = max(i+j+1, cnt)
else:
    if dp[lena][lenb-1] + b[lenb-1] <= k:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# C - Tsundoku
import sys
sys.setrecursionlimit(10**9)

N, M, K = map(int, input().split())
A = list(int(a) for a in input().split())
B = list(int(b) for b in input().split())
la = len(A)
lb = len(B)
T = 0
r = 0
ans = 0
def dfs(i, j, T, r):
    global ans
    ans = max(ans, r)
    if i < la and T+A[i] <= K:
        dfs(i+1, j, T+A[i], r+1)
    if j < lb and T+B[j] <= K:
        dfs(i, j+1, T+B[j], r+1)
    return

dfs(0, 0, T, 0)
print(ans)

Submission status: Time Limit Exceeded

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

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    if sum(A) + sum(B) < K:
        print(N + M)
        return
    weightA = 0
    tmp_A = N
    for idx, a in enumerate(A):
        if weightA + a > K:
            tmp_A = idx
            break
        else:
            weightA += a
    max_count = current_count = tmp_A
    len_A = tmp_A

    weightB = 0
    terminated = False
    for b in B:
        if terminated == True and weightA + weightB > K:
            break

        if len_A==0 and weightA + weightB + b > K:
            break

        if weightA + weightB + b <= K:
            weightB += b
            current_count += 1

        elif terminated==False:
            while weightA + weightB + b > K:
                if len_A>0:
                    weightA -= A[len_A-1]
                    len_A -= 1
                    current_count -= 1
                else:
                    terminated=True

            if weightA + weightB + b <= K:
                weightB += b
                current_count += 1
        max_count = max(max_count, current_count)


    print(max_count)
    return


def solve_old(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    weightA = 0
    tmp_A = N
    for idx, a in enumerate(A):
        if weightA + a > K:
            tmp_A = idx
            break
        else:
            weightA += a
    max_count = current_count = tmp_A
    len_A = tmp_A

    weightB = 0
    terminated = False
    for b in B:
        if terminated == True and weightA + weightB > K:
            break

        if len_A==0 and weightA + weightB + b > K:
            break

        if weightA + weightB + b <= K:
            weightB += b
            current_count += 1

        elif terminated==False:
            while weightA + weightB + b > K:
                if len_A>0:
                    weightA -= A[len_A-1]
                    len_A -= 1
                    current_count -= 1
                else:
                    terminated=True

            if weightA + weightB + b <= K:
                weightB += b
                current_count += 1
        max_count = max(max_count, current_count)

    print(max_count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, K, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

SA = [0]*(N+1)
SB = [0]*(M+1)
SA[0] = 0
SB[0] = 0
for i in range(1,N+1):
    SA[i] = SA[i-1] + A[i-1]
for i in range(1,M+1):
    SB[i] = SB[i-1] + B[i-1]
j = 0
k = 0
ans = 0
for j in range(N+1):
    for k in range(M+1):
        if SA[j] + SB[k] <= K:
            ans = max(ans, j + k)
    
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K= map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
A.insert(0,0)
ans = 0
for n in range(N+1):
    K -= A[n]
    t = K
    book = n
    if t < 0:
        break
    else:
        for m in range(M):
            if t >= B[m]:
                t -= B[m]
                book += 1
            else:
                if ans < book:
                    ans = book
                break
        if ans < book:
            ans = book
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = 0
a_book = 0
min = 0

for i in range(n+1):
    book = a_book
    now = min

    for j in range(m+1):
        if now > k:
            ans = max(ans,book-1)
            break

        if j == m:
            ans = max(ans, book)
            break

        now += b[j]
        book += 1

    if min > k or i == n:
        break
    a_book += 1
    min += a[i]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

if min(A[0],B[0])>K:
  print(0)
  exit()

c=[0 for _ in range(N)] + [1 for _ in range(M)]
C=list(permutations(c,len(c)))

for i in range(len(C)):
  countA=N
  countB=M
  ans=K
  answer=0
  for j in range(len(c)):
    if C[i][j]==0:
      ans-=A[countA-1]
      countA-=1
    else:
      ans-=B[countB-1]
      countB-=1
    if ans<=0:
      if N+M-(countA+countB)>answer:
        answer=N+M-(countA+countB)
        break
      else:
        break
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, maxsize

def main():
    n, m, k = [int(x) for x in stdin.readline().rstrip().split()]
    canread = [maxsize] *(n+m+2)

    pileda = 0
    a = [0]
    for x in stdin.readline().rstrip().split():
        x = int(x)
        pileda += x
        if pileda > k:
            break
        a.append(pileda)
        
    
    piledb = 0
    b = [0]
    for x in stdin.readline().rstrip().split():
        x = int(x)
        piledb += x
        if piledb > k:
            break
        b.append(piledb)

    for ai, at in enumerate(a):
        for bi, bt in enumerate(b):
            if at + bt > k:
                break
            if canread[ai+bi] > at+bt:
                canread[ai+bi] = at+bt
    ans = 0
    for i, time in enumerate(canread):
        if time > k:
            break
        ans = i
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

a = list(accumulate(a))
a.insert(0,0)
b = list(accumulate(b))
b.insert(0,0)

for i in range(n+m+1):

    p = [a[s]+b[i-s] for s in range(max(0,i-m),min(i,n)+1)]
    o = min(p)
    if o > k:
        print(i-1)
        break

else:
    print(n+m)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))

A_sum = [0]
B_sum = [0]

for a in A_list:
    A_sum.append(A_sum[-1] + a)

for b in B_list:
    B_sum.append(B_sum[-1] + b)

count = 0
for i, a in enumerate(A_sum):
    for j, b in enumerate(B_sum):
        if a + b <= K:
            if count < i + j:
                count = i + j
        else:
            break

print(count)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

N, M, K = map(int, input().split())

A = input().split()
B = input().split()

que = deque([(0, K, A, B)])

max_count = 0

while que:
    count, k, a, b = que.popleft()
    max_count = max(max_count, count)
    
    if a and 0 <= k-int(a[0]):
        que.appendleft((count+1, k-int(a[0]), a[1:], b))
    if b and 0 <= k-int(b[0]):
        que.appendleft((count+1, k-int(b[0]), a, b[1:]))

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [False]*N
b = [False]*M

ans = 0
now = 0
bf = 0

for i in range(N):
    if now + A[i] > K:
        break
    now += A[i]
    ans += 1
    a[i] = True

for i in range(M):
    if now + B[i] > K:
        break
    now += B[i]
    ans += 1
    b[i] = True
    bf = i

if all(a) and all(b):
    print(ans)
    exit()

if not any(a) and not any(b):
    print(ans)
    exit()

n = K - now
ans2 = ans
for i in reversed(range(N)):
    if a[i]:
        a[i] = False
        n += A[i]
        ans2 -= 1
        for j in range(bf,M):
            if not b[j]:
                if n - B[j] < 0:
                    break
                b[j] = True
                n -= B[j]
                ans2 += 1
    if ans2 > ans:
        ans = ans2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

import sys #追加
sys.setrecursionlimit(500*500) #追加


ans = [0]
memo = set()
import copy

def dfs(now_sum,i,j,cnt,memo1):
    if memo1 in memo:
        return
    # print(now_sum)
    # if ans[0] <= cnt:
    #     return
    if now_sum > K:
        # print("a")
        cnt -= 1
        ans[0] = max(ans[0],cnt)
        return

    
    
    # if i == N or j== M:
        # print("b")
        # print(now_sum,i,j)
    # ans[0] = max(ans[0],cnt)
        # return

    if i < N:
        memo_c = copy.deepcopy(memo1)
        memo.add((memo_c[0]+1,memo_c[1]))
        dfs(now_sum + A[i],i+1,j,cnt+1,memo_c)
    if j < M:
        memo_d = copy.deepcopy(memo1)
        memo.add((memo_d[0],memo_d[1]+1))
        dfs(now_sum + B[j],i,j+1,cnt+1,memo_d)
    ans[0] = max(ans[0],cnt)
    


dfs(0,0,0,0,(0,0))

print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    N,M,K = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()]
    B = [int(i) for i in input().strip().split()]

    pre_A = [0] * (N + 1)
    pre_B = [0] * (M + 1)


    for i in range(1,N+1):
        pre_A[i] = pre_A[i-1] + A[i-1]
        if pre_A[i] > K:
            idx_a = i-1
            break
    else:
        idx_a = N

    for i in range(1,M+1):
        pre_B[i]= pre_B[i-1] + B[i-1]
        if pre_B[i] > K:
            idx_b = i-1
            break
    else:
        idx_b = M

    ans = max(idx_a,idx_b)

    for i in range(idx_a + 1):
        for j in range(idx_b+1): 
            if pre_A[i] + pre_B[j] <= K:
                ans = max(ans,i+j)
            else:
                break

    return ans

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

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

class Node:
  def __init__(self, i, j, cur, total):
    self.i = i
    self.j = j
    self.cur = cur
    self.total = total
  def child(self):
    results = []
    if self.i + 1 < N and self.cur + A[self.i+1] <= K:
      results.append(Node(self.i+1, self.j, self.cur+A[self.i+1], self.total + 1))
    if self.j + 1 < M and self.cur + B[self.j+1] <= K:
      results.append(Node(self.i, self.j+1, self.cur+B[self.j+1], self.total + 1))
    return results
  def __repr__(self):
    return str([self.i, self.j, self.cur, self.total])
  
nodes = [Node(-1,-1,0,0)]
max_total = 0
while True:
  if len(nodes) == 0: break
  cur = nodes.pop()
  if cur.total > max_total: max_total = cur.total
  children = cur.child()
  nodes.extend(children)
  
print(max_total)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit( 10 ** 8 )

n, m, k = map( int, input().split() )
a = list( map( int, input().split() ) )
b = list( map( int, input().split() ) )

a.append( 10 ** 9 + 1 )
b.append( 10 ** 9 + 1 )

def dp( i, j, t ):
    next_i = min( i + 1, n )
    next_j = min( j + 1, m )
    if a[ i ] + t > k and b[ j ] + t > k:
        return 0
    elif a[ i ] + t > k:
        return dp( i, next_j, t + b[ j ] ) + 1
    elif b[ j ] + t > k:
        return dp( next_i, j, t + a[ i ] ) + 1
    else:
        r_i = dp( next_i, j, t + a[ i ] )
        r_j = dp( i, next_j, t + b[ j ] )
        return max( r_i, r_j ) + 1

read = dp( 0, 0, 0 )
    
print( read )

Submission status: Time Limit Exceeded

Solution code:
info = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

N = list()
M = list()
N.append(0)
for i in range(info[0]):
  N.append(N[i]+A[i])
M.append(0)
for i in range(info[1]):
  M.append(M[i]+B[i])

t = info[0]
n = 2
while True:
  if N[int(info[0]/n)] > info[2]:
    t = int(info[0]/n)
    break
  else:
    n += 1
  
ans = 0
for i in range(t, -1, -1):
  if N[i] > info[2] :
    continue
  if i+info[1] <= ans:
    break
  for j in range(info[1], -1, -1):
    if i+j <= ans:
      break
    if N[i]+M[j] <= info[2]:
      ans = i+j
      break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[47]:


N,M,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


# In[56]:


A_sum = [sum(A[:i]) for i in range(N+1)]
B_sum = [sum(B[:i]) for i in range(M+1)]
ans = 0
for a in range(N+1):
    if A_sum[a] > K:
        break
    for b in range(M+1):
        if A_sum[a] + B_sum[b] > K:
            break
        ans = max(ans, a+b)
print(ans)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))
 
def get_bcnt( usek,tb=tb ):
    t = 0
    cnt = 0
    try:
        while True:
            if t + tb[cnt] > usek:
                return cnt
            else:
                t += tb[cnt]
                cnt += 1
    except:
        return len(tb)
 
sumta = 0
readbook = [get_bcnt(k)] 
for i in range(na):
    sumta += ta[i]
    if sumta > k:
        break
    if ta[i] <= k:
        readbook.append( i+1 + get_bcnt( k - sumta ) )
 
print( max(readbook) )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from typing import List
from collections import deque

dp = {}


def solve(K: int, A: "List[int]", B: "List[int]"):
    queue = deque()
    if A[0] <= K: queue.append((K, 0, 0, 0))
    if B[0] <= K: queue.append((K, 0, 0, 0))
    # i, j = 0, 0
    c_max = 0
    while queue:
        rem, dep, i, j = queue.popleft()
        # if c <= rem:
        c_max = max(c_max, dep)
        # rem -= c
        dp[f'{i}_{j}'] = True
        if i < len(A) and A[i] <= rem and f'{i+1}_{j}' not in dp:
            queue.append((rem - A[i], dep + 1, i + 1, j))
        if j < len(B) and B[j] <= rem and f'{i}_{j+1}' not in dp:
            queue.append((rem - B[j], dep + 1, i, j + 1))
    return c_max


def solve3(K: int, A: "List[int]", B: "List[int]"):
    cost_a = calc_cost(A)
    cost_b = calc_cost(B)
    i, j = 0, 0
    c = K
    num = 0
    print(cost_a)
    print(cost_b)
    while i < len(cost_a) or j < len(cost_b):
        tmp = []
        if i == len(cost_a) or cost_b[j] < cost_a[i]:
            if c < B[j]:
                break
            c -= B[j]
            j += 1
        elif j == len(cost_b) or cost_a[i] < cost_b[j]:
            if c < A[i]:
                break
            c -= A[i]
            i += 1
        else:
            print('????', i, j)
        num += 1

    return num

def calc_cost(list):
    l2 = [0 for _ in list]
    pre = 0
    for i in range(len(list)):
        j = len(list) - 1 - i
        l2[j] = pre + list[j]
        pre = l2[j]
    return l2

def solve2(K: int, A: "List[int]", B: "List[int]"):
    if K == 0: return 0

    r = _solve(0, K, A, B, 0, 0)
    return r


def _solve(current:int, K: int, A: "List[int]", B: "List[int]", i, j):
    key = f'{i}_{j}'
    if key in dp: return dp[key]

    res = [current]
    if i < len(A) and A[i] <= K:
        res.append(_solve(current + 1, K - A[i], A, B, i + 1, j))

    if j < len(B) and B[j] <= K:
        res.append(_solve(current + 1, K - B[j], A, B, i, j + 1))

    dp[key] = max(res)
    return dp[key]


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # def iterate_tokens():
    #     for line in sys.stdin:
    #         for word in line.split():
    #             yield word
    # tokens = iterate_tokens()
    # N = int(next(tokens))  # type: int
    # M = int(next(tokens))  # type: int
    # K = int(next(tokens))  # type: int
    # A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    # B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    N, M, K = [int(k) for k in input().split()]
    A = [int(k) for k in input().split()]
    B = [int(k) for k in input().split()]
    print(solve(K, A, B))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M,K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

if len(A)>len(B):
    tmp = B[:]
    B = A
    A = tmp
    tmp = M
    M = N
    N = tmp

Acum = np.cumsum(np.array(A))
Bcum = np.cumsum(np.array(B))

maxnum = 0
for n in range(N,-1,-1):
    if n>0:
        tA = Acum[n-1]
    else:
        tA = 0
    if tA>K:
        continue
    
    for m in range(M,-1,-1):
        if m>0:
            tB = Bcum[m-1]
        else:
            tB = 0
        
        if tA+tB<=K:
            num = n+m
            if num>maxnum:
                maxnum = num
            break

print(maxnum)

Submission status: Time Limit Exceeded

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import random

N, M, K = MAP()
A = LIST()
B = LIST()

# N = random.randint(1, 200000)
# M = random.randint(1, 200000)
# K = random.randint(1, 10**9)
# A = [random.randint(1, 10**5) for _ in range(N)]
# B = [random.randint(1, 10**5) for _ in range(M)]
# print(N,M,K)

# def dfs(AorB, A_idx, B_idx, time_left, n_book):
#     if AorB == "A":
#         if A_idx >= N:
#             return n_book
#         if A[A_idx] > time_left:
#             return n_book
#         time_left -= A[A_idx]
#         A_idx += 1
#         n_book += 1

#     else:
#         if B_idx >= M:
#             return n_book
#         if B[B_idx] > time_left:
#             return n_book
#         time_left -= B[B_idx]
#         B_idx += 1
#         n_book += 1


#     n_book = max(
#         dfs("A", A_idx, B_idx, time_left, n_book),
#         dfs("B", A_idx, B_idx, time_left, n_book),
#         )
#     return n_book

# print(max(dfs("A", 0, 0, K, 0), dfs("B", 0, 0, K, 0)))


DP = [[0] * (N+1) for _ in range(M+1)]
ans = 0
for b in range(1, M+1):
    weight = DP[b-1][0] + B[b-1]
    if weight > K:
        break
    DP[b][0] = weight
    ans = b

b_range = ans+1
for b in range(b_range):
    for a in range(1, N+1):
       weight = DP[b][a-1] + A[a-1]
       if weight > K:
           break
       DP[b][a] = weight
       ans = max(ans, a+b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
X = N + M
sum_n = 0
sum_m = 0
ans = 0
flag = False
for i in reversed(range(1,X+1)):
    if(flag):
        break
    for j in range(i+1):
        n = j
        m = i - j
        if(n <= N and m <= M):
            sum_n = sum(A[0:n])
            sum_m = sum(B[0:m])
            if((sum_m + sum_n) <= K):
                ans=i
                flag =True
                break
            sum_m = 0
            sum_n = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = list(map(int,input().strip().split()))
a = list(map(int,input().strip().split()))
b = list(map(int,input().strip().split()))

ar_time = 0
a_sum = [0]
b_sum = [0]
for i in a:
  ar_time += i
  if k < ar_time:
    ar_time -= i
    break
  else:
    a_sum.append(ar_time)
br_time = 0
for i in b:
  br_time += i
  if k < br_time:
    break
  else:
    b_sum.append(br_time)
max_count = 0
for a_count,_a in enumerate(a_sum):
  for b_count,_b in enumerate(b_sum):
    if _a + _b <= k:
      if max_count < a_count + b_count:
        max_count = a_count + b_count
    else:
      break
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
def ABC172_C():
    import sys
    sys.setrecursionlimit(4100000)

    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    if k < a[0] or k < b[0]:
        print(0)
        return

    minamo = []
    def saiki(i,j,sum,mx):
        if sum > k:
            mx = min(i+j,mx)
            return mx

        elif sum == k:
            mx = min(i+j,mx)
            return mx

        if i+j >= mx:
            return mx

        if i+1 <= n:
            mx = saiki(i+1,j,sum+a[i],mx)
        if j+1 <= m:
            mx = saiki(i,j+1,sum+b[j],mx)

        return mx

    mls = saiki(0,0,0,pow(10,5))
    print(mls)
ABC172_C()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from typing import List
from collections import deque

dp = {}


def solve(K: int, A: "List[int]", B: "List[int]"):
    queue = deque()
    if A[0] <= K: queue.append((K, 0, 0, 0))
    if B[0] <= K: queue.append((K, 0, 0, 0))
    # i, j = 0, 0
    c_max = 0
    while queue:
        rem, dep, i, j = queue.popleft()
        # if c <= rem:
        c_max = max(c_max, dep)
        # rem -= c
        key = f'{i}_{j}'
        if i < len(A) and A[i] <= rem and key not in dp:
            queue.append((rem - A[i], dep + 1, i + 1, j))
        if j < len(B) and B[j] <= rem and key not in dp:
            queue.append((rem - B[j], dep + 1, i, j + 1))
        dp[key] = True
    return c_max


def solve3(K: int, A: "List[int]", B: "List[int]"):
    cost_a = calc_cost(A)
    cost_b = calc_cost(B)
    i, j = 0, 0
    c = K
    num = 0
    print(cost_a)
    print(cost_b)
    while i < len(cost_a) or j < len(cost_b):
        tmp = []
        if i == len(cost_a) or cost_b[j] < cost_a[i]:
            if c < B[j]:
                break
            c -= B[j]
            j += 1
        elif j == len(cost_b) or cost_a[i] < cost_b[j]:
            if c < A[i]:
                break
            c -= A[i]
            i += 1
        else:
            print('????', i, j)
        num += 1

    return num

def calc_cost(list):
    l2 = [0 for _ in list]
    pre = 0
    for i in range(len(list)):
        j = len(list) - 1 - i
        l2[j] = pre + list[j]
        pre = l2[j]
    return l2

def solve2(K: int, A: "List[int]", B: "List[int]"):
    if K == 0: return 0

    r = _solve(0, K, A, B, 0, 0)
    return r


def _solve(current:int, K: int, A: "List[int]", B: "List[int]", i, j):
    key = f'{i}_{j}'
    if key in dp: return dp[key]

    res = [current]
    if i < len(A) and A[i] <= K:
        res.append(_solve(current + 1, K - A[i], A, B, i + 1, j))

    if j < len(B) and B[j] <= K:
        res.append(_solve(current + 1, K - B[j], A, B, i, j + 1))

    dp[key] = max(res)
    return dp[key]


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # def iterate_tokens():
    #     for line in sys.stdin:
    #         for word in line.split():
    #             yield word
    # tokens = iterate_tokens()
    # N = int(next(tokens))  # type: int
    # M = int(next(tokens))  # type: int
    # K = int(next(tokens))  # type: int
    # A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    # B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    N, M, K = [int(k) for k in input().split()]
    A = [int(k) for k in input().split()]
    B = [int(k) for k in input().split()]
    print(solve(K, A, B))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))


ll = [(0, 0, 0)]
ans = 0

while len(ll) > 0:
    c, an, bn = ll.pop()
    if an < n:
        if c+a[an] <= k:
            ll.append((c+a[an], an+1, bn))
        elif an + bn > ans:
            ans = an+bn
    else:
        if an + bn > ans:
            ans = an+bn

    if bn < m:
        if c+b[bn] <= k:
            ll.append((c+b[bn], an, bn+1))
        elif an + bn > ans:
            ans = an+bn
    else:
        if an + bn > ans:
            ans = an+bn
    ll = list(set(ll))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int, input().split())

A=list(map(int, input().split()))
B=list(map(int, input().split()))
cnt=0
cntmax=0
sumA=[0]
sumB=[0]
cntA=0
cntB=0

for i in range(N):
  cntA+=A[i]
  if cntA>K:
    break
  else:
    sumA.append(cntA)
for i in range(M):
  cntB+=B[i]
  if cntB>K:
    break
  else:
    sumB.append(cntB)
#print(sumA,sumB)

N=len(sumA)
M=len(sumB)

for i in range(N):
  for j in range(M):
    if sumA[i]+sumB[j]<=K:
      cnt=i+j
      if cnt>=cntmax:
        cntmax=cnt
print(cntmax)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
n_a = 0
n_b = 0
t_a = 0
t_b = 0

for i in range(N):
    if sum(A[0:i + 1]) <= K:
        n_a += 1
        t_a += A[i]
        continue
    else:
        break
# print(n_a)
# print(t_a)

for i in range(M):
    if sum(B[0:i + 1]) <= K:
        n_b += 1
        t_b += B[i]
        continue
    else:
        break
# print(n_b)
# print(t_b)

if n_a >= n_b:
    n_b = 0
    t_b = 0
    for i in range(M):
        if sum(B[0:i + 1]) <= K - t_a:
            n_b += 1
            t_b += B[i]
            continue
        else:
            break
    # print(n_b)
    # print(t_b)

else:
    n_a = 0
    t_a = 0
    for i in range(N):
        if sum(A[0:i + 1]) <= K - t_b:
            n_a += 1
            t_a += A[i]
            continue
        else:
            break
    # print(n_a)
    # print(t_a)

print(n_a + n_b)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ai = 0
bi = 0
d = []
d.append((0, 1))
d.append((1, 0))

dic = {}
dic[(0,0)] = 0
ans = 0
while len(d) != 0:
  t = d.pop()
  
  if t in dic:
    continue
    
  if (t[0]-1, t[1]) in dic:
    tmp = dic[(t[0]-1, t[1])]
    time = tmp + a[t[0]-1]
    
  else:
    tmp = dic[(t[0], t[1]-1)]
    time = tmp + b[t[1]-1]
    
  dic[t] = time
  if time <= k:
    ans = max(ans, t[0]+t[1])
    if t[0] < n and (t[0]+1, t[1]) not in dic:
      d.append((t[0]+1, t[1]))

    if t[1] < m and (t[0], t[1]+1) not in dic:
      d.append((t[0], t[1]+1))
  
print(ans)