Problem:


Score: 400 points

Problem Statement

To become a millionaire, M-kun has decided to make money by trading in the next N days. Currently, he has 1000 yen and no stocks - only one kind of stock is issued in the country where he lives.

He is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next N days will be as follows:

A_1 yen on the 1-st day, A_2 yen on the 2-nd day, ..., A_N yen on the N-th day.

In the i-th day, M-kun can make the following trade any number of times (possibly zero), within the amount of money and stocks that he has at the time.

Buy stock: Pay A_i yen and receive one stock.

Sell stock: Sell one stock for A_i yen.

What is the maximum possible amount of money that M-kun can have in the end by trading optimally?

Constraints

2 \leq N \leq 80

100 \leq A_i \leq 200

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the maximum possible amount of money that M-kun can have in the end, as an integer.

Sample Input 1

7
100 130 130 130 115 115 150

Sample Output 1

1685

In this sample input, M-kun has seven days of trading. One way to have 1685 yen in the end is as follows:

Initially, he has 1000 yen and no stocks.

Day 1: Buy 10 stocks for 1000 yen. Now he has 0 yen.

Day 2: Sell 7 stocks for 910 yen. Now he has 910 yen.

Day 3: Sell 3 stocks for 390 yen. Now he has 1300 yen.

Day 4: Do nothing.

Day 5: Buy 1 stock for 115 yen. Now he has 1185 yen.

Day 6: Buy 10 stocks for 1150 yen. Now he has 35 yen.

Day 7: Sell 11 stocks for 1650 yen. Now he has 1685 yen.

There is no way to have 1686 yen or more in the end, so the answer is 1685.

Sample Input 2

6
200 180 160 140 120 100

Sample Output 2

1000

In this sample input, it is optimal to do nothing throughout the six days, after which we will have 1000 yen.

Sample Input 3

2
157 193

Sample Output 3

1216

In this sample input, it is optimal to buy 6 stocks in Day 1 and sell them in Day 2, after which we will have 1216 yen.



Sample input:
7
100 130 130 130 115 115 150


Sample output:
1685

Submission status: Runtime Error

Solution code:
def main():

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

    K = 2*10**6
    INF = 10**18
    dp = [[-INF]*K for i in range(n+1)]
    dp[0][0] = 1000
    for i in range(n):
        for j in range(K):
            dp[i+1][j] = dp[i][j]
        # sell
        for j in range(K):
            if j == 0:
                continue
            if dp[i][j] >= 0:
                #if i == 2 and j == 10:
                    #print(dp[i+1][0], dp[i][j]+j*A[i])
                dp[i+1][0] = max(dp[i+1][0], dp[i][j]+j*A[i])
                #if i == 2 and j == 10:
                    #print(dp[i+1][0])

        # buy
        for j in range(K):
            if dp[i][j] >= 0:
                q, r = divmod(dp[i][j], A[i])
                dp[i+1][q] = max(r, dp[i+1][q])
    #print(dp[1])
    ans = -INF
    for j in range(K):
        ans = max(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
As = list(map(int, input().split()))
judge = max(As)
max_index = As.index(judge)
preans = []
hand = 1000
kabu = 0
while As:
    a = As.pop(0)
    if a < judge:
        preans.append(a)
    else:
        buy = min(preans)
        while hand >= buy:
            kabu += 1
            hand-= buy
        hand += kabu * a
        kabu = 0
        preans = []
        if As:
            judge = max(As)
print(hand)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
money = 1000
kabu = 0
ind = 0
max_value = 0
min_value = 0
for i in range(n):
    if i == n-1:
        money += kabu*a[i]
        kabu = 0
    else:
        max_value = max(a[i:])
        ind = a.index(max_value)
        min_value = min(a[i:ind])

        if a[i]==min_value and a[i]<max_value:
            kau = money//a[i]
            kabu += kau
            money -= kau*a[i]
        else:
            money += kabu*a[i]
            kabu = 0


print(money)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [[-1 for _ in range(N+1)] for _ in range(100)]
dp[0][0] = 1000
for n in range(1,N):
    for i in range(250):
        # n日目
        for j in range(250):
        # n-1日目
            if dp[j][n-1] != -1:
                dp[i][n] = max(dp[j][n-1]+(j-i)*A[n-1],dp[i][n])
ans = 1000
for i in range(20):
    if dp[i][-2] != -1:
        if dp[i][-2]+i*A[-1] > ans:
            ans = dp[i][-2]+i*A[-1]
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
tl=[l[0]]
for i in range(1,n):
    if l[i]!=l[i-1]:
        tl.append(l[i])


a=[]
ma=False

for i in range(len(tl)):
    if i==0:
        if tl[i]>tl[i+1]:
            ma=True
            a.append(tl[i])
        else:
            ma=False
            a.append(tl[i])
    elif i==len(tl)-1:
        if tl[i]>tl[i-1]:
            a.append(tl[i])
        else:
            a.append(tl[i])
    else:
        if tl[i-1]<tl[i] and tl[i+1]<tl[i]:
            a.append(tl[i])
        elif tl[i-1]>tl[i] and tl[i+1]>tl[i]:
            a.append(tl[i])

if ma:
    a.pop(0)


num=0
ans=1000

for i in range(0,len(a)-1,2):
    thing1=(ans//a[i])*a[i+1]
    thing2=num*a[i+1]
    if thing1>thing2:
        ans=thing1+ans%a[i]
        num=0
        
    elif thing2>thing1:
        ans=thing2

print(ans)

Submission status: Runtime Error

Solution code:

def main():
    _ = int(input())
    A = list(int(c) for c in input().split(' '))

    if len(A) == 2 and A[0] == A[1]:
        return 1000

    tmp = []
    for i in range(len(A)-1):
        if A[i] != A[i+1]:
            tmp.append(A[i])
    if A[-1] != tmp[-1]:
        tmp.append(A[-1])
    A = tmp
    #print(A)

    money = 1000
    if len(A) < 2:
        return 1000

    if len(A) == 2:
        if A[0] < A[1]:
            kabu = money // A[0]
            money -= kabu*A[0]
            money += kabu*A[1]
            return money
        else:
            return 1000

    l = []
    kabu = 0
    if A[1] > A[0]:
        ascending = True
        kabu = money // A[0]
        money -= kabu*A[0]
    else:
        ascending = False
    for i in range(len(A)-1):
        #print(A[i],kabu,money)
        if ascending:  #上昇中
            if A[i] > A[i+1]:
                #下降に転じたので売り
                if kabu > 0:
                    money += kabu*A[i]
                    kabu = 0
                    ascending = False
                else:
                    pass
            else:
                continue
        else:  #下降中
            if A[i] < A[i+1]:
                #上昇したので買い
                assert kabu == 0
                kabu = money // A[i]
                money -= kabu*A[i]
                ascending = True
            else:
                continue
    if kabu > 0:
        money += kabu*A[-1]
        kabu = 0
    return money
if __name__ == "__main__":
    ret = main()
    print(ret)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[int(i) for i in input().split()]
k=max(l)
k1=l.index(k)
l=sorted(l[:k1+1])
if(l[0]==k):
    print(1000)
else:
    y=1000
    c=0
    m=0
    c2=0
    for i in range(k1):
        c1=0
        for j in range(k1):
            if(l[j]>l[i]):
                c1=1
                break
        if(c1==0 and m==0):
            break
        elif(c1==0 and m==1):
            y+=(l[i]*c)
            break
        else:
            if(m==0):
                if(c2!=0):
                    if(l[i]<k1):
                        m=1
                        c=y//l[i]
                        y%=l[i]
                        k=l[i]
                else:
                    c2=1
                    m=1
                    c=y//l[i]
                    y%=l[i]
                    k=l[i]
            else:
                if(l[i]>k):
                    y+=(l[i]*c)
                    k1=l[i]
                    m=0
    print(max(y,(l[k1]*(1000//l[0]))))

Submission status: Runtime Error

Solution code:
x = int(input())
A = list(map(int, input().split()))

kabu=0
money=1000
x=x-1
for i in range(len(A)):
    if A[x-i]>A[x-i-1]:
        lastday=x-i
        break
    
for i in range(lastday):
    if A[i]<A[i+1]:#翌日の方が高い⇒購入
        buy=money//A[i]
        money-=A[i]*buy
        kabu+=buy
    elif A[i]>A[i+1]:#前日の方が低い⇒売却
        money+=A[i]*kabu
        kabu=0

money+=A[lastday]*kabu
print(money)

Submission status: Runtime Error

Solution code:
def main():

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

    K = 10**6
    INF = 10**18
    dp = [[-INF]*K for i in range(n+1)]
    dp[0][0] = 1000
    for i in range(n):
        for j in range(K):
            dp[i+1][j] = dp[i][j]
        # sell
        for j in range(K):
            if j == 0:
                continue
            if dp[i][j] >= 0:
                #if i == 2 and j == 10:
                    #print(dp[i+1][0], dp[i][j]+j*A[i])
                dp[i+1][0] = max(dp[i+1][0], dp[i][j]+j*A[i])
                #if i == 2 and j == 10:
                    #print(dp[i+1][0])

        # buy
        for j in range(K):
            if dp[i][j] >= 0:
                q, r = divmod(dp[i][j], A[i])
                dp[i+1][q] = max(r, dp[i+1][q])
    #print(dp[1])
    ans = -INF
    for j in range(K):
        ans = max(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
money = 1000
kabu = 0
ind = 0
max_value = 0
min_value = 0
for i in range(n):
    max_value = max(a[i:])
    ind = a.index(max_value)
    if ind==i:
        min_value = max_value
    else:
        min_value = min(a[i:ind])

    if a[i]==min_value and a[i]<max_value:
        kau = money//a[i]
        kabu += kau
        money -= kau*a[i]
    else:
        money += kabu*a[i]
        kabu = 0


print(money)

Submission status: Runtime Error

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

yen = 1000

kabu = 0

for i in range(n-1):
    if a[i] < a[i+1]:
        kabu_today = yen // a[i]
        kabu += kabu_today
        yen = yen % a[i]
        
    else:
        yen += kabu * a[i]
        kabu = 0
    
#    print(yen, kabu,a[i], a[i] < a[i+1])

yen += kabu * a[n-1]
kabu = 0

print(yen)

Submission status: Runtime Error

Solution code:

def main():
    _ = int(input())
    A = list(int(c) for c in input().split(' '))

    
    tmp = []
    for i in range(len(A)-1):
        if A[i] != A[i+1]:
            tmp.append(A[i])
    if A[-1] != tmp[-1]:
        tmp.append(A[-1])
    A = tmp
    #print(A)

    money = 1000
    if len(A) < 2:
        return 1000

    if len(A) == 2:
        if A[0] < A[1]:
            kabu = money // A[0]
            money -= kabu*A[0]
            money += kabu*A[1]
            return money
        else:
            return 1000

    l = []
    kabu = 0
    if A[1] > A[0]:
        ascending = True
        kabu = money // A[0]
        money -= kabu*A[0]
    else:
        ascending = False
    for i in range(len(A)-1):
        #print(A[i],kabu,money)
        if ascending:  #上昇中
            if A[i] > A[i+1]:
                #下降に転じたので売り
                if kabu > 0:
                    money += kabu*A[i]
                    kabu = 0
                    ascending = False
                else:
                    pass
            else:
                continue
        else:  #下降中
            if A[i] < A[i+1]:
                #上昇したので買い
                assert kabu == 0
                kabu = money // A[i]
                money -= kabu*A[i]
                ascending = True
            else:
                continue
    if kabu > 0:
        money += kabu*A[-1]
        kabu = 0
    return money
if __name__ == "__main__":
    ret = main()
    print(ret)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().strip().split()))
day=0
money=1000
stock=0
is_up=True
while day<N :
    if is_up :
        past_day=day
        while A[day]<=A[day+1]:
            day+=1
            if day==N-1:
                break
        stock=int(money/A[past_day])
        money+=stock*(A[day]-A[past_day])
        day+=1
        is_up=False
    else :
        while A[day]>=A[day+1] :
            day+=1
            if day==N-1:
                day+=1
                break
        is_up=True


print("{}".format(money))

Submission status: Runtime Error

Solution code:
def main():

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

    K = 10**5+5
    INF = 10**18
    dp = [[-INF]*K for i in range(n+1)]
    dp[0][0] = 1000
    for i in range(n):
        for j in range(K):
            dp[i+1][j] = dp[i][j]
        # sell
        for j in range(K):
            if j == 0:
                continue
            if dp[i][j] >= 0:
                #if i == 2 and j == 10:
                    #print(dp[i+1][0], dp[i][j]+j*A[i])
                dp[i+1][0] = max(dp[i+1][0], dp[i][j]+j*A[i])
                #if i == 2 and j == 10:
                    #print(dp[i+1][0])

        # buy
        for j in range(K):
            if dp[i][j] >= 0:
                q, r = divmod(dp[i][j], A[i])
                dp[i+1][q] = max(r, dp[i+1][q])
    #print(dp[1])
    ans = -INF
    for j in range(K):
        ans = max(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
strategy = ["stay"] * len(A)

trend = "down"
for i in range(len(A)):
    if i == len(A) - 1:
        new_trend = "down"
        strategy[i] = "sell"
    else:
        if A[i] < A[i+1]:
            new_trend = "up"
            if trend != new_trend:
                strategy[i] = "buy"
        elif A[i] > A[i+1]:
            new_trend = "down"
            if trend != new_trend:
                strategy[i] = "sell"
        else:
            strategy[i] = "stay"
    trend = new_trend


money = 1000
stock = 0
for s in range(len(strategy)):
    if strategy[s] == "sell":
        money = money + stock * A[s]
        stock = 0
    elif strategy[s] == "buy":
        stock = money // A[s]
        money = money - A[s] * stock
    else:
        continue
print(money)

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = [int(x) for x in input().split()]

def solve(N, A):
    S = 0
    C = [A[0]]
    for i in range(1,N):
        if A[i] == C[-1]:
            continue
        C.append(A[i])
    A = C
    C = [(A[0], '-' if A[0] <A[1] else '+')]
    for i in range(1,len(A)-1):
        if C[-1] ==  A[i]:
            continue
        if A[i-1] > A[i] <= A[i+1]:
            C.append((A[i], "-"))
        elif A[i-1] < A[i] >= A[i+1]:
            C.append((A[i], "+"))
    if C[-1][0] != A[-1]:
        C.append((A[-1], '+' if A[-1] > C[-1][0] else '-'))

    S = 0
    m = 1000
    if C and C[0][1] == '+':
        C = C[1:]
    if C and C[-1][1] == '-':
        C = C[:-1]
    #print(C,file=sys.stderr) 

    for p, s in C:
        m_ = m
        S_ = S
        if s == '+':
            m += p * S 
            S = 0
        else:
            # buy stock
            m -= (m_ // p) * p
            S = (m_ // p)
        #print(s, p, "money(%d -> %d)"%(m_, m), "stock(%d -> %d)"% (S_, S))
    print(m)

solve(N, A)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(N-1)]
for i in range(N-1):
  if A[i]<A[i+1]:
    B[i]=1
B=[0]+B
money=1000
tmp=0
up=[]
down=[]
for i in range(N-1):
  if B[i]==0 and B[i+1]==1:
    up.append(i)
  if B[i]==1 and B[i+1]==0:
    down.append(i)
   
if up:
  if down==[]:
    down.append(N-1)
  if down!=[] and down[-1]<up[-1]:
    down.append(N-1)

for i in range(len(up)):
  k=bisect.bisect_left(down,up[i])
  print(k)
  money+=(A[down[k]]-A[up[i]])*(money//A[up[i]])     
print(money)

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
lis = []
prv = -1
for i in range(n):
    if prv != A[i]:
        lis.append(A[i])
        prv = A[i]
#print(lis)
dp = [[[0] * ]
def dfs(money,kabu,now):
    global ans
    if now == len(lis):
        ans = max(money,ans)
        return;
    if kabu != 0:
        dfs(money + kabu*lis[now],0,now+1)
    if money//lis[now] >= 1:
        dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
    dfs(money,kabu,now+1)
ans = 1000
dfs(1000,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
_A = list(map(int, input().split()))
ans = 1000
A = [_A[0]]
B = []

for i in range(n-1):
  if (_A[i] != _A[i + 1]):
    A.append(_A[i+1])

flag = 0
for i in range(len(A)-1):
  if (flag == 0 and A[i] < A[i + 1]):
    flag = 1
    B.append(A[i])
  elif (flag == 1 and A[i] > A[i + 1]):
    flag = 0
    B.append(A[i])
if((A[-1] > A[-2] and flag == 1) or (A[-1] < A[-2] and flag == 0)):
  B.append(A[-1])
if(len(B) < 2):
  print(ans)
  exit()
if(B[-1] < B[-2]):
  B.pop(-1)

stock = 0
for i,b in enumerate(B):
  if(i % 2 == 0):
    stock = ans // b
    ans = ans % b
  else:
    ans = ans + stock * b
    stock = 0

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))

money = 1000
ticket = 0
for i in range(N):
    # buy
    if A[i] < A[i + 1]:
        money -= (money // A[i]) * A[i]
        ticket += money // A[i]
    elif A[i] == A[i + 1]:
        pass
    # sell
    else:
        money += A[i] * ticket
        ticket = 0

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
money = 1000
kabu = 0
ind = 0
max_value = 0
min_value = 0
for i in range(n):
    max_value = max(a[i:])
    ind = a.index(max_value)
    if ind==i:
        min_value = max_value
    else:
        min_value = min(a[i:ind])

    if a[i]==min_value and a[i]<max_value:
        kau = money//a[i]
        kabu += kau
        money -= kau*a[i]
        #print('buy')
    else:
        money += kabu*a[i]
        kabu = 0
        #print('sell')

    #print('{0} {1}'.format(money, kabu))#横に並べて表示

print(money)

Submission status: Runtime Error

Solution code:
N = int(input())
As = list(map(int, input().split()))
judge = As[0]
preans = []
hand = 1000
kabu = 0
while As:
    a = As.pop(0)
    if a <= judge:
        preans.append(a)
    else:
        buy = min(preans)
        while hand >= buy:
            kabu += 1
            hand-= buy
        hand += kabu * a
        judge = a
        kabu = 0
        preans = []
print(hand)

Submission status: Runtime Error

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
At_list = [A_list[0]]
D_list = list()
Dt_list = list()
mone = 1000
stoc = 0
for i in range(1,len(A_list)):
    D_list.append(A_list[i]-A_list[i-1])
for h in range(len(D_list)):
    if D_list[h] != 0:
        Dt_list.append(D_list[h])
        At_list.append(A_list[h + 1])
for j in range(len(Dt_list)):
    if Dt_list[j] > 0:#買う
        stoc = mone // At_list[j]
        mone = mone % At_list[j]
    elif Dt_list[j] < 0:
        mone = mone + stoc * At_list[j]
        stoc = 0
        last_sell = j
if At_list[-1] >= At_list[-2]:
    mone = mone + stoc * At_list[-1]
else:
    mone = mone + stoc * At_list[last_sell]
print(mone)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
DP = [[-1 for _1 in range(10000)] for _ in range(N) ]

for i in range(1000//A[0]+1):
    DP[0][i] = 1000 - A[0]*i

max_stock = 1000//A[0]
for j in range(1, N):
    today = A[j]
    DP[j][0] = max(DP[j-1][0], DP[j-1][max_stock] + max_stock*today)
    max_stock = DP[j-1][0]//today
    DP[j][max_stock] =  DP[j-1][0] - max_stock*today




print(DP[N-1][0])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))

money = 1000
stock = 0

for i in range(N-1):
    if A[i+1] > a[i]:
        if money >= A[i]:
            n = money // A[i]
            stock += n
            money -= A[i] * n
    elif A[i+1] == A[i]:
        continue
    else:
        if stock > 1:
            money += stock * A[i]
            stock = 0

if stock > 0:
    money += stock * A[-1]

print(money)

Submission status: Runtime Error

Solution code:
A=list(map(int,input().split()))
B=[0 for i in range(N-1)]
for i in range(N-1):
  if A[i]<A[i+1]:
    B[i]=1
B=[0]+B
money=1000
tmp=0
up=[]
down=[]
for i in range(N-1):
  if B[i]==0 and B[i+1]==1:
    up.append(i)
  if B[i]==1 and B[i+1]==0:
    down.append(i)
   
if up:
  if down==[]:
    down.append(N-1)
  if down!=[] and down[-1]<up[-1]:
    down.append(N-1)

for i in range(len(up)):
  k=bisect.bisect_left(down,up[i])
  print(k)
  money+=(A[down[k]]-A[up[i]])*(money//A[up[i]])     
print(money)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.append(-1)
up = []
pre = False 
for i in range(1,N+1):
    if A[i] > A[i-1]:
        sw = True
    elif A[i] < A[i-1]:
        sw = False
    if sw != pre:
        up.append(i-1)
    pre = sw
if up == []:
    print(1000)
    exit()
money = 1000
p = False
for j in up:
    if p == False:
        stock = money//A[j]
        money -= stock*A[j]
    else:
        money += stock*A[j]
        stock = 0
    p = not p
print(money)

Submission status: Runtime Error

Solution code:
n= int(input())
a = list(map(int,input().split()))
s=0
k=0
top=[]
bottom=[]
t=0
ans=1000
ka=0
while a[s]==a[s+1] and s<n-1:
    s+=1
if s==n-1:
    print(ans)
else:
    if a[s]>a[s+1]:
        k=-1
        t=1
    else:
        k=1

    while s<n-1:
        while a[s]*k <= a[s+1]*k and s<n-1:
            s+=1
            if s==n-1:
                break
        if k ==-1:
            bottom.append(a[s])
        else:
            top.append(a[s])
        k *= -1
        s+=1
    if k == 1:
        top.append(a[-1])
    else:
        bottom.append(a[-1])
    if t==1:
        for i in range(len(top)):
            ka+=ans//bottom[i]
            ans = ans % bottom[i]
            ans += ka*top[i]
            ka = 0
    else:
        for i in range(len(top)):
            
            if i== 0:
                ka += ans // a[i]
                ans = ans % a[i]
                ans += ka * top[i]
                ka = 0
            else:
                ka+=ans//bottom[i-1]
                ans = ans % bottom[i-1]
                ans += ka*top[i]
                ka = 0
    print(ans)

Submission status: Runtime Error

Solution code:
n,k = list(map(int,input().split()))
prod = 1
l = list(map(int,input().split()))
for i in range(k):
    prod*=l[i]

prev = prod
idx = 0
for i in range(k,n):
    new_prod = prev/l[idx]
    new_prod *= l[i]
    idx+=1
    if(new_prod>prev):
        print('Yes')
    else:
        print('No')
    prev = new_prod

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
v = []
before = 0
for i in a:
    if i!=before:v.append(i)
    before = i
money = 1000
stack = 0
if v[0]<v[1]:
    buy_point = [1]
else:
    buy_point = [0]
for i in range(1,len(v)-1):
    if v[i-1]  < v[i] < v[i+1]:
        buy_point.append(2)
    elif v[i-1]  > v[i] > v[i+1]:
        buy_point.append(0)
    elif v[i-1]  < v[i] and v[i] > v[i+1]:
        buy_point.append(-1)
    elif v[i-1]  > v[i] and v[i] < v[i+1]:
        buy_point.append(1)
    else:
        print('error')
if v[-2] < v[-1]:
    buy_point.append(-1)
else:
    buy_point.append(0)

for (i,j) in zip(v,buy_point):
    if j == 1:
        stack += money//i
        money = money%i
    elif j == -1:
        money += stack * i
        stack = 0
    elif j == 2:
        stack += money//i
        money = money%i
        
print(money)

Submission status: Runtime Error

Solution code:
a=list(map(int,input().split()))
d=1
kabu=0
ans=1000
while d<=n-1:
    if a[d]>a[d-1]:
        f=ans//a[d-1]
        kabu+=f
        ans=ans-a[d-1]*f
    if a[d]<a[d-1]:
        ans+=kabu*a[d-1]
        kabu=0
    d+=1
ans+=kabu*a[n-1]
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

money = 1000
stock = 0
if A[0] < A[1]:
    stock += (money//A[0])
    money %= A[0]
    
tmp = A[0]
for i in range(1,N):
    if tmp < A[i]:
        if i == N-1:
            money += (stock*A[i])
        if A[i] < A[i+1]:
            tmp = A[i]
            continue
        money += (stock*A[i])
        stock = 0
        tmp = A[i]
    elif tmp > A[i]:
        if i == N-1:
            money += (stock*A[i])
            break
        if A[i] > A[i+1]:
            tmp = A[i]
            continue
        stock += (money//A[i])
        money %= A[i]
        tmp = A[i]
        
print(max(money,1000))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = [A[0]]
for i in range(1, N):
  if A[i] != A[i-1]:
    X.append(A[i])
B, C = [], []
n = len(X)
status = 0
result = 1000
now_m = 1000
k = 0
if X[0]>X[1]:
  B.append(0)
else:
  C.append(0)
for i in range(1, n-1):
  if X[i-1]<X[i] and X[i]>X[i+1]:
    B.append(i)
for i in range(1, n-1):
  if X[i-1]>X[i] and X[i]<X[i+1]:
    C.append(i)
if X[n-2]<X[n-1]:
  B.append(n-1)
else:
  C.append(n-1)
S = set(B+C)
for s in S:
    if status==0:
        k = now_m//X[s]
        now_m -= k*X[s]
        status = 1
    else:
        now_m += k*X[s]
        result = max(result, now_m)
        k = 0
        status = 0
print(result)

Submission status: Runtime Error

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

money = 1000
stock = 0
if A[0] < A[1]:
    stock += (money//A[0])
    money %= A[0]
    
tmp = A[0]
for i in range(1,N):
    if tmp < A[i]:
        money += (stock*A[i])
        stock = 0
        tmp = A[i]
    elif tmp > A[i]:
        if i == N:
            money += (stock*A[i])
            break
        if A[i] > A[i+1]:
            tmp = A[i]
            continue
        stock += (money//A[i])
        money %= A[i]
        tmp = A[i]
        
print(max(money,1000))

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

memo = {}
s = set()

ans = 0
def dfs(idx, money, stocks):
    global ans
    if idx==N:
        ans = max(ans, money)
        return
    a = As[idx]
    if (idx, stocks) in s:
        if money<=memo[(idx, stocks)]:
            return
    s.add((idx, stocks))
    for num in range(1, stocks+1):
        dfs(idx+1, money+a*num, stocks-num)
    cnt = 0
    while money>=0:
        dfs(idx+1, money, stocks+cnt)
        cnt += 1
        money -= a

dfs(0, 1000, 0)
print(ans)

Submission status: Runtime Error

Solution code:

    n = int(input())
    A = list(map(int, input().split()))
    funds = 1000
    stock = 0

    for i in range(n):
        if i > 0 and A[i] > A[i-1]:
            # sell
            funds += A[i] * stock
            stock = 0
        if i < n-1 and A[i] < A[i+1]:
            # buy
            stock += funds // A[i]
            funds -= A[i] * stock

    print(funds)

resolve()

Submission status: Runtime Error

Solution code:
INF=float('inf')
N=int(input())
A=list(map(int,input().split()))
dp=[[-INF for i in range(16001)] for i in range(N+1)]
dp[0][0]=1000#dp[i][j]=i日目に株をj個持っているときの最大所持金

for i in range(N):
    for j in range(16001):
        if dp[i][j]==-INF:
            continue
        for x in range(j+1):
            if j-x>=0:
                dp[i+1][j-x]=max(dp[i][j]+A[i]*x,dp[i+1][j-x])
            else:
                break
        for x in range(1000000):
            if dp[i][j]-A[i]*x>=0:
                dp[i+1][j+x]=max(dp[i][j]-A[i]*x,dp[i+1][j+x])
            else:
                break
print(max(dp[N]))

Submission status: Runtime Error

Solution code:
n=int(input())
a_list=list(map(int,input().split()))
current=1000
kabu=0
for i in range(n-1) print(current)
  if a_list[i]<a_list[i+1] :
    kabu+=current//a_list[i]
    current=current%a_list[i]
  else :
    current+=a_list[i]*kabu
    kabu=0
current+=a_list[-1]*kabu
print(current)

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    # N, K = [int(a) for a in input().split()]
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    aa = []
    t = A[0]
    start = A[0]
    for ai in A[1:]:
        if t <= ai:
            t = ai
            if start is None:
                start = ai
            continue
        aa.append(
            (start, t)
        )
        t = ai
        start = None
    if start is not None:
        aa.append((start, A[-1]))

    m = 1000
    for a, b in aa:
        c = m // a
        m += (b - a) * c
    print(m)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dp = [[-1]*1000 for i in range(n+1)]
dp[0][0] = 1000


for i in range(n):
    for j in range(1000):
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i+1][j] >= a[i]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j]-a[i])
        
    for j in range(999,0,-1):
        if dp[i+1][j] >= 0:
             dp[i+1][j-1] = max(dp[i+1][j-1],dp[i+1][j]+a[i])
print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))

ud = [0]

if A[1] > A[0]:
    trend = 1
elif A[1] == A[0]:
    trend = 0
else:
    trend = -1

if trend != 0:
    first_trend = trend

for i in range(1,N):
    if A[i] > A[i-1]:
        if first_trend==0:
            first_trend = 1
        if trend==-1:
            ud.append(i-1)
        trend = 1
    elif A[i] < A[i-1]:
        if first_trend==0:
            first_trend = -1
        if trend==1:
            ud.append(i-1)
        trend = -1

ud.append(N-1)

M = 1000

for i in range(len(ud)):
    if first_trend == 1:
        if i%2==0 and i!=len(ud)-1:
            stock = M // A[ud[i]]
            M = stock*A[ud[i+1]] + M % A[ud[i]]
    else:
        if i%2==1 and i!=len(ud)-1:
            stock = M // A[ud[i]]
            M = stock*A[ud[i+1]] + M % A[ud[i]]


print(M)

Submission status: Runtime Error

Solution code:
import sys
k=1000
N=int(input())
L=list(map(int,input().split()))
i=0
while i<N-1:
  if L[i]<L[i+1]:
    n=L[i]
    break
  i+=1
  if i==N-1:
    print(1000)
    sys.exit()
n=0
for j in range(i,N):
  if j==N-1 and n!=0:
    m=max(L[s:])
    c=k%n
    k=((k//n)*m)+c
    n=0
    break
  if L[j]<L[j+1] and n==0:
    n=L[j]
    s=j
  if L[j]>L[j+1] and n!=0:
    m=L[j]
    c=k%n
    k=((k//n)*m)+c
    n=0
print(k)