Problem p02623 (python)

Fixed submission:
from itertools import accumulate

def bs(t):
    l,h = 0,len(b)-1
    while l<=h:
        m = (l+h)//2
        if b[m]<t:
            l=m+1
        elif b[m]>t:
            h=m-1
        else:
            return m
    return h

n,m,k = map(int,input().split())
a = list(accumulate([0]+list(map(int,input().split()))))
b = list(accumulate([0]+list(map(int,input().split()))))
ans = 0
for idx,i in enumerate(a):
    if i<=k:
        #print(idx,bs(k-i))
        ans = max(ans,bs(k-i)+idx)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
#sys.setrecursionlimit(450000)
input = sys.stdin.readline

from functools import lru_cache


@lru_cache(maxsize=None)
def Tsundoku(i,j):
    global k
    #if dp[i][j]!=None:
    #    return dp[i][j]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        k-=a[i]
        ans1 = 1+Tsundoku(i+1,j)
        k+=a[i]
    if j<m and k-b[j]>=0:
        k-=b[j]
        ans2 = 1+Tsundoku(i,j+1)
        k+=b[j]
    #dp[i][j] = max(ans1,ans2)
    #return dp[i][j]
    return max(ans1,ans2)

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
#dp = [[None]*(m+1) for _ in range(n+1)]
ans = Tsundoku(0,0)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
#sys.setrecursionlimit(450000)
input = sys.stdin.readline

from functools import lru_cache

@lru_cache(maxsize=None)
def Tsundoku(i,j):
    global k
    if dp[i][j]!=None:
        return dp[i][j]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        k-=a[i]
        ans1 = 1+Tsundoku(i+1,j)
        k+=a[i]
    if j<m and k-b[j]>=0:
        k-=b[j]
        ans2 = 1+Tsundoku(i,j+1)
        k+=b[j]
    dp[i][j] = max(ans1,ans2)
    return dp[i][j]

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[None]*(m+1) for _ in range(n+1)]
ans = Tsundoku(0,0)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(450000)
input = sys.stdin.readline

def Tsundoku(i,j,k,n,m,dp,a,b):
    if dp[i][j]!=None:
        return dp[i][j]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        ans1 = 1+Tsundoku(i+1,j,k-a[i],n,m,dp,a,b)
    if j<m and k-b[j]>=0:
        ans2 = 1+Tsundoku(i,j+1,k-b[i],n,m,dp,a,b)
    dp[i][j] = max(ans1,ans2)
    return dp[i][j]
        
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[None]*(m+1) for _ in range(n+1)]
ans = Tsundoku(0,0,k,n,m,dp,a,b)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(400100)
input = sys.stdin.readline

def Tsundoku(i,j,k,n,m,dp,a,b):
    if dp[i][j]!=None:
        return dp[i][j]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        ans1 = 1+Tsundoku(i+1,j,k-a[i],n,m,dp,a,b)
    if j<m and k-b[j]>=0:
        ans2 = 1+Tsundoku(i,j+1,k-b[i],n,m,dp,a,b)
    dp[i][j] = max(ans1,ans2)
    return dp[i][j]
        
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [[None]*(m+1) for _ in range(n+1)]
ans = Tsundoku(0,0,k,n,m,dp,a,b)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(400010)

from sys import stdin
input = stdin.readline
def Tsundoku(i,j,k,n,m,dp,a,b):
    if (i,j) in dp:
        return dp[(i,j)]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        ans1 = 1+Tsundoku(i+1,j,k-a[i],n,m,dp,a,b)
    if j<m and k-b[j]>=0:
        ans2 = 1+Tsundoku(i,j+1,k-b[i],n,m,dp,a,b)
    dp[(i,j)] = max(ans1,ans2)
    return dp[(i,j)]
        
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = dict()
ans = Tsundoku(0,0,k,n,m,dp,a,b)
print(ans)

Buggy submission (verdict: Runtime Error):
from sys import stdin
input = stdin.readline
def Tsundoku(i,j,k):
    if (i,j) in dp:
        return dp[(i,j)]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        ans1 = 1+Tsundoku(i+1,j,k-a[i])
    if j<m and k-b[j]>=0:
        ans2 = 1+Tsundoku(i,j+1,k-b[j])
    dp[(i,j)] = max(ans1,ans2)
    return dp[(i,j)]
        
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = dict()
ans = Tsundoku(0,0,k)
print(ans)