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:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
from bisect import bisect
def main():
    n, m, k = map(int, input().split())
    a = tuple(accumulate(map(int, input().split())))
    b = tuple(accumulate(map(int, input().split())))
    r = bisect(b, k)

    for i1, ae in enumerate(a):
        if k < ae:
            break
        r = max(r, bisect(b, k - ae) + i1 + 1)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Begin Header {{{
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
# }}} End Header
# _________コーディングはここから！！___________
n, m, k = map(int, input().split())
A = list(accumulate(map(int, input().split())))
B = list(accumulate(map(int, input().split())))
A=[0]+A
B=[0]+B
ans = []
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

n, m, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cnt = 0
a_cum = [0] * (n + 1)
b_cum = [0] * (m + 1)

for i in range(n):
    a_cum[i+1] = a_cum[i] + a[i]
for i in range(m):
    b_cum[i+1] = b_cum[i] + b[i]

for i in range(n+1):
    a_cnt = i
    rest = k - a_cum[i]
    if rest < 0:
        break
    b_cnt = bisect_right(b_cum,rest) - 1    
    cnt = max(cnt, a_cnt + b_cnt)

print(cnt)

Submission status: Accepted

Solution code:
def judge(n,array1,array2,K):
    for i in range(n+1):
        if len(array1) > i and len(array2) > n-i:
            sum = array1[i] + array2[n-i]
            if sum <= K:
                return True
    return False

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

cum_sum_As = [0]
cum_sum_Bs = [0]

sum_As = 0
for i in range(N):
    sum_As += As[i]
    cum_sum_As.append(sum_As)

sum_Bs = 0
for i in range(M):
    sum_Bs += Bs[i]
    cum_sum_Bs.append(sum_Bs)

l = 0
r = N + M
while(r-l>1):
    mid = (l+r)//2
    if judge(mid,cum_sum_As,cum_sum_Bs,K):
        l = mid
    else:
        r = mid

if judge(r,cum_sum_As,cum_sum_Bs,K):
    print(r)
else:
    print(l)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M, K = map(int, input().split()) 
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    acc_A = []
    acc_B = []
    acc_A.append(0)
    acc_B.append(0)
    
    sum_a = 0
    sum_b = 0

    for a in A:
        sum_a += a
        acc_A.append(sum_a)

    for b in B:
        sum_b += b
        acc_B.append(sum_b)

    large_ar = []
    small_ar = []

    if N > M:
        large_ar = acc_A
        small_ar = acc_B
    else:
        large_ar = acc_B
        small_ar = acc_A
    
    ans = 0
    for i in range(len(small_ar)):
        for j in range(ans-i+1, len(large_ar)):
            if large_ar[j] + small_ar[i] <= K:
                ans = max(ans, i+j)
            else: break
    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()))

b = 0
tb = 0

for i in range(M):
    if tb + B[i] > K:
        break
    tb += B[i]
    b = i+1

ans = [0, b]
m = b
a = 0
ta = 0

for i in range(N):
    if ta + A[i] > K:
        break
    a = i+1
    ta += A[i]
    while True:
        if ta + tb > K:
            if b == 0:break
            b -= 1
            tb -= B[b]
        else:
            if a + b > m:
                m = a + b
                ans = [a, b]
            break

print(ans[0]+ans[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()))

Asum=[0]
Bsum=[0]

for i in range(N):
    Asum.append(Asum[-1]+A[i])
        
for i in range(M):
    Bsum.append(Bsum[-1]+B[i])
    
m=0
j=M

for i in range(len(Asum)):
    if Asum[i]>K:
        break
    while Asum[i]+Bsum[j]>K:
        j-=1
    if m<i+j:
        m=i+j
        
print(m)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_right
N, M, K = map(int,input().split())
A = [0]+list(accumulate(map(int,input().split()), lambda x,y:x+y))
B = [0]+list(accumulate(map(int,input().split()), lambda x,y:x+y))
ans = 0
for i in range(N+1):
    left = K-A[i]
    if left < 0:
        break
    j = bisect_right(B, left)
    ans = max(ans, i+j-1)
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()))

As = [0] * (n + 1)
Bs = [0] * (m + 1)
for i in range(n):
  As[i + 1] = A[i] + As[i]
for i in range(m):
  Bs[i + 1] = B[i] + Bs[i]

l = 0
r = n + m + 1
while r - l > 1:
  p = (l + r) // 2
  best = min(
    As[i] + Bs[p - i] for i in range(p + 1)
    if min(i, n) + min(p - i, m) == p
  )
  if best <= k:
    l = p
  else:
    r = p
print(l)

Submission status: Accepted

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

As = [0] * (n + 1)
Bs = [0] * (m + 1)
for i in range(n):
  As[i + 1] = A[i] + As[i]
for i in range(m):
  Bs[i + 1] = B[i] + Bs[i]

l = 0
r = n + m + 1
while r - l > 1:
  p = (l + r) // 2
  best = k + 1
  for i in range(p + 1):
    if min(i, n) + min(p - i, m) < p:
      continue
    best = min(best, As[i] + Bs[p - i])
  if best <= k:
    l = p
  else:
    r = p
print(l)

Submission status: Accepted

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

l = M
ans = 0
for k in range(N+1):
  if SA[k] > K:
    break
  while SA[k] + SB[l] > K:
    l -= 1
  ans = max(ans, k + l)
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 getval():
    n,m,k = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    a = [A[0]]
    b = [B[0]]
    for i in range(0,n-1):
        a.append(a[i]+A[i+1])
    for i in range(0,m-1):
        b.append(b[i]+B[i+1])
    return n,m,k,a,b

def main(n,m,k,a,b):
    idxa = 0
    ans = 0
    t = 0
    while a[idxa]<=k and idxa<n:
        idxa += 1
        if idxa==n:
            break
    ans = idxa
    idxa -= 1
    t = a[idxa]
    for i in range(m):
        t = a[idxa] + b[i]
        if t<=k:
            ans = max(ans,idxa+i+2)
        else:
            flag = False
            while t>k:
                idxa -= 1
                if idxa<0:
                    a.append(0)
                    break
                t = a[idxa]+b[i]
            ans = max(ans,idxa+i+2)

    print(ans)

if __name__=="__main__":
    n,m,k,a,b = getval()
    main(n,m,k,a,b)

Submission status: Accepted

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

for i in range(1, N + 1):
    cumsum_a[i] = cumsum_a[i - 1] + A[i - 1]

for i in range(1, M + 1):
    cumsum_b[i] = cumsum_b[i - 1] + B[i - 1]

ans = 0
bi = M
for i in range(N+1):
    for j in range(bi, -1, -1):
        t = cumsum_a[i] + cumsum_b[j]
        if t <= K:
            ans = max(ans, i + j)
            bi = j
            break

print(ans)

Submission status: Accepted

Solution code:
import math , sys, bisect

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

Asum=[0]
Bsum=[]
if A[0] > K and B[0] > K:
    print(0)
    sys.exit()

for i in range(N):
    if i ==0:
        tot = A[i]
    else:
        tot += A[i]
    Asum.append(tot)

for i in range(M):
    if i ==0:
        tot = B[i]
    else:
        tot += B[i]
    Bsum.append(tot)

#ans=bisect.bisect(Bsum,K)
ans=0
for i in range(N+1):
    tot = Asum[i]
    if tot > K:
        print(ans)
        sys.exit()
    num = bisect.bisect(Bsum,K-tot)
    if i + num >ans:
        ans=i+num
print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
tmp_a = list(map(int,input().split()))
tmp_b = list(map(int,input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i]+tmp_a[i])
for i in range(m):
    b.append(b[i]+tmp_b[i])
#print(a)
#print(b)
ans = 0
j = 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 itertools import accumulate
import bisect
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a_acc = [0] + list(accumulate(a))
b_acc = list(accumulate(b))
#print(a_acc)
#print(b_acc)

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        break

    bn = bisect.bisect_right(b_acc, rem)
    #print(bn)
    ans = max(ans, an + bn)

print(ans)

Submission status: Accepted

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

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
f=len(d)-1
for i in range(len(c)):
  for j in range(f,-1,-1):
    if c[i]+d[j]<=k:
      if i+j>e:
        e=i+j
      f=j
      break
print(e)

Submission status: Accepted

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(" ")]
A = [0]
B = [0]
for i in a:
    if A[-1] > k:
        break
    A.append(A[-1] + i)
for i in b:
    if B[-1] > k:
        break
    B.append(B[-1] + i)

ans = 0
j = len(B) - 1

for i in range(len(A)):
    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 = [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])
# print(a)
# print(b)
# print(a[3])
ans=0
j = 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 itertools import accumulate
import bisect

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

a_acc = [0] + list(accumulate(a))  # aを0冊読む=1冊も読まない場合があるので、[0]を先頭に追加します
b_acc = list(accumulate(b))  # bisect_rightでは、x以下の要素がいくつあるか？を求めるので、こちらに0は入れません

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        # aをこれ以上読めません
        break

    bn = bisect.bisect_right(b_acc, rem)
    ans = max(ans, an + bn)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect
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)
for i in range(N):
    SA[i+1] = SA[i] + A[i]
for i in range(M):
    SB[i+1] = SB[i] + B[i]

result = 0
y = M
for x in range(N+1):
    if SA[x] > K:
        break
    while y >= 0 and SA[x] + SB[y] > K:
        y -= 1
    result = max(result, x + y)
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect
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)
for i in range(N):
    SA[i+1] = SA[i] + A[i]
for i in range(M):
    SB[i+1] = SB[i] + B[i]
result = 0
for x in range(N+1):
    if SA[x] > K:
        break
    y = bisect(SB, K - SA[x]) - 1
    result = max(result, x + y)
print(result)

Submission status: Accepted

Solution code:
from bisect import bisect_left
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)
for i in range(N):
    SA[i+1] = SA[i] + A[i]
for i in range(M):
    SB[i+1] = SB[i] + B[i]
result = 0
for x in range(N+1):
    if SA[x] > K:
        break
    y = bisect_left(SB, K - SA[x] + 1) - 1
    result = max(result, x + y)
print(result)

Submission status: Accepted

Solution code:
def binary_search(arr, num):
  left = 0
  right = len(arr)-1
  while right-left > 0:
    mid = (left+right) // 2
    if arr[mid] > num:
      right = mid
    else:
      left = mid + 1
  if arr[left] > num:
    return left
  else:
    return len(arr)

def main():
  n, m, k = map(int , input().split())
  a_books = list(map(int , input().split()))
  b_books = list(map(int , input().split()))
  a_cum_sum = [0] * (n+1)
  b_cum_sum = [0] * (m+1)

  for i in range(n):
    a_cum_sum[i+1] = a_cum_sum[i] + a_books[i]
  for i in range(m):
    b_cum_sum[i+1] = b_cum_sum[i] + b_books[i]
  ans = 0
  for i in range(n+1):
    if a_cum_sum[i] > k:
      break
    rest = k - a_cum_sum[i]
    index = binary_search(b_cum_sum, rest)
    ans = max(ans, i+index-1)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def binary_search(arr, num):
  left = 0
  right = len(arr)-1
  while right-left > 0:
    mid = (left+right) // 2
    if arr[mid] > num:
      right = mid
    else:
      left = mid + 1
  if arr[left] > num:
    return left
  else:
    return len(arr)

def main():
  n, m, k = map(int , input().split())
  a_books = list(map(int , input().split()))
  b_books = list(map(int , input().split()))
  b_cum_sum = [0] * (m+1)
  for i in range(m):
    b_cum_sum[i+1] = b_cum_sum[i] + b_books[i]
  current = 0
  ans = 0
  for i in range(n+1):
    if i > 0:
      current += a_books[i-1]
    if current > k:
      break
    rest = k - current
    index = binary_search(b_cum_sum, rest)
    ans = max(ans, i+index-1)
  print(ans)

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]*(N+1), [0]*(M+1)
for i in range(N):
	a[i+1] = a[i] + A[i] 
for i in range(M):
	b[i+1] = 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()))
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:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 11:05:00 2020

@author: liang
"""

"""
片側を固定して、それぞれのケースに対して最適解を求める
それぞれのケースについて
index(b_i) =< index(b_i-1)
であるから、bの最大値bestを保存して探索することで重複探索を回避できる
"""
N, M, K = map(int, input().split())

A = [0] + [int(x) for x in input().split()]
B = [0] + [int(x) for x in input().split()]

s_b = 0
for i in range(M+1):
    s_b += B[i]
    if s_b > K:
        s_b -= B[i]
        best = i - 1
        break
else:
    best = M
res = best
#print(res)
s_a = 0
for i in range(N+1):
   # print("i", i)
    s_a += A[i]
    if s_a > K:
        break
    for j in reversed(range(best+1)):
        #print("j",j)
        if s_b <= K - s_a:
            if i + j > res:
                res = i + j
            best = j
            #print(i, j, s_a, s_b)
            break
        else:
            s_b -= B[j]
        
print(res)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import accumulate
def main():
    n, m, k = map(int,input().split())
    A = [0] + list(map(int,input().split()))
    B = [0] + list(map(int,input().split()))
    A = list(accumulate(A))
    B = list(accumulate(B))
    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)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
shelfA = list(map(int,input().split()))
shelfB = list(map(int,input().split()))
prodA = [0]*(n+1)
prodB = [0]*(m+1)
for i in range(1,n+1):
    prodA[i] = prodA[i-1] + shelfA[i-1]
for i in range(1,m+1):
    prodB[i] = prodB[i-1] + shelfB[i-1]

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



print(ans)