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

Solution code:
# Did not get in the contest. The key insight is in the end, the optimal solution involves taking X books from the front of A and Y books from the front of B. The intermediate transitions from one stack to another do not matter in the big picture.

from sys import stdin
n, m, k = map(int, stdin.readline().split())
astack = list(map(int, stdin.readline().split()))
bstack = list(map(int, stdin.readline().split()))

def correctApproach_naiveImplementation(n, m, k, astack, bstack):
    # TLE. Time complexity O(N^2). N<2*10^5.

    # max books from A upto which total time <= k.
    tot_time = 0
    maxbooks = 0
    prefix_tot_time_a = [0]

    # O(n) to calculate prefix total time for stack A.
    for i in astack:
        if tot_time + i <= k:
            tot_time += i
            maxbooks += 1
            prefix_tot_time_a.append(tot_time)
        else:
            break

    # remove one book at a time from maxbooks of A. And checking how many more books of B we can take. Find the max configuration of taking X books from front of A and Y books from front of B.

    # O(n) to calculate prefix total time for stack B.
    ans = maxbooks
    prefix_tot_time_b = [bstack[0]]
    for i in bstack[1:]:
        prefix_tot_time_b.append(prefix_tot_time_b[-1] + i)

    # ind1 is the number of books taken from A. This is O(n^2).
    for ind1 in range(maxbooks, -1, -1):
        currmax = ind1
        tot_time = prefix_tot_time_a[ind1]

        # this inner loop is O(N) we are trying to find the max number of books we can take from B linearly. We can use binary search instead.
        for ind2 in range(m):
            if tot_time + prefix_tot_time_b[ind2] <= k:
                currmax += 1
            else:
                break
        ans = max(ans, currmax)
    print(ans)
            
def correctApproach_binarySearch(n, m, k, astack, bstack):
    # Accepted. O(N log M + M)
    from bisect import bisect_right
    tot_time = 0
    maxbooks = 0
    prefix_tot_time_a = [0]

    # O(n) to calculate prefix total time for stack A.
    for i in astack:
        if tot_time + i <= k:
            tot_time += i
            maxbooks += 1
            prefix_tot_time_a.append(tot_time)
        else:
            break

    # O(n) to calculate prefix total time for stack B.
    ans = maxbooks
    prefix_tot_time_b = [bstack[0]]
    for i in bstack[1:]:
        prefix_tot_time_b.append(prefix_tot_time_b[-1] + i)

    # ind1 is the number of books taken from A. This is O(n log m).
    for ind1 in range(maxbooks, -1, -1):
        currmax = ind1
        tot_time = prefix_tot_time_a[ind1]

        # remaining time; Binary search on prefix total time on B.
        rem = k - tot_time 
        ind2 = bisect_right(prefix_tot_time_b, x = rem)
        currmax += ind2

        ans = max(ans, currmax)
    print(ans)

def correctApproach_twoPointer(n, m, k, astack, bstack):
    tot = 0
    pa = []
    for i in astack:
        if tot + i <= k:
            tot += i
            pa += [tot]
        else: break
    
    tot = 0
    pb = []
    for i in bstack:
        if tot + i <= k:
            tot += i
            pb += [tot]
        else: break
    
    l1, l2 = len(pa), len(pb)
    if l1 == 0: print(l2)
    elif l2 == 0: print(l1)
    else:
        i, j = l1-1, 0
        ans = max(l1, l2)
        currmax = (i+1) + (j)
        while i > -1 and j < l2:
            if pa[i] + pb[j] <= k:
                currmax += 1
                j += 1
            else:
                currmax -= 1
                i -= 1
            ans = max(ans, currmax)
        print(ans)
            
# correctApproach_binarySearch(n, m, k, astack, bstack)
correctApproach_twoPointer(n, m, k, astack, bstack)























########## MY FAILED ATTEMPT IN CONTEST; COULD ONLY GET 10 AC AND 10 WA ################
# Tried greedy approach in various ways which were wrong.


# from sys import stdin
# from collections import deque as dq
# from itertools import zip_longest
# n, m, k = map(int, input().split())
# a = dq(map(int, stdin.readline().split()))
# b = dq(map(int, stdin.readline().split()))

# tot = 0
# count = 0

# i = j = 0
# while i < n and j < m:
#     # pick one line
#     if tot + a[i] + b[j] > k:
#         count1 = 0
#         ssf = tot
#         for ind1 in range(i, n):
#             if a[ind1] + ssf > k:
#                 break
#             else:
#                 ssf += a[ind1]
#                 count1 += 1

#         count2 = 0
#         ssf = tot
#         for ind2 in range(j, m):
#             if b[ind2] + ssf > k:
#                 break
#             else:
#                 ssf += b[ind2]
#                 count2 += 1

#         if count1 > count2:
#             print(count + count1)
#         else:
#             print(count + count2) 
#         exit()

#     # pick from any line 
#     else:
#         if tot + min(a[i], b[j]) > k:
#             break
#         elif a[i] < b[j]:
#             tot += a[i]
#             count += 1
#             i += 1
#         elif b[j] < a[i]:
#             tot += b[j]
#             count += 1
#             j += 1
#         else:
#             count1 = 0
#             for ind1 in range(i, n):
#                 if a[ind1] <= a[i]:
#                     count1 += 1
#                 else:
#                     break
#             count2 = 0
#             for ind2 in range(j, m):
#                 if a[ind2] <= b[j]:
#                     count2 += 1
#                 else:
#                     break
            
#             if count1>count2:
#                 tot += a[i]
#                 i += 1
#             elif count2<count1:
#                 tot += b[j]
#                 j += 1
#             else:
#                 if sum(a[i: min(i + count1 + 1, n)]) < sum(b[j: min(j + count2 + 1, m)]):
#                     tot += a[i]
#                     i += 1
#                 else:
#                     tot += b[j]
#                     j += 1
#             count += 1


# if i == n and j == m:
#     print(count)
# elif i < n:
#     for ind in range(i, n):
#         if tot + a[ind] <= k:
#             count += 1
#             tot += a[ind]
#     print(count)
# elif j < m:
#     for ind in range(j, m):
#         if tot + b[ind] <=k:
#             count += 1
#             tot += b[ind]
#     print(count)




# while tot < k:
#     atop = a[0] if a else 10**10
#     btop = b[0] if b else 10**10

#     # both empty
#     if atop == 10**10 and btop == 10**10:
#         break
    
#     # if adding the minimum crosses k.
#     if tot + min(atop, btop) > k:
#         break
    
#     if tot + atop + b
#     if atop < btop:
#         tot += a.popleft()
#         count += 1
#     elif btop < atop:
#         tot += b.popleft()
#         count += 1
#     else:
#         rema = True
#         for i, j in zip(a, b):
#             if i < j:
#                 rema = True
#                 break
#             elif j < i:
#                 rema = False
#                 break
#             else:
#                 pass
#         if rema:
#             tot += a.popleft()
#             count += 1
#         else:
#             tot += b.popleft()
#             count += 1

Submission status: Accepted

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

t = sum(b)
j = m
ans = 0
for i in range(n+1):
    while j > 0 and t > k:
        j -= 1
        t -= b[j]
    if t > k:
        break
    ans = max(ans, i+j)
    if i == n:
        break
    t += a[i]

print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
A= list(map(int, input().split()))
B= list(map(int, input().split()))
a,b=[0],[0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])

ans,j=0,m
for i in range(n+1):
    if a[i]>k:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
from itertools import accumulate
AA = [0]+list(accumulate(A))
BB = [0]+list(accumulate(B))
ans = 0
j = M
for i in range(N+1):
    if AA[i]>K:
        break
    while BB[j]>K-AA[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Submission status: Accepted

Solution code:
# Did not get in the contest. The key insight is in the end, the optimal solution involves taking X books from the front of A and Y books from the front of B. The intermediate transitions from one stack to another do not matter in the big picture.

from sys import stdin
n, m, k = map(int, stdin.readline().split())
astack = list(map(int, stdin.readline().split()))
bstack = list(map(int, stdin.readline().split()))

def correctApproach_naiveImplementation(n, m, k, astack, bstack):
    # TLE. Time complexity O(N^2). N<2*10^5.

    # max books from A upto which total time <= k.
    tot_time = 0
    maxbooks = 0
    prefix_tot_time_a = [0]

    # O(n) to calculate prefix total time for stack A.
    for i in astack:
        if tot_time + i <= k:
            tot_time += i
            maxbooks += 1
            prefix_tot_time_a.append(tot_time)
        else:
            break

    # remove one book at a time from maxbooks of A. And checking how many more books of B we can take. Find the max configuration of taking X books from front of A and Y books from front of B.

    # O(n) to calculate prefix total time for stack B.
    ans = maxbooks
    prefix_tot_time_b = [bstack[0]]
    for i in bstack[1:]:
        prefix_tot_time_b.append(prefix_tot_time_b[-1] + i)

    # ind1 is the number of books taken from A. This is O(n^2).
    for ind1 in range(maxbooks, -1, -1):
        currmax = ind1
        tot_time = prefix_tot_time_a[ind1]

        # this inner loop is O(N) we are trying to find the max number of books we can take from B linearly. We can use binary search instead.
        for ind2 in range(m):
            if tot_time + prefix_tot_time_b[ind2] <= k:
                currmax += 1
            else:
                break
        ans = max(ans, currmax)
    print(ans)
            
def correctApproach_binarySearch(n, m, k, astack, bstack):
    from bisect import bisect_right
    tot_time = 0
    maxbooks = 0
    prefix_tot_time_a = [0]

    # O(n) to calculate prefix total time for stack A.
    for i in astack:
        if tot_time + i <= k:
            tot_time += i
            maxbooks += 1
            prefix_tot_time_a.append(tot_time)
        else:
            break

    # O(n) to calculate prefix total time for stack B.
    ans = maxbooks
    prefix_tot_time_b = [bstack[0]]
    for i in bstack[1:]:
        prefix_tot_time_b.append(prefix_tot_time_b[-1] + i)

    # ind1 is the number of books taken from A. This is O(n log n).
    for ind1 in range(maxbooks, -1, -1):
        currmax = ind1
        tot_time = prefix_tot_time_a[ind1]

        # remaining time; Binary search
        rem = k - tot_time 
        ind2 = bisect_right(prefix_tot_time_b, x = rem)
        currmax += ind2

        ans = max(ans, currmax)
    print(ans)

correctApproach_binarySearch(n, m, k, astack, bstack)























########## MY FAILED ATTEMPT IN CONTEST; COULD ONLY GET 10 AC AND 10 WA ################
# Tried greedy approach in various ways which were wrong.


# from sys import stdin
# from collections import deque as dq
# from itertools import zip_longest
# n, m, k = map(int, input().split())
# a = dq(map(int, stdin.readline().split()))
# b = dq(map(int, stdin.readline().split()))

# tot = 0
# count = 0

# i = j = 0
# while i < n and j < m:
#     # pick one line
#     if tot + a[i] + b[j] > k:
#         count1 = 0
#         ssf = tot
#         for ind1 in range(i, n):
#             if a[ind1] + ssf > k:
#                 break
#             else:
#                 ssf += a[ind1]
#                 count1 += 1

#         count2 = 0
#         ssf = tot
#         for ind2 in range(j, m):
#             if b[ind2] + ssf > k:
#                 break
#             else:
#                 ssf += b[ind2]
#                 count2 += 1

#         if count1 > count2:
#             print(count + count1)
#         else:
#             print(count + count2) 
#         exit()

#     # pick from any line 
#     else:
#         if tot + min(a[i], b[j]) > k:
#             break
#         elif a[i] < b[j]:
#             tot += a[i]
#             count += 1
#             i += 1
#         elif b[j] < a[i]:
#             tot += b[j]
#             count += 1
#             j += 1
#         else:
#             count1 = 0
#             for ind1 in range(i, n):
#                 if a[ind1] <= a[i]:
#                     count1 += 1
#                 else:
#                     break
#             count2 = 0
#             for ind2 in range(j, m):
#                 if a[ind2] <= b[j]:
#                     count2 += 1
#                 else:
#                     break
            
#             if count1>count2:
#                 tot += a[i]
#                 i += 1
#             elif count2<count1:
#                 tot += b[j]
#                 j += 1
#             else:
#                 if sum(a[i: min(i + count1 + 1, n)]) < sum(b[j: min(j + count2 + 1, m)]):
#                     tot += a[i]
#                     i += 1
#                 else:
#                     tot += b[j]
#                     j += 1
#             count += 1


# if i == n and j == m:
#     print(count)
# elif i < n:
#     for ind in range(i, n):
#         if tot + a[ind] <= k:
#             count += 1
#             tot += a[ind]
#     print(count)
# elif j < m:
#     for ind in range(j, m):
#         if tot + b[ind] <=k:
#             count += 1
#             tot += b[ind]
#     print(count)




# while tot < k:
#     atop = a[0] if a else 10**10
#     btop = b[0] if b else 10**10

#     # both empty
#     if atop == 10**10 and btop == 10**10:
#         break
    
#     # if adding the minimum crosses k.
#     if tot + min(atop, btop) > k:
#         break
    
#     if tot + atop + b
#     if atop < btop:
#         tot += a.popleft()
#         count += 1
#     elif btop < atop:
#         tot += b.popleft()
#         count += 1
#     else:
#         rema = True
#         for i, j in zip(a, b):
#             if i < j:
#                 rema = True
#                 break
#             elif j < i:
#                 rema = False
#                 break
#             else:
#                 pass
#         if rema:
#             tot += a.popleft()
#             count += 1
#         else:
#             tot += b.popleft()
#             count += 1

Submission status: Accepted

Solution code:
def main():
    N, M, K = map(int, input().split())
    ns = list(map(int, input().split()))
    ms = list(map(int, input().split()))
    ns_accum, ms_accum = [0], [0]
    n_accum_tmp, m_accum_tmp, num_books = 0, 0, 0
    for i in range(len(ns)):
        n_accum_tmp += ns[i]
        ns_accum.append(n_accum_tmp)

    for i in range(len(ms)):
        m_accum_tmp += ms[i]
        ms_accum.append(m_accum_tmp)

    for i in range(len(ns_accum)):
        time_left = K - ns_accum[i]
        if time_left >= 0:
            num_book_m = max(0, binary_search(ms_accum, time_left))
            num_books = max(num_books, i+num_book_m)

    print(num_books)


def binary_search(A, x):
    ok = -1
    ng = len(A)
    while (abs(ok - ng) > 1):
        mid = (ng+ok) // 2
        if A[mid] <= x:
            ok = mid
        else:
            ng = mid

    return ok


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
 
def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
 
    maxv = 0
    acum = [0] * (n + 1)
    bcum = [0] * (m + 1)
    for i in range(n):
        acum[i + 1] = acum[i] + a[i]
    for i in range(m):
        bcum[i + 1] = bcum[i] + b[i]
 
    for i in range(n + 1):
        if acum[i] > k:
            break
        maxv = max(maxv, i + bisect_right(bcum, k - acum[i]) - 1)
    print(maxv)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
  a.append(a[i] + A[i])
for i in range(M):
  b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
     break
  else:
    while b[j] > K - a[i]:
      j -= 1
  ans = max(ans, i + j)
print(ans)

Submission status: Accepted

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

a, b = [0], [0]
 
for i in range(N):
	a.append(a[i] + A[i])
    
for i in range(M):
	b.append(b[i] + B[i])
    
ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

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

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

    ans = 0
    bi = m
    for ai, at in enumerate(a):
        if at > k:
            break

        while at + b[bi] > k:
            bi -= 1
        
        ans = max(ans, ai+bi)
    
    print(ans)
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

N, M, K = map(int, input().split())
a = [0] + list(accumulate(int(i) for i in input().split()))
b = [0] + list(accumulate(int(i) for i in input().split()))

cnt = 0
best0 = M
for i in range(N+1):
    ai = a[i]
    for j in range(best0, -1, -1):
        bj = b[j]
        if ai + bj <= K:
            cnt = max(cnt, i + j)
            best0 = j
            break

print(cnt)

Submission status: Accepted

Solution code:

from bisect import bisect_right
from itertools import accumulate
def resolve():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    cum_A = [0]+list(accumulate(A))
    cum_B = [0]+list(accumulate(B))

    ans = 0
    for i in range(N + 1):
        limit = K - cum_A[i]
        if limit < 0:
            break
        cnt = i
        cnt += bisect_right(cum_B, limit)-1
        ans = max(ans, cnt)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
cumA = [0] * (N+1)
cumB = [0] * (M+1)

point = 0
for i in range(N):
    cumA[i+1] = cumA[i] + A[i]
for i in range(M):
    cumB[i+1] = cumB[i] + B[i]

# 尺取りの要領でiを増やしjを減らす
res, j = 0, M
for i in range(N+1):
    if cumA[i] > K:
        break
    while cumB[j] > K - cumA[i]:
        j -= 1
    res = max(res, i+j)

print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left,bisect_right
n,m,k=map(int,input().split())
a=list(accumulate(map(int,input().split()),initial=0))
b=list(accumulate(map(int,input().split()),initial=0))
ans=[0]
for i in range(n+1):
    c=bisect_right(b,k-a[i])-1
    if c!=-1:
        ans.append(c+i)
print(max(ans))

Submission status: Accepted

Solution code:
from bisect import bisect_right

def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    maxv = 0
    acum = [0] * (n + 1)
    bcum = [0] * (m + 1)
    for i in range(n):
        acum[i + 1] = acum[i] + a[i]
    for i in range(m):
        bcum[i + 1] = bcum[i] + b[i]

    for i in range(n + 1):
        if acum[i] > k:
            continue
        maxv = max(maxv, i + bisect_right(bcum, k - acum[i]) - 1)
    print(maxv)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

answer = 0
cost = 0
index_a = -1
for i in range(len(A)):
    if i == len(A) or cost + A[i] > K:
        break
    cost += A[i]
    answer += 1
    index_a = i

max_answer = answer
index_b = 0
while (index_b < len(B)):    
    if cost + B[index_b] > K:
        if index_a < 0:
            break
        cost -= A[index_a]
        index_a -= 1
        answer -= 1
    else:
        cost += B[index_b]
        index_b += 1
        answer += 1
    if max_answer < answer:
        max_answer = answer
print(max_answer)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
for i in range(1,n):
    a[i] += a[i-1]
for i in range(1,m):
    b[i] += b[i-1]
a = [0]+a
b = [0]+b

ans = 0
ALL = 0
j = m

for i in range(n+1):
    if a[i] > k:
        continue
    else:
        while k-a[i] < b[j] :
            j -=1
    ans = max(ans,i+j)
print(ans)

Submission status: Accepted

Solution code:
# 貪欲に一つ目の要素をとっていってはいけない。
# 累積和からうまくえらぶ

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

A = [0]
B = [0]
for a in input().split():
    A.append(A[-1]+int(a))
for b in input().split():
    B.append(B[-1]+int(b))

ans = 0
b_num = m
for i in range(n+1):
    while b_num>=0 and B[b_num]>k-A[i]:
        b_num -= 1
    if b_num>=0 and i+b_num > ans:
        ans = i+b_num
#        print(i, b_num)
print(ans)

Submission status: Accepted

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

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

a =[0]+ list(itertools.accumulate(a))
b =[0]+ list(itertools.accumulate(b))



ans=0
for i in range(n+1):
    x=k-a[i]
    if x<0:
        break
    else:
        v=bisect.bisect_right(b,x)-1
        ans=max(ans,i+v)
print(ans)

Submission status: Accepted

Solution code:
import bisect

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(1, N):
    A[i] = A[i] + A[i-1]
A = [0] + A
B = list(map(int, input().split()))
for i in range(1, M):
    B[i] = B[i] + B[i-1]
B = [0] + B

ans = 0
for i in range(N+1):
    if A[i] > K:
        break
    temp = K - A[i]
    val = bisect.bisect_right(B, temp) - 1
    ans = max(ans, i + val)
print(ans)

Submission status: Accepted

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

A_parts = [0 for _ in range(N+1)]
B_parts = [0 for _ in range(M+1)]

for i in range(N):
  A_parts[i+1] = A_parts[i] + A[i]

for i in range(M):
  B_parts[i+1] = B_parts[i] + B[i]

a_ind = 0
b_ind = M
best = 0

while a_ind <= N and b_ind >= 0:
  while b_ind >= 0 and A_parts[a_ind] + B_parts[b_ind] > K:
    b_ind -= 1
  if b_ind < 0:
    break
  best = max(best, a_ind + b_ind)
  a_ind += 1

print best

Submission status: Accepted

Solution code:
import numpy as np
from bisect import bisect

N,M,K = map(int,input().split())
A = np.array(input().split(),dtype=int)
B = np.array(input().split(),dtype=int)

AA = np.insert(A,0,0)
BB = np.insert(B,0,0)
AAA = np.cumsum(AA)
BBB = np.cumsum(BB)
max_books = 0
for a in enumerate(AAA):
    if a[1] > K:
        break
    books = a[0]
    ind = bisect(BBB,K - a[1])
    books += (ind-1)
    max_books = max(books,max_books)
print(max_books)

Submission status: Accepted

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

a=[0]
b=[0]

for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
    
c=0
idx=m

for i in range(n+1):
    while 1:
        if idx<0:
            break
        if a[i]+b[idx]>k:
            idx-=1
            continue
        else:
            c=max(i+idx,c)
            break
else:
    print(c)

Submission status: Accepted

Solution code:
import bisect
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
sa = [0 for _ in range(n)]
sb = [0 for _ in range(m)]
x = 0
for i in range(n):
  x += a[i]
  sa[i] = x
y = 0
for j in range(m):
  y += b[j]
  sb[j] = y
si = -1
for i in range(n):
  if sa[n-1-i] <= k:
    si = n-1-i
    break
if si == -1:
  ki = bisect.bisect_right(sb,k)
  print(ki)
else:
  ans = si+1
  for i in range(0,si+1):
    ki = bisect.bisect_right(sb,k-sa[i])
    if ki+i+1 > ans:
      ans = ki+i+1
  ki = bisect.bisect_right(sb,k)
  if ki > ans:
    ans = ki
  print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sum_a = [0]
sum_b = [0]
for i in range(n):
    sum_a.append(a[i]+sum_a[i])
for i in range(m):
    sum_b.append(b[i]+sum_b[i])
ans = 0
j = m
for i in range(n+1):
    if sum_a[i] > k:
        break
    while sum_b[j] > k - sum_a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)

Submission status: Accepted

Solution code:
import sys
# from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	n, m, k = read()
	arr1 = [0]+read(); arr2 = [0]+read()
	for i in range(1, n+1):arr1[i] += arr1[i-1]
	for i in range(1, m+1):arr2[i] += arr2[i-1]

	i = 0; ans = 0
	while i < n+1 and arr1[i] <= k:
		tem = i + bisect(arr2, k-arr1[i])-1
		# print(tem, i, arr1[i], bisect(arr2, k-arr1[i]))
		ans = max(ans, tem)
		i += 1
	print(ans)

	





		

if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
from bisect import bisect_right
n,m,k=map(int,input().split())
a=[int(i) for i in input().split()][:n]
b=[int(i) for i in input().split()][:m]
x=[0]*(n+1)
y=[0]*(m+1)
for i in range(1,n+1):
    x[i]=x[i-1]+a[i-1]
for j in range(1,m+1):
    y[j]=y[j-1]+b[j-1]
ans,j=0,m
for i in range(n+1):
    if x[i]>k:
        break
    j=bisect_right(y,k-x[i])-1
    ans=max(ans,i+j)
print(ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
for i in range(1,n):
    a[i] += a[i-1]
for i in range(1,m):
    b[i] += b[i-1]
a = [0]+a
b = [0]+b

ans = 0
ALL = 0
from bisect import bisect
for i in range(n+1):
    ALL = a[i]
    if ALL > k:
        continue
    else:
        idx = bisect(b,k-ALL)
    #print(i,ALL,idx)
        ans = max(ans,i+idx-1)
print(ans)

Submission status: Accepted

Solution code:
import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,K = LI()
A = LI()
B = LI()
accumulate_A = [0]+list(itertools.accumulate(A))
accumulate_B = [0]+list(itertools.accumulate(B))
ans,j = 0,M
for i in range(N+1):
    if accumulate_A[i]>K:
        break
    while accumulate_A[i]+accumulate_B[j]>K:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Submission status: Accepted

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

a=[0]
b=[0]
for i in range(n):
  a.append(a[i]+A[i])
for i in range(m):
  b.append(b[i]+B[i])
ans=0
j=m
for i in range(n+1):
  if a[i]>k:
    break
  while a[i]+b[j]>k:
    j-=1
  ans=max(ans,i+j)
print(ans)

Submission status: Accepted

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

a, b = [0],[0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)

Submission status: Accepted

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

    a, b = [0], [0]
    for i in range(N):
        a.append(a[i] + A[i])

    for i in range(M):
        b.append(b[i] + B[i])

    ans, j = 0, M
    for i in range(N + 1):
        if a[i] > K:
            break
        while b[j] > K - a[i]:
            j -= 1
        ans = max(ans, i + j)

    print(ans)
main()

Submission status: Accepted

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

for i in range(1, n+1):
    a[i] += a[i -1]

for i in range(1, m+1):
    b[i] += b[i -1]

b_cnt = m
ans = 0

for a_cnt in range(n+1):
    if a[a_cnt] <= k:
        while a[a_cnt] + b[b_cnt] > k:
            b_cnt -= 1
    else:
        break

    ans = max(ans, a_cnt + b_cnt)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate, permutations
import bisect

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

A = [0] + list(accumulate(A))
B = [0] + list(accumulate(B))

ans = 0
for i in range(N+1):
    a = A[i]
    if a > K:
        break
    r = K - a
    j = bisect.bisect(B, r) - 1
    ans = max(ans, i + j)

print(ans)