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 bisect

n,m,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
sum_a=[a[0]]
for i in range(len(a)-1):
    sum_a.append(sum_a[i]+a[i+1])
sum_b=[b[0]]
for i in range(len(b)-1):
    sum_b.append(sum_b[i]+b[i+1])

#現在のインデックス
idx_a=0
idx_b=0

while idx_a<n or idx_b<m:
    read=''
    #aの読める数
    oset_a=sum_a[idx_a-1] if idx_a>0 else 0
    can_cnt_a=bisect.bisect_right(sum_a,k+oset_a)
    #bの読める数
    oset_b=sum_b[idx_b-1] if idx_b>0 else 0
    can_cnt_b=bisect.bisect_right(sum_b,k+oset_b)
    read='a' if can_cnt_a-idx_a>can_cnt_b-idx_b else 'b'
    if idx_a==n:
        read='b'
    if idx_b==m:
        read='a'
    

    #読むほうをPOP
    k-=a[idx_a] if read=='a' else b[idx_b]
    #kを超えた場合ブレーク
    if k<0:
        break
    #カウントアップ
    if read=='a':
        idx_a+=1
    else:
        idx_b+=1
print(idx_a+idx_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()))

cnt = 0
cost = 0
for i, x in enumerate(a):
    cost += x
    if cost > k:
        cnt = i
        cost -= x
        break
else:
    for j, y in enumerate(b):
        cost += y
        if cost > k:
            cnt = n + j
            cost -= y
            break
    else:
        cnt = n + m

if cnt <= n:
    i_max, j = cnt - 1, 0
else:
    i_max, j = n - 1, cnt - n

while j < m and cost + b[j] <= k:
    cost += b[j]
    j += 1
    cnt += 1

ans = cnt
for i in range(i_max, -1, -1):
    if j == m: break
    cost -= a[i]
    cnt -= 1
    while j < m and cost + b[j] <= k:
        cost += b[j]
        j += 1
        cnt += 1

    ans = max(cnt, 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()))

#1

import numpy as np
import bisect
acum=np.cumsum(a).tolist()
bcum=np.cumsum(b).tolist()

ans=0

for i,c in enumerate(acum):
    d=k-c
    if d<0:break
    j=bisect.bisect_right(bcum,d)-1
 
    ans=max(ans,(i+1)+(j+1))
    
for i,c in enumerate(bcum):
    d=k-c
    if d<0:break
    j=bisect.bisect_right(acum,d)-1
 
    ans=max(ans,(i+1)+(j+1))
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = []
aa = 0
bb = 0
b = []
flag = 0
for i in range(N):
    aa += A[i]
    a.append(aa)
for i in range(M):
    bb += B[i]
    b.append(bb)
MAX = 0
for i in range(N):
    t = a[i]
    if t > K:
        break
    else:
        tt = K-t
        index = bisect_left(b,tt)
    if index == M:
        MAX = max(MAX,i+1+M)
    elif b[index] == tt:
        MAX = max(MAX,i+1+1+index)
    else:
        MAX = max(MAX,i+1+index)
for i in range(M):
    t = b[i]
    if t > K:
        break
    else:
        tt = K-t
        index = bisect_left(a,tt)
    if index == N:
        MAX = max(MAX,i+1+N)
    elif a[index] == tt:
        MAX = max(MAX,i+1+1+index)
    else:
        MAX = max(MAX,i+1+index)



print(MAX)

Submission status: Accepted

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

init = 0
init2 = 0
s = 0
for i in range(n):
  if s + a[i] <= k:
    s += a[i]
    init += 1
  else:
    break

for i in range(m):
  if s + b[i] <= k:
    s += b[i]
    init2 += 1
  else:
    break

max_ = init+init2

while init > 0:
  s -= a[init-1]
  init -= 1
  for i in range(init2, m):
    if s + b[i] <= k:
      s += b[i]
      init2 += 1
    else:
      break
  max_ = max(max_, init+init2)
print(max_)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 0
    a_time = [0]
    b_time = [0]
    for i in range(1, len(a) + 1):
        a_time.append(a_time[i - 1] + a[i - 1])
    for i in range(1, len(b) + 1):
        b_time.append(b_time[i - 1] + b[i - 1])

    a_max = 0
    b_max = 0
    for i in range(len(a_time)):
        if a_time[i] > k:
            break
        else:
            a_max = i
    for i in range(len(b_time)):
        if b_time[i] > k:
            break
        else:
            b_max = i

    for i in range(len(b_time)):
        if a_time[a_max] + b_time[i] <= k:
            ans = max(ans, a_max + i)
        else:
            if a_max > 0:
                a_max -= 1
    for i in range(len(a_time)):
        if b_time[b_max] + a_time[i] <= k:
            ans = max(ans, b_max + i)
        else:
            if b_max > 0:
                b_max -= 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

#DIV = (10**9) + 7
DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N,M,K = isRaw()
    As = isRaw()
    Bs = isRaw()
    sAs = [0]
    for a in As:
        t = a + sAs[-1]
        if t>K:
            break
        sAs.append(t)

    sBs=[0]
    for b in Bs:
        t = b + sBs[-1]
        if t>K:
            break
        sBs.append(t)
    sBs = sBs[1:]
    ans = 0
    for sai,sa in enumerate(sAs):
        
        sbi = bisect.bisect_right(sBs,K-sa)
        ans = max(ans,sai+sbi)
    print (ans)


main()

Submission status: Accepted

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

    cum = 0
    a_cnt = 0
    b_cnt = 0
    for i, j in enumerate(a):
        if cum + j > k:
            break
        cum += j
        a_cnt += 1
    
    for i, j in enumerate(b):
        if cum + j > k:
            break
        cum += j
        b_cnt += 1

    cnt = a_cnt + b_cnt
    max_cnt = cnt

    for i in range(a_cnt-1, -1, -1):
        cum -= a[i]
        cnt -= 1
        for i in range(b_cnt, len(b)):
            if cum + b[i] > k:
                break
            cum += b[i]
            b_cnt += 1
            cnt += 1
            max_cnt = max(cnt, max_cnt)
    print(max_cnt)   

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import bisect
n,m,k=map(int,input().split())
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
count=0
book=0
rest=0
ans=[]
aaa=list(itertools.accumulate(aa))
bbb=list(itertools.accumulate(bb))
bs=bisect.bisect(bbb,k)
ap=bisect.bisect(aaa,k)
ans.append(ap)
for i in range(bs+1):
  ii=bs-i
  rest=k-bbb[ii-1]
  goal=bisect.bisect(aaa,rest)
  ans.append(ii+goal)
  #print(ii,goal,rest)

print(max(ans))

Submission status: Accepted

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


def log(*args):
    print(*args, file=sys.stderr)


def main():
    _n, _m, k = map(int, input().split())
    ns = list(map(int, input().rstrip().split()))
    ms = list(map(int, input().rstrip().split()))
    sum = 0
    count = 0
    for v in ns:
        if sum + v > k:
            break
        else:
            sum += v
            count += 1

    ans_now = count
    ans = ans_now
    i = count - 1
    for v in ms:
        if sum + v > k:
            while sum + v > k:
                if i < 0:
                    break
                sum -= ns[i]
                i -= 1
                ans_now -= 1
            if sum + v > k:
                break
            sum += v
            ans_now += 1
        else:
            sum += v
            ans_now += 1
        ans = max(ans, ans_now)
    print(ans)


if __name__ == '__main__':
    main()

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()))
mnt=0
i=1
mb=0
j=1
while mnt<=k and 0<i<n+1:
    mnt+=a[i-1]
    i+=1
if mnt>k:
    i-=2
    mnt-=a[i]
else:
    i-=1

while i>=0:

    while mnt<=k and j<m+1:
        if j==0:
            j=1
        mnt+=b[j-1]
        j+=1
    if mnt>k:
        j-=1
        mnt-=b[j-1]
    
        
    if i+j-1>mb:
        mb=i+j-1
    
    mnt-=a[i-1]
    i-=1            
            
            
print(mb)

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

# もしすべてaから選んだ場合
time = k
aOnly = 0
for i in range(len(a)):
    time -= a[i]
    if time < 0:
        time += a[i]
        i -= 1
        break
    aOnly += 1
a_idx = i
b_idx = -1

for i in range(len(b)):
    time -= b[i]
    if time < 0:
        time += b[i]
        i -= 1
        break
    aOnly += 1
b_idx = i
ans = aOnly

ans_kari = ans
for i in range(a_idx, -1, -1):
    time += a[i]
    ans_kari -= 1
    for j in range(b_idx+1, len(b)):
        time -= b[j]
        if time < 0:
            time += b[j]
            b_idx = j-1
            break
        ans_kari += 1
    ans = max(ans, ans_kari)
    
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left, bisect_right
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)


def main():
    from builtins import int, map
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    # AとBの累積和
    cA = [0] * (N + 1)
    cB = [0] * (M + 1)
    for k in range(N):
        cA[k + 1] = cA[k] + A[k]
    for k in range(M):
        cB[k + 1] = cB[k] + B[k]

    # 読むAの冊数
    ans = -1
    for a in range(N + 1):
        rem = K - cA[a]
        if rem < 0:
            break
        bli = bisect_left(cB, rem)
        bri = bisect_right(cB, rem)
        ans_a = None
        if bli == bri:
            ans_a = a + bli - 1
        else:
            ans_a = a + bli
        # print(a, rem, bli, bri, ans_a)
        ans = max(ans, ans_a)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    total = 0
    a_idx = 0 # A[a_idx] は含まれない
    while a_idx < n and total + A[a_idx] <= k:
        total += A[a_idx]
        a_idx += 1
    b_idx = 0
    while b_idx < m and total + B[b_idx] <= k:
        total += B[b_idx]
        b_idx += 1

    ans = a_idx + b_idx
    while a_idx - 1 >= 0:
        a_idx -= 1
        total -= A[a_idx]
        while b_idx < m and total + B[b_idx] <= k:
            total += B[b_idx]
            b_idx += 1
        ans = max(ans, a_idx + b_idx)

    print(ans)
resolve()

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

    time = 0
    i = 0
    while (time + A[i] <= K):
        time += A[i]
        i += 1
        if i == N:
            break

    i2 = i-1#i2はAの一番下の変数を指すポインタ
    h = 0
    while (time + B[h] <= K):
        time += B[h]
        h += 1
        i += 1
        if h == M:
            break
    max = i
    #iは冊数

    i3 = i#今後比べていくときの合計冊数
    #print(time,i)
    if h == M:
        return max

    for j in range(i2+1):
        if i2 < 0:
            return max
        time -= A[i2]
        i3 -= 1
        while (time + B[h] <= K):
            time += B[h]
            h += 1
            i3 += 1
            if h == M:
                break
        #print(time,i3)

        if i3 > max:
            max = i3

        i2 -= 1
        if h == M:
            return max

    return max

print(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.append(1999999999999999)
b.append(1999999999999999)

o = 0
aa = 0
be = 0
for i in range(n+1):
    o += a[i]
    aa += 1
    if o > k:
        break
        
ans = aa-1
an = aa
cur = k - o
for i in range(aa):
    cur += a[aa-1-i]
    an -= 1
    
    for j in range(m+1):
        cur -= b[be]
        if cur < 0:
            cur += b[be]
            break
        an += 1
        be += 1
        
    ans = max(an,ans)
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, M, K = map(int, input().split())
As = [0] + list(map(int, input().split()))
Bs = [0] + list(map(int, input().split()))
csum_A = list(accumulate(As))
csum_B = list(accumulate(Bs))

ok = 0
ng = N + M + 2
while ng - ok > 1:
    mid = (ng + ok) // 2
    min_time = 10 ** 9 + 10
    for t in range(max(0, mid-M), min(mid+1, N+1)):
        min_time = min(min_time, csum_A[t] + csum_B[mid - t])
    
    if K >= min_time:
        ok = mid
    else:
        ng = mid

print(ok)

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 j in range(m):
    sb[j+1] = sb[j] + b[j]
#print(sa)
#print(sb)
ans = 0
for i in range(n+1):
    if k - sa[i] >= 0:
        j = bisect_left(sb, k-sa[i])
        #print(k-sa[i])
        #print(j)
        if j <= m and k - sa[i] == sb[j]:
            ans = max(ans, i+j)
        else:
            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()))

s_a = [0] * (n + 1)
s_b = [0] * (m + 1)
#s_a[0] = a[0]
#s_b[0] = b[0]
for i in range(1, n + 1):
    s_a[i] = s_a[i - 1] + a[i - 1]
for i in range(1, m + 1):
    s_b[i] = s_b[i - 1] + b[i - 1]
    
import bisect
ans = 0
for i in range(n + 1):
    num = s_a[i]
    if k < num:
        continue
    cnt = i
    cnt += bisect.bisect_right(s_b, k - num) - 1
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
import bisect
N,M,K=map(int,input().split())
A=[int(x) for x in input().split()]
B=[int(y) for y in input().split()]
ans=0
a_nowtime=0
B_time=[0]*M
kari=0#time
for j in range(M):
    kari+=B[j]
    B_time[j]=kari
kari=0#numofbookofa+b
a_nowtime=0
for i in range(N+1):
    time=K-a_nowtime
    num=bisect.bisect_right(B_time,time)
    kari=i+num
    ans=max(ans,kari)
    if i==N:
        break
    a_nowtime+=A[i]

    if a_nowtime>K:
        break

print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
    resolve()

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 = deque(a)
b = deque(b)
t = 0
book = deque()
while len(b):
    if b[0]+t <= k:
        t += b[0]
        book.append(b.popleft())
    else:
        break
nn = len(book)
# 逆じゅん
new_book = deque()
for i in range(nn):
    new_book.append(book.pop())
book = new_book
# aも詰め込めるだけ
while len(a):
    if a[0]+t <= k:
        t += a[0]
        book.append(a.popleft())
    else:
        break
ans = len(book)
for i in range(nn):
    t -= book.popleft()
    while len(a) and t+a[0]<=k:
        ta = a.popleft()
        t += ta
        book.append(ta)
    ans = max(ans, len(book))

print(ans)

Submission status: Accepted

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

a_li = [0] + a_li
b_li = [0] + b_li

time = 0
ans = 0
a = 0
temp = 0

a_wa = [0] * (n+10)
b_wa = [0] * (m+10)

s = 0
for i in range(n+1):
    s += a_li[i]
    a_wa[i] = s

s = 0
for i in range(m+1):
    s += b_li[i]
    b_wa[i] = s
    

for i in range(n+1):
    for j in range(max(min(temp-i, m), 0), m+1):
        time = a_wa[i] + b_wa[j]
        if time <= k:
            ans = max(ans, i+j)
            temp = ans
        else:
            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()))
AA=[0]*(N+1)
BB=[0]*(M+1)
A3=0
B3=0
high=0
for i in range(0,N):
    A3+=A[i]
    AA[i+1]=A3
for j in range(0,M):
    B3+=B[j]
    BB[j+1]=B3
for i in range(0,N+1):
    if AA[i]>K:
        break
    while True:
        if BB==[]:
            break
        elif BB==[0]:
            BB=[]
            break
        elif AA[i]+BB[-1]>K:
            BB.pop(-1)
        else:
            break
    if BB!=[]:
        time=AA[i]+BB[-1]
        judge=1
    else:
        time=AA[i]
        judge=0
    if time<=K:
        if judge==0:
            if high<i:
                high=i
        else:
            if high<i+len(BB)-1:
                high=i+len(BB)-1
print(high)

Submission status: Accepted

Solution code:
from bisect import bisect


n, m, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = list(map(int, input().split()))

for i in range(1, n + 1):
    A[i] += A[i - 1]
for j in range(1, m):
    B[j] += B[j - 1]

ans = 0
for i in range(n + 1):
    if A[i] <= k:
        x = k - A[i]
        j = bisect(B, x)
        ans = max(ans, i + j)

print(ans)

Submission status: Accepted

Solution code:
def binary_search(l:list,a:int):
    #リストlからaの値のインデックスをサーチする。
    #二分探索を可能にするためにはリストlはソートされていなければならない。
    length = len(l)
    center = length//2
    low = 0
    high = length - 1
    while low <= high:
        if l[center] == a:
            return center
        elif l[center] < a:
            low = center + 1
        elif l[center] > a:
            high = center - 1

        center = (low + high) // 2
    return center


def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    a_sums = [0] * (len(a) + 1)
    a_sums[0] = 0
    for i in range(len(a)):
        a_sums[i+1] = a_sums[i] + a[i]
    b_sums = [0] * (len(b)+1)
    b_sums[0] = 0
    for i in range(len(b)):
        b_sums[i+1] = b_sums[i] + b[i]
    #print(a_sums)
    #print(b_sums)
    mx = 0
    for i in range(len(a_sums)):
        if a_sums[i] > k:
            break
        b_take_ind = binary_search(b_sums,k-a_sums[i])
        if b_take_ind < 0:
            b_take = 0
        else:
            b_take = b_take_ind
        mx = max(mx,i + b_take)
    print(mx)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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]

ans = 0

for i, a in enumerate(A):
    time = K - a
    if time < 0:
        break
    cnt = i + 1
    if time != 0:
        tmp = bisect(B, time)
        cnt += tmp
    ans = max(ans, cnt)

for i, b in enumerate(B):
    time = K - b
    if time < 0:
        break
    cnt = i + 1
    if time != 0:
        tmp = bisect(A, time)
        cnt += tmp
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    n, m, k = map(int, input().split())
    A = [0]+list(map(int, input().split()))
    B = [0]+list(map(int, input().split()))

    from itertools import accumulate

    AA = [0] + A
    BB = [0]+B
    # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
    AA = list(accumulate(A))
    BB = list(accumulate(B))

    ans = 0
    for i in range(n+1):
        s = AA[i]
        if s > k:
            break
        rem = k-s
        idx = bisect.bisect_right(BB, rem)-1
        ans = max(ans, i+idx)
    print(ans)


resolve()

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

aa = [0] + list(itertools.accumulate(A))
bb = [0] + list(itertools.accumulate(B))

ans = bisect.bisect_left(aa, K)-1
ans = max(ans, bisect.bisect_left(bb, K)-1)

for i in reversed(range(N+1)):
    tmp_K = K-aa[i]
    if tmp_K == 0:
        ans = max(ans, i)
    elif tmp_K < 0:
        continue

    if i + M <= ans:
        continue

    if tmp_K >= bb[-1]:
        ans = max(ans, i+M)
        continue

    ans = max(ans, bisect.bisect_left(bb, tmp_K)-1+i)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_right

R = lambda: map(int, input().split())
*_, k = R()
a = accumulate(R())
b = list(accumulate(R()))
r = bisect_right(b, k)
for i, x in enumerate(a, 1):
  if x > k:
    break
  j = bisect_right(b, k - x)
  r = max(r, i + j) 
print(r)

Submission status: Accepted

Solution code:
import bisect

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

A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

WA = [0] * (N + 1)
WB = [0] * (M + 1)
for i in range(N):
    WA[i + 1] = WA[i] + A[i]
for j in range(M):
    WB[j + 1] = WB[j] + B[j]
ma = 0
last = False
for i in range(0, N + 1):
    if WA[i] > K:
        break
    t = K - WA[i]
    j = bisect.bisect(WB, t)
    ma = max(ma, i + j - 1)

print(ma)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
from sys import stdin
input = stdin.readline


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

  ac_A = [0]*(len(A)+1)
  for i, a in enumerate(A):
    ac_A[i+1] = ac_A[i] + a
  ac_A.append(float('inf'))

  ac_B = [0]*(len(B)+1)
  for i, b in enumerate(B):
    ac_B[i+1] = ac_B[i] + b
  ac_B.append(float('inf'))

  # print(ac_A)
  # print(ac_B)

  ai = 0
  bi = 0
  max_num_book = 0
  for ai, sa in enumerate(ac_A):
    if K - sa < 0:
      continue
    bi = bisect.bisect_right(ac_B, K-sa) -1
    max_num_book = max(max_num_book, ai+bi)
    # print(ai, bi, max_num_book, K-sa)

  print(max_num_book)
#   while (ai < len(A) or bi < len(B)):
#     if ai >= len(A):
#       bi += 1
#     elif bi >= len(B):
#       ai += 1
#     elif (ac_A[ai+1] < ac_B[bi+1]):
#       ai += 1
#     else:
#       bi += 1
# 
#     if K >= ac_A[ai] + ac_B[bi]:
#       num_book += 1
#     else:
#       break

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

sa=[0]*(n+1)
sb=[0]*(m+1)
s=0
for i in range(n):
  s+=a[i]
  sa[i+1]=s
s=0
for i in range(m):
  s+=b[i]
  sb[i+1]=s

if sa[n]+sb[m]<=k:
  print(n+m)
  exit()

ans=0
j=0
for i in reversed(range(n+1)):
  if sa[i]+sb[j]>k:
    continue
  while j<m and sa[i]+sb[j+1] <= k:
    j+=1
  if sa[i]+sb[j] <= k and ans<i+j:
    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()))
s_a = [0]*(n+1)
s_b = [0]*(m+1)
for i in range(1,n+1):
    s_a[i] = s_a[i-1] + a[i-1]
for i in range(1,m+1):
    s_b[i] = s_b[i-1] + b[i-1]
import bisect
Sa = bisect.bisect_right(s_a,k) -1
Sb = bisect.bisect_right(s_b,k) -1
ans = max(Sa,Sb)
for i in range(1,Sa+1):
    x = max(0, k - s_a[Sa-i+1])
    y = bisect.bisect_right(s_b,x)
    ans = max(ans,y+Sa-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()))
SA=[]
SB=[]
goukeiA=0
goukeiB=0
for i in range(N):
    goukeiA+=A[i]
    SA.append(goukeiA)
for i in range(M):
    goukeiB+=B[i]
    SB.append(goukeiB)

#def binary_search()
Mcount=0



for i in range(N+1):
    if i!=N:
        
    
        count=0
        nokori=K-SA[i]
        if nokori >=0 and nokori >=SB[M-1]:
            count+=i+1+M
        elif nokori >=0:
            count+=i+1
            tmp=nokori
            left=0
            right=M-1
            #flag=False
            while left<=right:
                #print("mohu")
                mid=(left+right)//2
                if SB[mid]<=nokori and SB[mid+1]>nokori:
                    count+=mid+1
                    #print("es",count,mid)
                    break
                elif SB[mid]>nokori:
                    #print(nokori,mid)
                    right=mid-1
                elif SB[mid]<nokori:
                    #print(nokori,mid)
                    left=mid+1
                else:
                    print("イレギュラーな例につかまりました")
                    exit()
    else:
        count=0
        nokori=K
        if nokori >=SB[M-1]:
            count+=M
        elif nokori >0:
            tmp=nokori
            left=0
            right=M-1
            #flag=False
            while left<=right:
                #print("mohu")
                mid=(left+right)//2
                if SB[mid]<=nokori and SB[mid+1]>nokori:
                    count+=mid+1
                    #print("es",count,mid)
                    break
                elif SB[mid]>nokori:
                    #print(nokori,mid)
                    right=mid-1
                elif SB[mid]<nokori:
                    #print(nokori,mid)
                    left=mid+1
                else:
                    print("イレギュラーな例につかまりました")
                    exit()        
    
    if Mcount<count:
        #print("kita",count)
        Mcount=count
            
    
        
print(Mcount)

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から選んでみる
minutes_a = 0
count_a = 0
for i in range(N):
    if minutes_a + A[i] > K:
        break
    minutes_a += A[i]
    count_a += 1

ans = count_a
minutes_b = 0
count_b = 0

for i in range(M):
    if minutes_a + minutes_b + B[i] > K:
        found = False
        while count_a > 0:
            minutes_a -= A[count_a - 1]
            count_a -= 1
            if minutes_a + minutes_b + B[i] <= K:
                minutes_b += B[i]
                count_b += 1
                found = True
                break
        if not found:
            break
    else:
        minutes_b += B[i]
        count_b += 1
    ans = max(ans, count_a + count_b)

print(ans)