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:
def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    cum_A = [0]
    for a in A:
        if a + cum_A[-1] <= K:
            cum_A.append(a + cum_A[-1])
        else:
            break
    cum_B = [0]
    for b in B:
        if b + cum_B[-1] <= K:
            cum_B.append(b + cum_B[-1])
        else:
            break

    ans = 0
    max_b_idx = len(cum_B) - 1
    for a_idx, a in enumerate(cum_A):
        if a <= K and a_idx > ans:
            ans = a_idx
        for b_idx in reversed(range(max_b_idx + 1)):
            if a + cum_B[b_idx] <= K:
                max_b_idx = b_idx
                if a_idx + b_idx > ans:
                    ans = a_idx + b_idx
                break
    print(ans)


if __name__ == '__main__':
    main()

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()]
aa = [0]
bb = [0]
 
for s in range(n):
    aa.append(aa[s] + a[s])
for s in range(m):
    bb.append(bb[s] + b[s])      
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:
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = []

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

cen = M
j = M
for i in range(N+1):
  if a[i]>K:
    break
  while b[j]>K-a[i]:
    j -= 1
  ans.append(i+j)
  
print(max(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()]
aa = [0]
bb = [0]

for s in range(n):
    aa.append(aa[s] + a[s])
for s in range(m):
    bb.append(bb[s] + b[s])      
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:
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(len(a)):
    A.append(A[i] + a[i])
for i in range(len(b)):
    B.append(B[i] + b[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,=map(int,input().split())
*B,=map(int,input().split())

AX=[0]*(N+1)
na=N+1
for i in range(1,N+1):
    AX[i]=AX[i-1]+A[i-1]
    if K<AX[i]:na=min(na,i)

BX=[0]*(M+1)
nb=M+1
for i in range(1,M+1):
    BX[i]=BX[i-1]+B[i-1]
    if K<BX[i]:nb=min(nb,i)

import bisect        
ans=0
for i in range(na):
 j=bisect.bisect_right(BX,K-AX[i])-1
 # print(na,t,i,j)
 ans=max(ans,i+j)
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    from bisect import bisect_right
    n, m, k, *ab = map(int, string.split())
    a, b = [0] + ab[:n], [0] + ab[n:]
    a, b = list(accumulate(a)), list(accumulate(b))
    ans = 0
    for i in range(n + 1):
        c = bisect_right(b, k - a[i]) - 1
        if c != -1:
            ans = max(ans, c + i)
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from itertools import accumulate


def _solve(string):
    n, m, k, *ab = map(int, string.split())
    a, b = [0] + ab[:n], [0] + ab[n:]
    a, b = list(accumulate(a)), list(accumulate(b))
    i, j = n, 0
    while a[i] > k:
        i -= 1
    while j <= m and a[i] + b[j] <= k:
        j += 1
    ans = i + j - 1
    for i in range(i, -1, -1):
        while j <= m and a[i] + b[j] <= k:
            j += 1
        ans = max(ans, i + j - 1)
    return str(ans)


def solve(string):
    from bisect import bisect_right
    n, m, k, *ab = map(int, string.split())
    a, b = [0] + ab[:n], [0] + ab[n:]
    a, b = list(accumulate(a)), list(accumulate(b))

    ans = [0]

    for i in range(n + 1):
        c = bisect_right(b, k - a[i]) - 1
        if c != -1:
            ans.append(c + i)

    return str(max(ans))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    n, m, k, *ab = map(int, string.split())
    a, b = [0] + ab[:n], [0] + ab[n:]
    a, b = list(accumulate(a)), list(accumulate(b))
    i, j = n, 0
    while a[i] > k:
        i -= 1
    while j <= m and a[i] + b[j] <= k:
        j += 1
    ans = i + j - 1
    for i in range(i, -1, -1):
        while j <= m and a[i] + b[j] <= k:
            j += 1
        ans = max(ans, i + j - 1)
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    n, m, k, *ab = map(int, string.split())
    a, b = [0] + ab[:n], [0] + ab[n:]
    a, b = list(accumulate(a)), list(accumulate(b))
    i, j, ans = n, 0, 0
    while a[i] > k:
        i -= 1
    while j <= m and a[i] + b[j] <= k:
        j += 1
    ans = i + j - 1
    while i > 0:
        i -= 1
        while j <= m and a[i] + b[j] <= k:
            j += 1
        ans = max(ans, i + j - 1)
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split()) 
Al=list(map(int,input().split()) )
Bl=list(map(int,input().split()) )
bmax=0
A=[0]
B=[0]
for i in range(1,n+1):
    A.append(A[i-1]+Al[i-1])  
for i in range(1,m+1):
    B.append(B[i-1]+Bl[i-1])
    if B[i]<=k:
        bmax=i

ans=0
b=bmax
for a in range(len(A)):
    if A[a]>k:
        break
    # ans = max(ans, a+1)
    
    while A[a] + B[b] >k and b>=0:
        b -= 1
        
        
    ans = max(ans, a+b)
        
print(ans)

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]

ans = 0

b_index = M

for a_index in range(N+1):
    left = K - A[a_index]
    if left < 0: continue

    while left - B[b_index] < 0:
        b_index -= 1

    ans = max(ans, a_index + b_index)

print(ans)

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()))
ra = [0] * (n + 1)
rb = [0] * (m + 1)
for i in range(n):
    ra[i + 1] = a[i] + ra[i]

for j in range(m):
    rb[j + 1] = b[j] + rb[j]

ans = 0
for i in range(n + 1):
    zan = k - ra[i]
    if zan < 0:
        break
    rbi = bisect.bisect_right(rb, zan) - 1
    if rbi < 0:
        rbi = 0
    ans = max(ans, i + rbi)
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()))
ans=0
asum=0
bsum=0
pointer=0
while pointer<m and bsum+b[pointer]<=k:
	bsum+=b[pointer]
	pointer+=1
ans=pointer
for i in range(n):
	asum+=a[i]
	while asum+bsum>k and pointer>=0:
		pointer-=1
		bsum-=b[pointer]
	if asum+bsum>k:
		break
	ans=max(ans,(i+1)+pointer)
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()))
aa,bb=[0],[0]
for i in range(n):
    aa.append(aa[-1]+a[i])
for i in range(m):
    bb.append(bb[-1]+b[i])
ans,j=0,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:
n,m,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_c_sum = [0]*(n + 1)
for i in range(n):
  a_c_sum[i + 1] = a_c_sum[i] + a[i]
b_c_sum = [0]*(m + 1)
for i in range(m):
  b_c_sum[i + 1] = b_c_sum[i] + b[i]

ans, best_b = 0, m
for i in range(n + 1):
  if a_c_sum[i] > k:
    break
  else:
    while 1:
      if b_c_sum[best_b] + a_c_sum[i] <= k:
        ans = max(ans, i + best_b)
        break
      else:
        best_b -= 1
        if best_b == 0:
          break
print(ans)

Submission status: Accepted

Solution code:
n,m,k = list(map(int,input().split(" ")))
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
cnt = 0
ans = 0
j = m
t = sum(b)

for i in range(n+1):
    while j>0:
        if t>k: #aのみの場合の処理が足りない（常にjでスキップされてしまう）
            j -= 1
            t -= b[j]
        else:break
    if t<=k: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()))
t = sum(b)
ans = 0
j = m

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 = [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 b[j] > K-a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Submission status: Accepted

Solution code:
import sys
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
b2 = []
t = k
start = 0
while True:
  if start == len(b):
    break
  else:
    if t - b[start] < 0:
      break
    else:  
      t -= b[start]
      b2.append(b[start])
      start += 1
num = start
lst = [start]
M = start

for i in range(len(a)):
  if a[i] > t and b2 == []:
    print(M)
    sys.exit()
  while a[i] > t and b2 != []:
    b_ = b2.pop()
    t = t+b_
    num -= 1
    
  if a[i] <= t:
    t -= a[i]
    num += 1
  
 
  if M < num:
    M = num
  lst.append(num)    
    
  
  
  
  
print(M)

Submission status: Accepted

Solution code:
import bisect

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

a_time_sum = [0]
b_time_sum = []
for i in range(n):
    if i == 0:
        a_time_sum.append(book_a[0])
    else:
        a_time_sum.append(a_time_sum[i]+book_a[i])

for i in range(m):
    if i == 0:
        b_time_sum.append(book_b[0])
    else:
        b_time_sum.append(b_time_sum[i-1]+book_b[i])

ans = 0

# Aから何冊か読む
for i in range(n+1):
    read = i
    a_time = a_time_sum[i]
    time_remain = k - a_time
    if time_remain < 0:
        break
    # このときBから何冊よめる？
    b_read = bisect.bisect_right(b_time_sum, time_remain)
    read += b_read
    ans = max(ans, read)

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

aa = [0]
bb = [0]
for i in range(n):
    aa.append(aa[-1]+a[i])
for i in range(m):
    bb.append(bb[-1]+b[i])
c = m
ans = 0
for i in range(n+1):
    u = k - aa[i]
    for j in range(c, -1, -1):
        if bb[j] <= u:
            ans = max(ans, i+j)
            c = j
            break
print(ans)

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

a2 = [0] * (n + 1)
b2 = [0] * (m + 1)
for i in range(0, n):
    a2[i+1] = a[i] + a2[i]
for i in range(0, m):
    b2[i+1] = b[i] + b2[i]

ans = 0
for i in range(n+1):
    tmp = bisect.bisect_right(b2, k-a2[i]) - 1
    if a2[i] + b2[tmp] <= k and tmp >= 0:
        ans = max(ans, i+tmp)

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

totalA = sum(A)
while totalA > K:
    totalA -= A.pop()
ans = len(A)

totalB = 0
for i in range(M):
    totalB += B[i]
    while totalA + totalB > K:
        if not A:
            break
        totalA -= A.pop()
    if totalA + totalB <= K:
        ans = max(ans, len(A) + i + 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()))
a=[0]
b=[0]
for i in range(len(A)):
	a.append(a[i]+A[i])

for i in range(len(B)):
	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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, K = MAP()
A = LIST()
B = LIST()
A_ruiseki = A
B_ruiseki = B
for i in range(N-1):
    A_ruiseki[i+1] += A_ruiseki[i]

for i in range(M-1):
    B_ruiseki[i+1] += B_ruiseki[i]
ans = 0
for i in range(N):
    a_idx = 0
    # b_idx = 0
    amari = K
    if K - A_ruiseki[i] >= 0:
        a_idx = i + 1
        amari = amari - A_ruiseki[i]
        b_idx = bisect(B_ruiseki, amari)
        total = a_idx + b_idx
        ans = max(ans, total)
#  only b case
b_idx = bisect(B, K)
# print(b_idx)
ans = max(ans, b_idx)
print(ans)

Submission status: Accepted

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

sum_a = [0]
for i in range(n):
    sum_a.append(sum_a[i] + a[i])
sum_b = [0]
for i in range(m):
    sum_b.append(sum_b[i] + 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
pin = sys.stdin.readline
pout = sys.stdout.write
perr = sys.stderr.write

N, M, K = map(int, pin().split())
A = list(map(int, pin().split()))
B = list(map(int, pin().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

for i in range(N + 1):
    #Aの合計がKを超えるまで比較する
    if a[i] > K:
        break
    # 超えていた場合に本の個数を減らす
    while b[M] > K - a[i]:
        M -= 1
    ans = max(ans, M + i)
print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
from itertools import accumulate
from bisect import bisect_right
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ac=[0]+list(accumulate(a))
bc=[0]+list(accumulate(b))
temp=0

for i in range(n+1):
    if ac[i]<=k:
        count=i
        count+=bisect_right(bc,k-ac[i])-1
        temp=max(temp,count)
print(temp)

Submission status: Accepted

Solution code:
import numpy as np

from numba import njit


@njit("i8[:](i8, i8[:], i8[:])", cache=True)
def cumsum(K, L, cL):
    for i, a in enumerate(L):
        cL[i] = cL[i - 1] + L[i]
        if cL[i] > K:
            cL[i] = 0
            break

    cL = cL[cL != 0]
    cL = np.append(0, cL)
    return cL


@njit("i8(i8, i8[:], i8[:])", cache=True)
def solve(K, A, cB):
    ans_max = 0
    for i, a in enumerate(A):
        ans = 0
        K -= a
        ind = np.searchsorted(cB, K, side="right") - 1
        ans = i + ind

        if ans > ans_max:
            ans_max = ans

        if ind == 0 or K < 0:
            break

    return ans_max


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

cA = np.zeros(N, dtype=np.int64)
cB = np.zeros(M, dtype=np.int64)

# np.cumsumだとoverflowする
cA = cumsum(K, A, cA)
cB = cumsum(K, B, cB)

A = np.append(0, A)
ans = solve(K, A, cB)
print(max(ans, len(cA) - 1, len(cB) - 1))

Submission status: Accepted

Solution code:
import numpy as np

from numba import njit


@njit("i8[:](i8, i8[:], i8[:])", cache=True)
def cumsum(K, A, cA):
    for i, a in enumerate(A):
        cA[i] += cA[i - 1] + A[i]
        if cA[i] > K:
            break

    cA = cA[cA != 0]
    cA = np.append(0, cA)
    return cA


@njit("i8(i8, i8[:], i8[:])", cache=True)
def solve(K, cA, cB):
    ans = np.searchsorted(cA, K - cB, side="right") - 1
    ans += np.arange(len(cB))
    return ans.max()


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

cA = np.zeros(N, dtype=np.int64)
cB = np.zeros(M, dtype=np.int64)

# np.cumsumだとoverflowする
cA = cumsum(K, A, cA)
cB = cumsum(K, B, cB)

ans = solve(K, cA, cB)
print(ans)

Submission status: Accepted

Solution code:
'''
Created on 2020/08/31

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,M,K=map(int,pin().split())
  A=list(map(int,pin().split()))
  B=list(map(int,pin().split()))
  a=[0]
  b=[0]
  for i in range(N):
    a.append(a[i]+A[i])
  for j in range(M):
    b.append(b[j]+B[j])
  ans=0
  l=M
  for k in range(N+1):
    if a[k]>K:
      break
    while b[l]>K-a[k]:
      l-=1
    ans=max(ans,l+k)
  print(ans)
  return
main()
#解説AC

Submission status: Accepted

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

for i in range(n):
    a_time.append(a_time[-1] + a[i])
for j in range(m):
    b_time.append(b_time[-1] + b[j])

j = m
cnt = 0

for i in range(n+1):
    if a_time[i] > k:
        continue

    while j > 0 and a_time[i] + b_time[j] > k:
        j -= 1
    cnt = max(cnt, i + j)

print(cnt)

Submission status: Accepted

Solution code:
n, m, k = list(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])

res = 0
j = m

for i in range(n + 1):
  if A[i] > k:
    break
  while ((A[i] + B[j]) > k):
    j -= 1
  res = max(res, i + j)
  
print(res)

Submission status: Accepted

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

for i in range(n):
    a_time.append(a_time[-1] + a[i])
for j in range(m):
    b_time.append(b_time[-1] + b[j])

j = m
cnt = 0

for i in range(n+1):
    if a_time[i] > k:
        continue

    while j > 0 and a_time[i] + b_time[j] > k:
        j -= 1
    cnt = max(cnt, i + j)

print(cnt)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

N,M,K=i_map()
A=i_list()
B=i_list()
cum_A = [0]*(N+1)
cum_B = [0]*(M+1)
for i in range(1, N+1):
    cum_A[i] = cum_A[i-1] + A[i-1]
for i in range(1, M+1):
    cum_B[i] = cum_B[i-1] + B[i-1]
ans = 0
for i in range(0, N+1):
    val = K - cum_A[i]
    if val < 0:
        continue
    idx = bisect_right(cum_B, val) - 1
    ans = max(ans, i + idx)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    sum_A = [0 for _ in range(N + 1)]
    sum_B = [0 for _ in range(M + 1)]

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

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

    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)

if __name__ == "__main__":
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    solve()

Submission status: Accepted

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_stack=deque([])
now=0
mn=0
j=0
for i in a:
  mn+=i
  if mn>k:
    mn-=i
    break
  else:
    now+=1
    a_stack.append(i)
for i in b:
  mn+=i
  if mn>k:
    mn-=i
    break
  else:
    now+=1
    j+=1
    if j==m:
      print(now)
      exit()
ans=now
while a_stack:
  if j>=m:
    break
  else:
    q=a_stack.pop()
    mn-=q
    now-=1
    while k-mn>0:
      mn+=b[j]
      now+=1
      if k-mn<0:
        now-=1
        mn-=b[j]
        break
      j+=1
      if j==m:
        break
    ans=max(now,ans)
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()))

aa = [0]
bb = [0]
for i in range(n):
    aa.append(aa[-1]+a[i])
for i in range(m):
    bb.append(bb[-1]+b[i])

d = 0
ans = 0
for i in range(n, -1, -1):
    c = k - aa[i]
    if c >= 0:
        for j in range(d, m+1):
            if bb[j] <= c:
                d = j
            else:
                break
        ans = max(ans, i+d)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

N,M,K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

accA = list(accumulate(A))
accB = list(accumulate(B))

maxbook = 0
idx_B = M
for idx_A in range(N+1):
    time = accA[idx_A]
    for j in range(idx_B, -1, -1):
        if time + accB[j] <= K:
            idx_B = j
            break
    if time + accB[idx_B] <= K:
        maxbook = max(maxbook, idx_A + idx_B)

print(maxbook)

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))
ans = 0
for i in range(N+1):
  rem = K - a_acc[i]
  if rem < 0:
    break
  bn = bisect.bisect_right(b_acc,rem)
  ans = max(ans, i+bn)
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の本を上からi冊読んだ時の数列を{ai}とする
a0 = 0, a1 = A1, a2 = A1 + A2, a3 = A1+ A2 + A3, ...
計算量を減らすには漸化式を利用する
a2 = a1 + A2, a3 = a2 + A3, ..., ai = a(i - 1) + Ai
"""

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

"""
上から読む机Aの本の数を昇順で考えていくとき
上から読む机Bの本の数は降順で考えると計算量を減らせる
また、上から読む机Aの本の数を1冊増やしたとき
上から読む机Bの本の数は前より冊数が少ないことを利用する
"""

j = M
ans = 0
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
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))
ans = 0
for i, A_sums in enumerate(A_sums_list):
    B_min = -1
    B_max = M + 1
    while B_max - B_min > 1:
        B_index = int((B_max + B_min) * 0.5)
        if A_sums + B_sums_list[B_index] <= K:
            B_min = B_index
        else:
            B_max = B_index
#    B_index = int((B_max + B_min) * 0.5)
    if i + B_min > ans and A_sums + B_sums_list[B_min] <= K:
        ans = i + B_min
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))
ans = 0
for i, A_sums in enumerate(A_sums_list):
    B_min = -1
    B_max = M + 1
    while B_max - B_min > 1:
        B_index = int((B_max + B_min) * 0.5)
        if A_sums + B_sums_list[B_index] <= K:
            B_min = B_index
        else:
            B_max = B_index
    B_index = int((B_max + B_min) * 0.5)
    if i + B_index > ans and A_sums + B_sums_list[B_index] <= K:
        ans = i + B_index
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))
ans = 0
for i, A_sums in enumerate(A_sums_list):
    B_min = 0
    B_max = M + 1
    while True:
        B_index = int((B_max + B_min) * 0.5)
        if A_sums + B_sums_list[B_index] <= K:
            B_min = B_index
        else:
            B_max = B_index
        if B_max - B_min == 1:
            break   
    if i + B_min > ans and A_sums + B_sums_list[B_min] <= K:
        ans = i + B_min
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import bisect
from typing import List


def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(t(n, m, k, a, b))


def t(n: int, _: int, k: int, a: List[int], b: List[int]) -> int:
    a = np.concatenate([[0], a])
    a = np.cumsum(a)
    b = np.concatenate([[0], b])
    b = np.cumsum(b)

    ret = 0
    for i in range(n + 1):
        x = a[i]
        s = k - x
        if s < 0:
            break
        j = bisect.bisect(b, s) - 1
        ret = max(ret, i + j)

    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m,k=input2()
A=input_array()
B=input_array()
acc_A=[0]
acc_B=[0]

for i in range(n):
	acc_A.append(A[i]+acc_A[i])
for i in range(m):
	acc_B.append(B[i]+acc_B[i])

ans=0
tmp_m=m
for i in range(n+1):
	if acc_A[i]>k:
		break
	for j in range(tmp_m,-1,-1):
		if acc_B[j]<=k-acc_A[i]:
			ans=max(i+j,ans)
			tmp_m=j #探索開始地点の更新
			break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, m, k = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

a = [0]
b = [0]

a = np.append(a, np.cumsum(A))
b = np.append(b, np.cumsum(B))

j = m
ans = 0
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:
import itertools
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(itertools.accumulate(a))
b_acc = [0] + list(itertools.accumulate(b))
ans = 0

for i in range(n+1):
    if k - a_acc[i] >= 0:
        ans = max(ans, i + bisect.bisect(b_acc, k - a_acc[i])-1)
print(ans)

Submission status: Accepted

Solution code:
import bisect
from typing import List


def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(t(n, m, k, a, b))


def t(n: int, m: int, k: int, a: List[int], b: List[int]) -> int:
    aa = [0]
    for i in range(n):
        aa.append(aa[i] + a[i])
    bb = [0]
    for i in range(m):
        bb.append(bb[i] + b[i])

    ret = 0
    for i in range(n + 1):
        x = aa[i]
        s = k - x
        if s < 0:
            break
        j = bisect.bisect(bb, s) - 1
        ret = max(ret, i + j)

    return ret


if __name__ == '__main__':
    main()