Problem p03008 (python)

Fixed submission:
def f(a,b,N):

    tmpa,tmpb=[],[]
    for i in range(3):
        if a[i]<b[i]:
            tmpa.append(a[i])
            tmpb.append(b[i])
    a,b=tmpa,tmpb

    if len(a)==0: return N
    elif len(a)==1: return (N//a[0])*b[0]+N%a[0]

    elif len(a)==2:
        if a[0]<a[1]: a,b=a[::-1],b[::-1]

        i,ans=0,N
        while i*a[0]<=N:
            j=(N-i*a[0])//a[1]
            ans=max(ans,i*b[0]+j*b[1]+(N-i*a[0]-j*a[1]))
            i+=1
        return ans

    else:
        memo=[i for i in range(N+1)]

        for i in range(1,N+1):
            tmp=[]
            for j in range(len(a)):
                if i-a[j]>=0: tmp.append(memo[i-a[j]]+b[j])
            if tmp!=[]: memo[i]=max(tmp)
        return memo[N]

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)

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

def f(a,b,N):
    def cur(n):
        if n<0: return -2
        elif memo[n]!=-1: return memo[n]
        tmp=[]
        for i in range(3):
            if cur(n-a[i])!=-2: tmp.append(cur(n-a[i])+b[i])
        if max(tmp)>=0: memo[n]=max(tmp)
        else: memo[n]=-2
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)

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

def f(a,b,N):
    
    def cur(n):
        if n<0: return -1
        if memo[n]!=-1: return memo[n]
        tmp=[]
        for i in range(3):
            if n-a[i]>=0: tmp.append(cur(n-a[i])+b[i])
        memo[n]=max(tmp)
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)

Buggy submission (verdict: Runtime Error):
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

def f(a,b,N):
    
    def cur(n):
        if n<0: return -1
        if memo[n]!=-1: return memo[n]
        tmp=[]
        memo[n]=max(cur(n-a[i])+b[i] for i in range(3))
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

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

N=f(A,B,N)
N=f(B,A,N)
print(N)

Buggy submission (verdict: Runtime Error):
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

def f(a,b,N):
    l=[]
    for i in range(3):
        if a[i]<b[i]: l.append(i)

    if len(l)==0: return N
    if len(l)==1:
        l=l[0]
        return (N//a[l])*b[l]+N%a[l]
    elif len(l)==2:
        x,y=l[0],l[1]
        p,q=a[x],a[y]
        lcm=p*q//gcd(p,q)

        n1,n2=N-N%lcm,N%lcm
        ans1=max(n1*b[x]//p,n1*b[y]//q)
        i=0
        ans2=0
        while i*p<=n2:
            ans2=max(ans2,i*b[x]+((n2-i*p)//q)*b[y])
            i+=1
        return ans1+ans2
        
    else:
        p,q,r=a[0]
        lcm=a[0]*a[1]//gcd(a[0],a[1])
        lcm=lcm*a[2]//gcd(a[2],lcm)
        n1,n2=N-N%lcm,N%lcm
        ans1=max(n1*b[i]//a[i] for i in range(3))
        i=0
        ans2=0
        while i*a[0]<=n2:
            n3=n2-i*a[0]
            j=0
            while  j*a[1]<=n3:
                ans2=max(ans2,i*b[0]+j*b[1]+(n3-j*a[1])*b[2])
                j+=1
            i+=1
        return ans1+ans2

import sys
N=int(input())

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

N=f(a,b,N)
N=f(b,a,N)
print(int(N))