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

Solution code:
def check(A,B,a,b,MAX):
    if A[a] == MAX:
        return False
    elif B[b] == MAX:
        return True
    
    if A[a] == B[b]:
        return check(A,B,a+1,b+1,MAX)
    elif A[a] < B[b]:
        return True
    else:
        return False

N, M, K = map(int, input().split(" "))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
MAX = 10 ** 9 + 7
A.append(MAX)
B.append(MAX)
a, b, time = 0, 0, 0
for i in range(0,len(A)+len(B)-1):
#     print(A[a],B[b])
    if A[a] == B[b]:
        if A[a] == MAX:
            break
        if check(A,B,a+1,b+1,MAX):
            time += A[a]
            a += 1
        else:
            time += B[b]
            b += 1
    elif A[a] <= B[b]:
        time += A[a]
        a += 1
    else:
        time += B[b]
        b += 1
    if time > K:
        break
#     print(time)
print(i)

Submission status: Runtime Error

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

ans = 0
def dfs(a, b, k):
	global ans

	if a == N and b == M:
		return True

	if k < 0:
		return False

	if a < N and k >= A[a] and dfs(a + 1, b, k - A[a]):
		ans += 1
		return True

	if b < M and k >= B[b] and dfs(a, b + 1, k - B[b]):
		ans += 1
		return True

	return True

dfs(0, 0, K)
print(ans)

Submission status: Runtime Error

Solution code:
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
while True:
    if len(a) and len(b):
        if a[0] < b[0] and k >= a[0]:
            k-=a[0]
            del a[0]
            ans+=1
        elif a[0] >= b[0] and k >= b[0]:
            k-=b[0]
            del b[0]
            ans+=1
        else:
            print(ans)
            exit()
    elif len(a)==0 and k >= b[0]:
        k-=b[0]
        del b[0]
        ans+=1
    elif len(b)==0 and a[0] <= k:
        k-=a[0]
        del a[0]
        ans+=1
    else:
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(200000000)

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


def dfs(curr_a, curr_b, choice, time_required, count):
    global max_num
    if choice == 0:
        if curr_a >= N - 1:
            if max_num < count:
                max_num = count
            return
        else:
            curr_a += 1
            time_required += a[curr_a]
    else:
        if curr_b >= M - 1:
            if max_num < count:
                max_num = count
            return
        else:
            curr_b += 1
            time_required += b[curr_b]
    if time_required > K:
        return
    count += 1
    if max_num < count:
        max_num = count
    dfs(curr_a, curr_b, 0, time_required, count)
    dfs(curr_a, curr_b, 1, time_required, count)


if sum(a) + sum(b) <= K:
    print(N + M)
else:
    curr_a = -1
    curr_b = -1
    time_required = 0
    count = 0
    dfs(curr_a, curr_b, 0, time_required, count)
    curr_a = -1
    curr_b = -1
    time_required = 0
    count = 0
    dfs(curr_a, curr_b, 1, time_required, count)
    print(max_num)

Submission status: Runtime Error

Solution code:
n, m, c  = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

# まずはAの本棚を全部よみ、一つずつBの数値をあげる
check_list = []
read_time = 0
a_index = 0
for i, value in enumerate(a_list):
    a_index = i + 1
    read_time += value
    if read_time > c: # タイムを超えたら
        read_time -= value
        a_index -= 1
        break
    

read_book = a_index  # Aの読んだ本
b_index = 0
a_read_book_list = a_list[:read_book]
a_read_book_list.reverse()

"""
# Bを加えてオーバーするなら、オーバーする前の数値をリストに入れて、Aの上から一つ取り除く
for i, value in enumerate(b_list):
    b_index = i + 1 # first = 1
    # read_time += value
    if read_time + value > c:
        b_index -= 1
        check_list.append(len(a_read_book_list)+b_index)
        
        read_time -= a_read_book_list[-1]
    else:
        read_time += value
"""
flag_last = False
for i, value in enumerate(a_read_book_list):
    while read_time <= c:
        if b_index >= len(b_list):
            flag_last = True
            break
        read_time += b_list[b_index]
        b_index += 1

    if flag_last == False:
        read_time -= b_list[b_index]
        b_index -= 1

    flag = False

    check_list.append(len(a_read_book_list)-i+b_index)
    read_time -= value # Aから一冊取る


if len(check_list) == 0:
    print(0)
else:
    print(max(check_list))

Submission status: Runtime Error

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

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

time = 0
A_num = 0
B_num = 0
while time < K:
    A = A_list[A_num]
    B = B_list[B_num]
    if A < B:
        time += A
        A_num += 1

    elif A > B:
        time += B
        B_num += 1

    else:
        add = 1
        time += A
        while (A_list[A_num + add] == B_list[B_num + add]) and \
              (time < K):
            time += A_list[A_num + add]
            add += 1
        if A_list[A_num + add] > B_list[B_num + add]:
            A_num += add
        else:
            B_num += add

print(A_num + B_num - 1)

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())
Alist = list(map(int,input().split()))
Blist = list(map(int,input().split()))
count = 0


while True:
    if len(Alist) != 0 and len(Blist) != 0:
        if Alist[0] < Blist[0]:
            readtime = Alist.pop(0)
        elif Alist[0] > Blist[0]:
            readtime = Blist.pop(0)
    elif len(Alist) != 0:
        readtime = Alist.pop(0)
    elif len(Blist) != 0:
        readtime = Blist.pop(0)
    else: 
        break

    if K < readtime:
        break
    else:
        count = count + 1
        K = K - readtime

print(count)

Submission status: Runtime Error

Solution code:
a,b,c = map(int, input().split())
l1 = list(map(int, input().split()))
l2= list(map(int, input().split()))
i,j, s, d=0,0,0,0
while(c>0 and (i<=(a-1) or j<=(b-1))):
    if((i<=(a-1)) and l1[i]<l2[j]):
        if (c-l1[i])>=0:
            c=c-l1[i]
            i=i+1
            d+=1
        else:
            break
    elif(j<=(b-1)):
        if (c-l2[j])>=0:
            c=c-l2[j]
            j=j+1
            d+=1
        else:
            break
print(d)

Submission status: Runtime Error

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

ans = 0
cnt = 0
a = 0
b = 0
if sum(l_a) + sum(l_b) <= K:
  print(len(l_a) + len(l_b))
else:
  while cnt <= K:
    if l_a[a] <= l_b[b] and a != len(l_a) + 1:
      cnt += l_a[a]
      a += 1
      ans += 1
    elif l_b[b] <= l_a[a] and b != len(l_b) +1:
      cnt += l_b[b]
      b += 1
      ans += 1
  ans -= 1
  print(ans)

Submission status: Runtime Error

Solution code:
n, m, k = [int(s) for s in input().split(" ")]
if n == 0:
  input()
  alist = []
else:
  alist = [int(s) for s in input().split(" ")]
if m == 0:
  input()
  blist = []
else:
  blist = [int(s) for s in input().split(" ")]

def max_inds(aind, bind, cur_time, k):
  if aind < len(alist) and bind < len(blist) and cur_time + alist[aind] > k and cur_time + blist[bind] > k:
    return aind + bind
  else:
    if aind < len(alist) and cur_time + alist[aind] <= k:
      t1 = max_inds(aind + 1, bind, cur_time + alist[aind], k)
    else:
      t1 = aind + bind
    if bind < len(blist) and cur_time + blist[bind] <= k:
      t2 = max_inds(aind, bind + 1, cur_time + blist[bind], k)
    else:
      t2 = aind + bind
    return max(t1, t2)

if k == 0:
  print(0)
else:
  print(max_inds(0, 0, 0, k))

Submission status: Runtime Error

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

ac = 0
bc = 0
cc = 0
dd = 0
while True:
    if a[ac] > b[bc]:
        m = a[ac]
        ac += 1
    else:
        m = b[bc]
        bc += 1
    cc += m
    if cc > k:
        print(dd)
        exit()
    dd += 1

Submission status: Runtime Error

Solution code:
N,M,K = [int(s) for s in input().split()]

a = [int(s) for s in input().split()]
b =[int(s) for s in input().split()]

li = []

while True:
    try:
        if a[0]<b[0]:
            li.append(a[0])
            del a[0]
        elif a[0]>b[0]:
            li.append(b[0])
            del b[0]
        elif a[0]==b[0]:
            if a[1]<b[1]:
                li.append(a[0])
                del a[0]
            else:
                li.append(b[0])
                del b[0]
    except:
        break
        
for i in a:
    li.appned(i)
for i in b:
    li.append(i)
total = 0

count = 0

for i in li:
    total += i
    if total <=K:
        count +=1
    else:
        break
print(count)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
minute=0
ans=0
while True:
    if A[0] > K and B[0] > K:
        break
    elif not A and not B:
        break
    elif not A:
        x=B[0]
        del B[0]
    elif not B:
        x=A[0]
        del A[0]
    elif A[0]!=B[0]:
        x=min(A[0],B[0])
        if A[0]<B[0]:
            del A[0]
        else:
            del B[0]
    else:
        x=A[0]
        while True:
            i=1
            if A[i]<B[i]:
                del A[0]
                break
            elif B[i]<A[i]:
                del B[0]
                break
            else:
                i+=1
    minute += x
    if minute > K:
        break
    ans += 1

print(ans)

Submission status: Runtime Error

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


b_book = list(map(int,input().split()))

total = 0
count = 0
i=0
A = 0
B = 0
for i in range(N):
  if a_book[i]>=K:
    A = 1
for i in range(M):
  if b_book[i]>=K:
    B = 1

if A==1 or B==1:
  count = 0
elif sum(a_book)+sum(b_book)<=K:
    count = N + M
else:
  while K>=total:
    if a_book[i] <= b_book[i]:
      total += a_book[i]
      count+=1
      a_book.pop(i)
    else:
      total += b_book[i]
      count+=1
      b_book.pop(i)
    
if count==0:
  print(count)
elif count<N+M:
  print(count-1)
else:
  print(count)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]

time = 0
maxBooks = 0
for i in range(N):
  if K - time >= A[i]:
    time += A[i]
    maxBooks += 1
  else:
    break

A_count = maxBooks
nowBooks = maxBooks
flag = True
for i in range(M):
  if K - time >= B[i]:
    time += B[i]
    nowBooks += 1
  else:
    time += B[i]
    nowBooks += 1
    while K < time:
      time -= A[A_count]
      A_count -= 1
      nowBooks -= 1
      if A_count < 0:
        break
    if flag:
      break

  if maxBooks < nowBooks:
    maxBooks = nowBooks
    
print(maxBooks)

Submission status: Runtime Error

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

a = list(map(int,input().split()))

b = list(map(int,input().split()))

aa = a.reverse()
bb = b.reverse()
ans = 0
while k > 0 :
    if k >= aa[-1] or k >= bb[-1] :
        if aa[-1] > bb[-1] :
            ans += 1
            k = k - bb[-1]
            del bb[-1]
            if len(bb) == 0 :
                bb.append(2000000000)
        elif bb[-1] > aa[-1] :
            ans += 1
            k = k - aa[-1]
            del aa[-1]
            if len(aa) == 0 :
                a.append(2000000000)
        elif aa[-1] == bb[-1] :
            ans += 1
            for j in range(1,1000000):
                if aa[j*(-1)] > bb[j*(-1)] :
                    k = k - bb[-1]
                    del bb[-1]
                    if len(bb) == 0 :
                        bb.append(2000000000)
                    break
                elif aa[j*(-1)] < bb[j*(-1)] :
                    k = k - aa[-1]
                    del aa[-1]
                    if len(aa) == 0 :
                        aa.append(2000000000)
                    break
    else :
        break

print(ans)

Submission status: Runtime Error

Solution code:
a,b,c=map(int,input().split())
li_a=list(map(int,input().split()))
li_b=list(map(int,input().split()))

count=0
x=0
y=0
while c>=0:
  if a!=0 and b!=0:
    
    c=c-min(li_a[x],li_b[y])
    if li_a[x]>=li_b[y]:
      x+=1
      a-=1
    else:
      y+=1
      b-=1
    if c-min(min(li_a),min(li_b))<0:
      break
    count+=1
  if a!=0 and b==0:
    c=c-li_a[x]
    x+=1
    a-=1
    if c<0:
      break
    count+=1
  if a==0 and b!=0:
    y+=1
    b-=1
    c=c-li_b[y]
    if c<0:
      break
    count+=1
  if a==0 and b==0:
    break
    
    
print(count)

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
from collections import defaultdict, deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''C Tsundoku'''
def count(i,n,j,m,a,b,k):
    if k<0:
        return 0
    if i==n:
        if j==m:
            return 0
        if b[j]<=k:
            return 1+count(i,n,j+1,m,a,b,k-b[j])
        return 0
    elif j==m:
        if i==n:
            return 0
        if a[i]<=k:
            return 1+count(i+1,n,j,m,a,b,k-a[i])
        return 0
    else:
        if a[i]>k and b[j]>k:
            return 0
        if a[i]>k:
            return 1+count(i,n,j+1,m,a,b,k-b[j])
        if b[j]>k:
            return 1+count(i+1,n,j,m,a,b,k-a[i])
        return max(1+count(i,n,j+1,m,a,b,k-b[j]),1+count(i+1,n,j,m,a,b,k-a[i]))

n,m,k=rm()
a=rl()
b=rl()
i=0;j=0;
print(count(i,n,j,m,a,b,k))

Submission status: Runtime Error

Solution code:
n,m,rem=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
i=0
j=0
k=0
c=list()
count=0
while k<n+m:
	if a[i]<=b[j]:
		c.append(a[i])
		k=k+1
		i=i+1
	else:
		c.append(b[j])
		k=k+1
		j=j+1
	if i==n:
		while j<m:
			c.append(b[j])
			k=k+1
			j=j+1
	if j==m:
		while i<n:
			c.append(a[i])
			k=k+1
			i=i+1
i=0
while i<=k and rem>=c[i] :
	rem=rem-c[i]
	i=i+1
	count=count+1
print(count)

Submission status: Runtime Error

Solution code:
N,M,K=list(map(int, input().split())) 
a=list(map(int, input().split())) 
b=list(map(int, input().split())) 
anum=0
bnum=0
count=0
ans=0
if(K>=sum(a)+sum(b)):
    print(len(a)+len(b))
else:
    while(True):
        if(a[anum]>=b[bnum]):
            count+=b[bnum]
            bnum+=1
            if(K<count):
                break
            ans+=1
        else:
            count+=a[anum]
            anum+=1
            if(K<count):
                break
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque as q
import bisect

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

def f(nb,s,ia,ib):
    #print(nb,s,ia,ib)
    if s > K:
        return nb-1
    if ia==N and ib==M:
        return nb
    
    nb_max=0
    for nxt in ['a','b']:
        if nxt == 'a':
            if ia==N:
                continue
            nb_max=f(nb+1,s+As[ia],ia+1,ib)
        if nxt == 'b':
            if ib==M:
                continue
            nb_tmp=f(nb+1,s+Bs[ib],ia,ib+1)
            if nb_max < nb_tmp:
                nb_max = nb_tmp
    return nb_max



ans = f(0,0,0,0)
print(ans)

Submission status: Runtime Error

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]
if N[int(info[0]/2)]+M[int(info[1]/2)] <= info[2]:
  t = info[0]/2
  
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: Runtime Error

Solution code:
N,M,K=map(int,input().split())
A=map(int,input().split())
A=list(A)
B=map(int,input().split())
B=list(B)
time=int(0)
book=int(0)
ia=0
jb=0
while time<K and ia<N and jb<M:
    if A[ia]<=B[jb]:
        time += A[ia]
        book += 1
        ia+=1
        if ia==N:
            break
    else:
        time += B[jb]
        book +=1
        jb -=1
        if jb==M:
            break
if time<K and ia==N:
    while time<=K and jb<M:
        time+=B[jb]
        book+=1
        jb+=1
        if jb==M:
            break
elif time<K and jb==M:
    while time<K and ia<N:
        time+=A[ia]
        book+=1
        ia+=1
        if ia==N:
            break
if time<=K:
    print(book)
else:
    print(book-1)

Submission status: Runtime Error

Solution code:
n,m,k=map(int, input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
left_time = k - sum(a)
cnt_a = n
cnt_b = 0
flag = True
report=[]
while flag:
    if left_time <= 0:
        left_time += a[cnt_a-1]
        cnt_a -= 1
        if cnt_a <= 0 and left_time <= 0:
            flag = False
    else:
        left_time -= b[cnt_b]
        cnt_b += 1
        if cnt_b >= m:
            flag = False
    if left_time >= 0:
        report.append(cnt_a+cnt_b)
print(max(report))

Submission status: Runtime Error

Solution code:
n, m, k = [int(s) for s in input().split(" ")]
if n == 0:
  alist = []
else:
  alist = [int(s) for s in input().split(" ")]
if m == 0:
  blist = []
else:
  blist = [int(s) for s in input().split(" ")]

def max_inds(aind, bind, cur_time, k):
  if aind < len(alist) and bind < len(blist) and cur_time + alist[aind] > k and cur_time + blist[bind] > k:
    return aind + bind
  else:
    if aind < len(alist) and cur_time + alist[aind] <= k:
      t1 = max_inds(aind + 1, bind, cur_time + alist[aind], k)
    else:
      t1 = aind + bind
    if bind < len(blist) and cur_time + blist[bind] <= k:
      t2 = max_inds(aind, bind + 1, cur_time + blist[bind], k)
    else:
      t2 = aind + bind
    return max(t1, t2)

if k == 0:
  print(0)
else:
  print(max_inds(0, 0, 0, k))

Submission status: Runtime Error

Solution code:
''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys

sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7


class MergeFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]

    def find(self, a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")


def prime_factors(n):  # n**0.5 complex
    factors = dict()
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        while n % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1
            n = n // i
    if n > 2:
        factors[n] = 1
    return (factors)


def all_factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))


def fibonacci_modP(n, MOD):
    if n < 2: return 1
    return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(
        fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD


def factorial_modP_Wilson(n, p):
    if (p <= n):
        return 0
    res = (p - 1)
    for i in range(n + 1, p):
        res = (res * cached_fn(InverseEuler, i, p)) % p
    return res


def binary(n, digits=20):
    b = bin(n)[2:]
    b = '0' * (digits - len(b)) + b
    return b


def is_prime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True


def generate_primes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime


factorial_modP = []


def warm_up_fac(MOD):
    # print("in")
    global factorial_modP, fac_warm_up
    if fac_warm_up: return
    factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
    # print(len(factorial_modP))
    for i in range(2, fac_warm_up_size):
        factorial_modP[i] = (factorial_modP[i - 1] * i) % MOD
    fac_warm_up = True


def InverseEuler(n, MOD):
    return pow(n, MOD - 2, MOD)


def nCr(n, r, MOD):
    global fac_warm_up, factorial_modP
    if not fac_warm_up:
        warm_up_fac(MOD)
        fac_warm_up = True

    return (factorial_modP[n] * (
            (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD)) % MOD)) % MOD


def test_print(*args):
    if testingMode:
        print(args)


def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")


def display_2D_list(li):
    for i in li:
        print(*i)


def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm += i
        res.append(sm)
    return res


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))


memory = dict()


def clear_cache():
    global memory
    memory = dict()


def cached_fn(fn, *args):
    global memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result


def ncr(n, r):
    return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))


def binary_search(i, li):
    fn = lambda x: li[x] - x // i
    x = -1
    b = len(li)
    while b >= 1:
        while b + x < len(li) and fn(b + x) > 0:  # Change this condition 2 to whatever you like
            x += b
        b = b // 2
    return x


# -------------------------------------------------------------- MAIN PROGRAM


TestCases = False
fac_warm_up_size = 10 ** 6 + 100
optimise_for_recursion = True  # Can not be used clubbed with TestCases WHen using recursive functions, use Python 3



def fun(n, m, k, ans):
    global mx, a, b, dp

    mx = max(mx, ans)

    if n <= 0 and m <= 0 or k <= 0:
        return ans

    key = str(n)+"_"+str(m)+"_"+str(k)
    if key in dic:
        return dic[key]

    x, y = -100, -100
    if n > 0 and a[n - 1] <= k:
        key1 = str(n-1)+"_"+str(m)+"_"+str(k - a[n - 1])
        x = fun(n - 1, m, k - a[n - 1], ans + 1)
        dic[key1] = x

    if m > 0 and b[m - 1] <= k:
        key2 = str(n) + "_" + str(m-1) + "_" + str(k - b[m - 1])
        y = fun(n, m - 1, k - b[m - 1], ans + 1)
        dic[key2] = y

    dic[key] = max(x,y)
    return max(x, y)

mx = 0
n, m, k = get_tuple()
dic = defaultdict(int)
a = get_list()
b = get_list()
a = a[::-1]
b = b[::-1]

def main():
    fun(n, m, k, 0)
    print(mx)


if TestCases:
    for i in range(get_int()):
        main()
else:
    main() if not optimise_for_recursion else threading.Thread(target=main).start()

Submission status: Runtime Error

Solution code:
A=[]
B=[]
books = 0
time = 0
n, m, k = map(int,input().split())
i = 0
j = 0
A = list(map(int,input().strip().split()))[:n] 
B = list(map(int,input().strip().split()))[:m] 
while not(time > k) :
    if ((i<n and j<n and A[i]<B[j]) or (i<n and not(j<m))):
        time = time+A[i]
        i=i+1
        books=books+1
    elif ((i<n and j<m and (not(A[i]<B[j]))) or (j>-1 and not(i<n))):
        time = time+B[j]
        j=j+1
        books=books+1
print(books)

Submission status: Runtime Error

Solution code:
def dfs(a, b, k):
    global cnt
    seen[a][b] = True
    na = a + 1
    nb = b + 1
    if cnt < N + M:
        if na <= N and seen[na][b] is False and k >= book_a[na]:
            k -= book_a[na]
            cnt = max(cnt, na + b)
            dfs(na, b, k)
        if nb <= M and seen[a][nb] is False and k >= book_b[nb]:
            k -= book_b[nb]
            cnt = max(cnt, a + nb)
            dfs(a, nb, k)

N, M, k = map(int, input().split())
book_a = [int(x) for x in input().split()]
book_b = [int(x) for x in input().split()]
book_a.insert(0, 0)
book_b.insert(0, 0)
cnt = 0
seen = [[False] * (M + 1) for _ in range(N + 1)]
dfs(0, 0, k)
print(cnt)

Submission status: Runtime Error

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

ac = 0
bc = 0
cc = 0
dd = 0
while True:
  if a[ac] > b[bc]:
    m = a[ac]
    ac += 1
  else:
    m = b[bc]
  	bc += 1
  cc += m
  if cc > k:
    print(d)
    exit()
  d += 1

Submission status: Runtime Error

Solution code:
root = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))      
a.append(1000000000)
b.append(1000000000)
minute=0
books=0
ai=0
bi=0

while minute <= root[2]:
    books += 1
    if a[ai] < b[bi]:
        minute += a[ai]
        if len(a) >= ai + 1:
            an = 1000000000
        else:
            ai += 1
    elif b[bi] < a[ai]:
        minute += b[bi]
        bi += 1
        if len(b) <= bi + 1:
            bn = 1000000000
        else:
            bi += 1
    else:
        if bn == an == 1000000000:
            books += 1
            break
        if len(a) < ai:
            ai += 1
        elif len(b) < bi:
            bi += 1

print(books-1)

Submission status: Runtime Error

Solution code:
def check(A,B,a,b,MAX):
    if A[a] == MAX:
        return False
    elif B[b] == MAX:
        return True
    
    if A[a] == B[b]:
        return check(A,B,a+1,b+1)
    elif A[a] < B[b]:
        return True
    else:
        return False

N, M, K = map(int, input().split(" "))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
MAX = 10 ** 9 + 7
A.append(MAX)
B.append(MAX)
a, b, time = 0, 0, 0
for i in range(0,len(A)+len(B)-1):
#     print(A[a],B[b])
    if A[a] == B[b]:
        if A[a] == MAX:
            break
        if check(A,B,a+1,b+1,MAX):
            time += A[a]
            a += 1
        else:
            time += B[b]
            b += 1
    elif A[a] <= B[b]:
        time += A[a]
        a += 1
    else:
        time += B[b]
        b += 1
    if time > K:
        break
#     print(time)
print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    m = kwargs["m"]
    k = kwargs["k"]
    A = collections.deque(kwargs["A"])
    B = collections.deque(kwargs["B"])
    tmp = np.zeros((n + 1, m + 1))
    res = 0

    for i in range(1, n + 1):
        tmp[i, 0] = tmp[i - 1, 0] + A[i - 1]

        if tmp[i, 0] <= k:
            res = max(res, i)

    for j in range(1, m + 1):
        tmp[0, j] = tmp[0, j - 1] + B[j - 1]

        if tmp[0, j] <= k:
            res = max(res, i)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            tmp[i, j] = tmp[i, 0] + tmp[0, j]

            if tmp[i, j] <= k:
                res = max(res, i + j)

            if tmp[i, j] > k:
                break
    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"], kwargs["m"], kwargs["k"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["A"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["B"] = [int(i) for i in cin]

    cout = main(kwargs)
    print(cout)

Submission status: Runtime Error

Solution code:
import math

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
pre = 0
ai = 0
for i in range(n):
  pre += a[i]
  a[i] = pre
  if pre <= k:
    ai = i
pre = 0
bi = 0
for i in range(m):
  pre += b[i]
  b[i] = pre
  if pre <= k:
    bi = i
while a[ai] + b[bi] > k:
  if ai < 0 or bi < 0:
    ai = -1
    bi = -1
    break
  l = math.ceil(a[ai]/(ai+1))
  r = math.ceil(b[bi]/(bi+1))
  if l == r:
    if abs(a[ai]-a[ai+1]) >= abs(b[bi]-b[bi+1]):
      ai -= 1
    else:
      bi -= 1
  elif l < r:
    bi -= 1
  else:
    ai -= 1
print(ai+bi+2)