Problem p02603 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    _A=list(mi())
    A = []

    for a in _A:
        if len(A) > 0 and A[-1] == a: continue
        A.append(a)
    
    N = len(A)
    bottoms = []
    
    if N < 2:
        print(1000)
        exit()

    if A[0] < A[1]:
        bottoms.append(0)

    for i in range(N-1):
        if not i+2 < len(A): continue
        # print(A[i], A[i+1], A[i+2])
        if A[i] > A[i+1] and A[i+1] < A[i+2]:
            bottoms.append(i+1)
    
    money = 1000
    kabu = 0
    # print(bottoms)
    for bi in bottoms:
        bottom = A[bi]
        i = bi
        while i < N-1 and A[i] < A[i+1]:
            i += 1
        
        top = A[i]

        # print(bi,i)
        # print(bottom,top)
        kabu += money//bottom
        money -= money//bottom * bottom
        
        money += kabu * top
        kabu = 0
        # print("money",money)
    
    print(money)

    

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**5+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]


    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            if not m < len(dp[i]): continue
            for n in [0,m]:
                dp[i+1][m-n] = max(0,dp[i+1][m-n],dp[i][m] + A[i+1] * n)
                # assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                j = dp[i][m] // A[i+1]
                dp[i+1][m+j] = max(0,dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                _mx = max(_mx,m+j)
                # assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**5+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]


    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            for n in [0,m]:
                dp[i+1][m-n] = max(0,dp[i+1][m-n],dp[i][m] + A[i+1] * n)
                # assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                j = dp[i][m] // A[i+1]
                dp[i+1][m+j] = max(0,dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                _mx = max(_mx,m+j)
                # assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**3+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]


    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            for n in range(m+1):
                dp[i+1][m-n] = max(0,dp[i+1][m-n],dp[i][m] + A[i+1] * n)
                # assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                for j in range((dp[i][m] // A[i+1])+1):
                    dp[i+1][m+j] = max(0,dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                    _mx = max(_mx,m+j)
                    
                    # assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**3+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]


    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            for n in range(m+1):
                dp[i+1][m-n] = max(0,dp[i+1][m-n],dp[i][m] + A[i+1] * n)
                assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                for j in range((dp[i][m] // A[i+1])+1):
                    dp[i+1][m+j] = max(0,dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                    _mx = max(_mx,m+j)
                    
                    assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**3+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]


    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            for n in range(m+1):
                dp[i+1][m-n] = max(dp[i+1][m-n],dp[i][m] + A[i+1] * n)
                assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                for j in range((dp[i][m] // A[i+1])+1):
                    dp[i+1][m+j] = max(dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                    _mx = max(_mx,m+j)
                    
                    assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**3+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]

    if A[0] == max(A):
        print(1000)
        exit()
 

    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            for n in range(m+1):
                dp[i+1][m-n] = dp[i][m] + A[i+1] * n
                assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                for j in range((dp[i][m] // A[i+1])+1):
                    dp[i+1][m+j] = max(dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                    _mx = max(_mx,m+j)
                    
                    assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    # print(max(dp[N]))
    print(ans)

if __name__ == "__main__":
    main()