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:
# m-solutions2020_d.py
# https://atcoder.jp/contests/m-solutions2020 : D

global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    N = int(lines[0])
    # A, B, C = list(map(int, lines[0].split()))
    # K = lines[1]
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    # 利用価値のない変動日を削除する
    difs = list()
    difs.append(values[0])
    prev = None
    for n in range(N-1):
        dif = values[n+1] - values[n]
        if dif == 0:
            pass
        elif prev is None:
            difs.append(values[n+1])
            prev = dif
        elif prev * dif < 0:
            difs.append(values[n+1])
            prev = dif

    log(f'difs=[{difs}]')

    # 初回変動が下がるだけだといらないので削除
    if difs[0] > difs[1]:
        difs = difs[1:]

    # 最終変動が下がるだけだといらないので削除
    if difs[len(difs)-2] > difs[len(difs)-1]:
        difs = difs[:-1]

    log(f'difs=[{difs}]')

    kane = 1000
    kabu = 0

    log(f'len(difs)=[{len(difs)}]')

    if difs == [] or len(difs) == 1:
        return [1000]

    for i, dif in enumerate(difs):
        if i % 2 == 0:
            log(f'kau[{dif}]')
            q, mod = divmod(kane, dif)
            kane -= q*dif
            kabu += q
        else:
            log(f'uru[{dif}]')
            kane += kabu*dif
            kabu = 0

    return [kane]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['7', '100 130 130 130 115 115 150']
        lines_export = [1685]
    if pattern == 2:
        lines_input = ['6', '200 180 160 140 120 100']
        lines_export = [1000]
    if pattern == 3:
        lines_input = ['2', '157 193']
        lines_export = [1216]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    if mode > 0:
        log(f'lines_input=[{lines_input}]')
        log(f'lines_export=[{lines_export}]')
        log(f'lines_result=[{lines_result}]')
        if lines_result == lines_export:
            log('OK')
        else:
            log('NG')
    finished = time.time()
    duration = finished - started
    log(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

money = 1000
urine = 0
kabu = 0 
n = 0
mode = ""

if N == 2 and A[0] == A[1] :
  print("1000")
  sys.exit()

if A[0] < A[1] :
  mode = "up"
  urine = A[0]
  kabu = money // urine
  money = money - kabu*urine
elif A[0] > A[1] :
  mode = "down"
else :
  while A[n] == A[n + 1]:
    if n + 2 > N :
      print("1000")
      sys.exit()
      
    if A[n + 1] < A[n + 2]:
      mode = "up"
      urine = A[n + 1]
      kabu = money // urine
      money = money - kabu*urine
      break
    elif A[n + 1] > A[n + 2]:
      mode ="down"
      break
    
    n += 1  

for i in range(N-1):
  if mode == "up" :
    if A[i] <= A[i + 1] :
      next
    elif A[i] > A[i +1] :
      mode = "down"
      money = money + kabu*A[i]

  elif mode == "down":
    if A[i] >= A[i + 1] :
      next
    elif A[i] < A[i +1] :
      mode = "up"
      urine = A[i]
      kabu = money // urine
      money = money - kabu * urine
      
if mode == "up" :
  print(money + A[N-1]*kabu)
else :
  print(money)

Submission status: Runtime Error

Solution code:
def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))

n = inN()
a = inL()

kab = 0
mon = 1000
f = []
i=0
state = 0
while(i < n-1):
    if i == 0:
        if a[i+1] > a[i]:
            f.append(1)
            state = 1
        else:
            f.append(0)
    elif state == 1:
        while(i<n-1 and a[i+1]>=a[i]):
            f.append(0)
            i+=1
        f.append(2)
        state = 0
    elif state == 0:
        while(i<n-1):
            if a[i+1]<=a[i]:
                f.append(0)
                i +=1
            else:
                f.append(1)
                i += 1
                break
    else:
        f.append(0)
    i += 1
f.append(2)
    
print(f)   
for i in range(n):

    if f[i] == 1 :
        kab += mon//a[i]
        mon = mon % a[i]
    elif f[i] == 2:
        mon += a[i]*kab
        kab = 0
    
print(mon)

Submission status: Runtime Error

Solution code:
days= int(input())
word = input().split()
nums = [0]*days
for i in range(days):
    nums[i] = int(word[i])
yen = 1000
kabu = 0

maxs = []
mins = []
if nums[0] < nums[1]:
    mins.append(0)
    
for j in range(1,days-1):
    if nums[j] < nums[j+1] and nums[j] <= nums[j-1]:
        mins.append(j)
    elif nums[j] > nums[j+1] and nums[j] >= nums[j-1]:
        maxs.append(j)
        
if nums[days-2] < nums[days-1]:
    maxs.append(days-1)

if len(maxs) == 0:
    print(1000)
elif len(maxs) == 1:
    kabu = yen // nums[mins[0]]
    yen = yen % nums[mins[0]]
    yen += kabu * nums[maxs[0]]
    print(yen)
else:
    kabu = yen // nums[mins[0]]
    yen = yen % nums[mins[0]]
    for s in range(len(maxs)-1):
        yen += kabu * nums[maxs[s]]
        kabu = yen // nums[mins[s+1]]
        yen = yen % nums[mins[s+1]]
    yen += kabu * nums[maxs[s+1]]
    print(yen)

Submission status: Runtime Error

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

money=1000

chart=[a[0]]
flag=0

for i in range(n):
    if flag==0:
        if a[i]>chart[-1]:
            chart.append(a[i])
            flag=1

    else:
        if a[i]<chart[-1]:
            cnt=0
            M=0
            for j in range(i, n):
                if a[i]<a[j]:
                    cnt+=1
                    if M<a[j]:
                        M=a[j]
            
            if cnt==0:
                break
            elif cnt==1:
                chart.append(M)
                break
            else:
                flag=0

days=len(chart)

for day in range(days):
    if day%2==0:
        contact=money//chart[i]
        money-=contact*chart[i]
    
    else:
        money+=contact*chart[i]

print(money)

Submission status: Runtime Error

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

hs = []
ls = []

i = 0
if As[1] > As[0]:
  ls.append((As[0],0))
  f = 1
elif As[1] < As[0]:
  hs.append((As[0],0))
  f = 0
else:
  fl = 1
  for j in range(2,N):
    if As[j] > As[0]:
      ls.append((As[0],0))
      f = 1
      i = j
      fl = 0
      break
    elif As[j] < As[0]:
      hs.append((As[0],0))
      f = 0
      i = j
      fl = 0
      break
  if fl == 1:
    print(1000)
    exit()
  
while i < N-1:
  if f == 1 and As[i] > As[i+1]:
    hs.append((As[i],i))
    f = 0
  elif f == 0 and As[i] < As[i+1]:
    ls.append((As[i],i))
    f = 1
  i += 1
    
if As[N-2] < As[N-1]:
  hs.append((As[N-1],N-1))
elif As[N-2] > As[N-1]:
  ls.append((As[N-1],N-1))

if len(ls) == 1 and len(hs) == 1 and ls[0][1] > hs[0][1]:
  print(1000)
  exit()
if ls[0][1] > hs[0][1]:
  del hs[0]
if hs[-1][1] < ls[-1][1]:
  del ls[-1]

Submission status: Runtime Error

Solution code:
def resolve():
    import numpy as np
    n = int(input())
    A = list(map(int, input().split()))
    C = 1000
    kabu = 0
    buy = []
    sell = []

    # for i in range(n - 1, 0, -1):
    #     if A[i] > A[i - 1]:
    #         sell.append(i)
    #         if i == 1:
    #             buy.append(0)
    #     elif A[i] < A[i - 1] and len(sell) != 0:
    #         buy.append(i)

    flag = 1
    for i in range(1, n):
        if A[i - 1] <= A[i] and flag:
            l = i - 1
            flag = 0
        elif flag == 0:
            k = C // A[l]
            C -= k * A[l]
            kabu += k

            C += kabu * A[i - 1]
            kabu = 0
            flag = 1

        # if i in buy:
        #     k = C // A[i]
        #     C -= k * A[i]
        #     kabu += k
        # elif i in sell:
        #     C += kabu * A[i]
        #     kabu = 0

#    print(l, kabu, C)
    if A[l] < A[-1]:
        k = C // A[l]
        C -= k * A[l]
        kabu += k
        C += kabu * A[-1]
    print(C)

resolve()

Submission status: Runtime Error

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

money=1000

chart=[a[0]]
flag=0

for i in range(n):
    if flag==0:
        if a[i]>chart[-1]:
            chart.append(a[i])
            flag=1

    else:
        if a[i]<chart[-1]:
            cnt=0
            M=0
            for j in range(i, n+1):
                if a[i]<a[j]:
                    cnt+=1
                    if M<a[j]:
                        M=a[j]
            
            if cnt==0:
                break
            elif cnt==1:
                chart.append(M)
                break
            else:
                flag=0

days=len(chart)

for day in range(days):
    if day%2==0:
        contact=money//chart[i]
        money-=contact*chart[i]
    
    else:
        money+=contact*chart[i]

print(money)

Submission status: Runtime Error

Solution code:
n=int(input("n?"))
a=[int(input("a?")) for i in range(n)]
mon=1000
kai=0
for i in range(n-1):
  if a[i]>a[i+1]:
    mon+=kai*a[i]
    kai=0
  elif a[i]<a[i+1]:
    kai=int(mon/a[i])
    mon-=kai*a[i]

mon+=kai*a[n-1]

print(mon)

Submission status: Runtime Error

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

for i in range(N-1,0,-1) :
    if A[i-1]>A[i] :
        if A[i]<A[i+1] :
            continue
        A.pop(i)
print(A)

if len(A)==1 :
    print(1000)
    exit()

n=len(A)
money=1000
kabu=0


for i in range(n-1) : 
    if i==n-2 :
        if A[i-1]<=A[i] :
            continue
        elif A[i-1]>A[i] :
            kabu+=money//A[i]
            money-=A[i]*(money//A[i])

    if A[i]<A[i+1] and money>=A[i] : #株を買う
        kabu+=money//A[i]
        money-=A[i]*(money//A[i])

    elif A[i]>A[i+1] and kabu>0 :    #株を売る
        money+=kabu*A[i]
        kabu=0

else :
    money+=kabu*A[n-1]
    print(money)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
#Y = 1000
#N = 7
#A = [100, 130, 130, 130, 115, 115, 150]
#K = 0

def buy(i):
    global K,Y
    K += Y // A[i]
    Y -= K * A[i]

def sell(i):
    global K,Y
    Y += K * A[i]
    K = 0

# 初日は必ず買う
buy(0)
#print(i,K,Y)
#
for i in range(1,N-1):
    if A[i] < A[i+1]:
        buy(i)
    else:
        sell(i)
    #print(i,K,Y)
    
# 最終日は必ず売る
sell(N-1)
print(Y)

Submission status: Runtime Error

Solution code:
_ = int(input())
kakaku = list(map(int, input().split()))

money = 1000
num_item = 0

up_flag = False
down_flag = False

if kakaku[0] < kakaku[1]:
    up_flag = True
else:
    down_flag = True

dp = []

if up_flag:
    dp.append(kakaku[0])

# 減=>増=>減....の形にする
for i in range(1, len(kakaku)):
    # いま増加中or下後中
    if kakaku[i - 1] > kakaku[i]:
        if down_flag:
            pass
        else:
            down_flag=True
            up_flag=False
            dp.append(kakaku[i-1])
        down_flag = True
    elif kakaku[i-1] < kakaku[i]:
        if up_flag:
            pass
        else:
            down_flag = False
            up_flag = True
            dp.append(kakaku[i-1])
        up_flag = True
    # print('up', up_flag, 'down', down_flag, 'now item',kakaku[i], 'dp', dp)

if kakaku[-2] < kakaku[-1]:
    if kakaku[-3] < kakaku[-2]:
        dp[-1] = kakaku[-1]
    else:
        dp.append(kakaku[-1])

# print(dp)

for i in range(len(dp)):
    if i % 2 == 0:
        num_item += money // dp[i]
        money -= dp[i] * num_item
    else:
        money += dp[i] * num_item
        num_item = 0
if num_item != 0:
    money += num_item * dp[-1]

print(money)

Submission status: Runtime Error

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

prices = sorted(list(set(a)),key=a.index)


curentVal = 1000
stockNum = 0

for i in range(len(prices)):
    if i == 0:
        if prices[i] < prices[i+1]:
            num = curentVal // prices[i]
            curentVal -= prices[i] * num
            stockNum += num
    elif i == len(prices) - 1:
        if prices[i-1] < prices[i]:
            num = stockNum
            curentVal += prices[i] * num
            stockNum -= num
    elif prices[i] < prices[i+1] and prices[i-1] > prices[i]:
        num = curentVal // prices[i]
        curentVal -= prices[i] * num
        stockNum += num
    elif prices[i] > prices[i+1] and prices[i-1] < prices[i]:
        num = stockNum
        curentVal += prices[i] * num
        stockNum -= num

print(curentVal)

Submission status: Runtime Error

Solution code:
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = _ia()

    for i in range(1, n):
        if a[i]-a[i-1] > 0:
            j = i - 1
            break
    else:
        return 1000

    pairs = []
    m = a[j]
    flag = True
    for i in range(j, n-1):
        if flag and a[i+1] - a[i] < 0:
            pairs.append([m, a[i]])
            flag = False
        elif (not flag) and a[i+1] - a[i] > 0:
            m = a[i]
            flag = True
    if flag:
        pairs.append([m, a[-1]])

    w = {0: 1000}
    for p in pairs:
        low, hi = p
        tmp = {}
        for c, val in w.items():
            for a, v in enumerate(range(0, val+1, low)):
                cnt = c + a
                tmp[cnt] = max(tmp.get(cnt, 0), val - v)

        for c, val in tmp.items():
            for a in range(0, c+1):
                cnt = c - a
                w[cnt] = max(tmp.get(cnt, 0), val + a * hi)

    return max(w.values())


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
N = 2
ARR = [157, 193]

N = 6
ARR = [200, 180, 160, 140, 120, 100]

N = 7
ARR = [100, 130, 130, 130, 115, 115, 150]

N = int(input())
ARR = list(map(int, input().split()))


# N = 5
# ARR = [157, 193, 193, 193, 191]

def prepare(n, arr):
    result = []
    for i in range(n):
        if i == 0:
            result.append(arr[0])
        else:
            if arr[i] != arr[i - 1]:
                result.append(arr[i])
    return result


def calculate(arr):
    n = len(arr)
    result = []
    for i in range(n):
        if i == n-1:
            if arr[i] > arr[i-1]:
                result.append({'type': 1, 'value': arr[i]})
            if arr[i] < arr[i-1]:
                result.append({'type': 0, 'value': arr[i]})
            continue

        if arr[i + 1] > arr[i]:
            result.append({'type': 0, 'value': arr[i]})
        if arr[i+1] < arr[i]:
            result.append({'type': 1, 'value': arr[i]})

    money = 1000
    num = 0
    history = []
    for res in result:
        type = res.get('type')
        value = res.get('value')
        if type == 0:
            num += money // value
            money -= num * value
        else:
            money += num * value
            history.append(money)
            num = 0

    print(max(history))

# arr = prepare(N, ARR)
calculate(ARR)

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))
money=1000
stock=0
buy=0
flag=0
sell=300
if A[0]==max(A):
  print(money)
else:
  for i in range(n):
    if A[i]>buy and stock>0:
      money+=stock*A[i]
      stock=0
      sell=A[i]
      if sell==max(A[i:n+1]):
        flag=1
    elif A[i]<sell and flag==0 and A[i]==min(A[i:A.index(max(A[i:n+1]))]):
      stock=money//A[i]
      money-=stock*A[i]
      buy=A[i]
      sell=0
  print(money)

Submission status: Runtime Error

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

for i in range(N-1,0,-1) :
    if A[i-1]>A[i] :
        if A[i]<A[i+1] :
            continue
        A.pop(i)

if len(A)==1 :
    print(1000)
    exit()

n=len(A)
money=1000
kabu=0


for i in range(n-1) : 
    if i==n-2 :
        if A[i-1]<=A[i] :
            continue
        elif A[i-1]>A[i] :
            kabu+=money//A[i]
            money-=A[i]*(money//A[i])

    if A[i]<A[i+1] and money>=A[i] : #株を買う
        kabu+=money//A[i]
        money-=A[i]*(money//A[i])

    elif A[i]>A[i+1] and kabu>0 :    #株を売る
        if A[i+1]>=A[i+2] :          #下がり続けていれば何もしない
            continue
        elif A[i+1]<A[i+2] :
            money+=kabu*A[i]
            kabu=0

else :
    money+=kabu*A[n-1]
    print(money)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[0]*N
A=list(map(int,input().split()))
money=1000
money_temp=1000
kazu=0
for i in range(N-1):
    if(A[i]<A[i+1]):
        money=money+kazu*ma
        kazu=money//A[i]
        money_temp=max(money_temp,money-A[i]*kazu)
        money=money-A[i]*kazu
        #print('ue')
        #print(A[i])
        #print(A[i+1])
    elif(A[i]==A[i+1]):
        pass
    elif(A[i+1]<A[i]):
        stop=1
        ma=max(A[i],ma)

money=money+kazu*A[N-1]

print(max(money,money_temp))

Submission status: Runtime Error

Solution code:
def resolve():
    '''
    code here
    '''
    N = int(input())
    As = [int(item) for item in input().split()]

    deff_list = [0]
    for i in range(1,N):
        deff_list.append(As[i] - As[i-1])

    res_list = []
    is_first = True
    any_plus = False
    for i in range(1,N):
        if deff_list[i] > 0:
            any_plus = True
        
        if is_first and any_plus and deff_list[i] < 0 :
            res_list.append([i-1, As[i-1]])
            is_first = False

        if deff_list[i-1] > 0 and deff_list[i] < 0:
            res_list.append([i-1, As[i-1]])
        


    else:
        if deff_list[N-1] >= 0 and any_plus:
            res_list.append([N-1, As[N-1]])

    prev = 0
    res = 1000
    for i, val in res_list:
        temp_min = min(As[prev:i])
        temp_num = res //  temp_min
        res = temp_num * val + res % temp_min
        prev = i

    print(res)



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def stockBuySell(price, n): 

	if (n == 1): 
		return
	i = 0
	while (i < (n - 1)): 
		while ((i < (n - 1)) and
				(price[i + 1] <= price[i])): 
			i += 1

		if (i == n - 1): 
			break
        if money:
		    quantity = money//price[i]
		    money = money//quantity

		while ((i < n) and (price[i] >= price[i - 1])): 
			i += 1
		if quantity:	
            money = quantity*price[i-1]
            quantity = 0
		
		
n = int(input())
price = list(map(int, input().split()))
quantity = 0
money = 1000
stockBuySell(price, n) 
print(money)

Submission status: Runtime Error

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

hs = []
ls = []

i = 0
if As[1] > As[0]:
  ls.append((As[0],0))
  f = 1
elif As[1] < As[0]:
  hs.append((As[0],0))
  f = 0
else:
  fl = 1
  for j in range(2,N):
    if As[j] > As[0]:
      ls.append((As[0],0))
      f = 1
      i = j
      fl = 0
      break
    elif As[j] < As[0]:
      hs.append((As[0],0))
      f = 0
      i = j
      fl = 0
      break
  if fl == 1:
    print(1000)
    exit()
  
while i < N-1:
  if f == 1 and As[i] > As[i+1]:
    hs.append((As[i],i))
    f = 0
  elif f == 0 and As[i] < As[i+1]:
    ls.append((As[i],i))
    f = 1
  i += 1
    
if As[N-2] < As[N-1]:
  hs.append((As[N-1],N-1))
elif As[N-2] > As[N-1]:
  ls.append((As[N-1],N-1))

if len(ls) == 1 and len(hs) == 1 and ls[0][1] > hs[0][1]:
  print(1000)
  exit()
if ls[0][1] > hs[0][1]:
  del hs[0]
if hs[-1][1] < ls[-1][1]:
  del ls[-1]
  
memo = [[[0]*2 for _ in range(len(ls)+1)]  for _ in range(2)]
memo[0][0][0] = 1000
memo[0][0][1] = 0
memo[1][0][0] = 1000
memo[1][0][1] = 0

for i in range(1,len(ls)+1):
  a = memo[1][i-1][0] // ls[i-1][0]
  if a > memo[0][i-1][1]:
    memo[0][i][0] = memo[1][i-1][0]-a*ls[i-1][0]
    memo[0][i][1] = a
  else:
    memo[0][i][0] = memo[1][i-1][0]
    memo[0][i][1] = 0
  b = memo[0][i][1]*hs[i-1][0] + memo[0][i][0]
  if b > memo[1][i-1][0]:
    memo[1][i][0] = b
    memo[1][i][1] = 0
  else:
    memo[1][i][0] = memo[0][i][0]
    memo[1][i][1] = memo[0][i][1]
    
print(memo[1][-1][0])

Submission status: Runtime Error

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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


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


def main():
    N = readint()
    A = list(readnums())
    d = deque(A)
    d.appendleft(201)
    d.append(0)
    # ans = 1000 + (max(A) - min(A)) * (1000 // min(A))
    il = []
    for i in range(N):
        if d[i] <= d[i + 1] and d[i + 1] > d[i + 2]:
            il.append(i)
        elif d[i] >= d[i + 1] and d[i + 1] < d[i + 2]:
            il.append(i)

    # print(il)
    if len(il) == 1:
        print(1000)
    else:
        b = 1000
        s = 0
        if A[il[0]] < A[il[1]]:
            for i, v in enumerate(il):
                if not i % 2:
                    s += b // A[v]
                    b -= s * A[v]
                else:
                    b += s * A[v]
                    s = 0
                # print(b, s)
        else:
            for i, v in enumerate(il):
                if i % 2:
                    s += b // A[v]
                    b -= s * A[v]
                else:
                    b += s * A[v]
                    s = 0
                # print(b, s)

        print(max(1000, b))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
money = 1000
cab = 0
lowprice = A[0]
check = True
for i in range(1,N):
    if(lowprice>A[i]):
        lowprice = A[i]
        check= True
    elif(lowprice<A[i] and check == True):
        high_price = A[i]
        if(i<=N-1):
            if(high_price > A[i+1]):
                cab=money//lowprice
                money-=(lowprice*cab)
                money+=(high_price*cab)
                cab = 0
                check = False
                lowprice = high_price
        else:
            cab=money//lowprice
            money-=(lowprice*cab)
            money+=(high_price*cab)
            cab = 0
            check = False
            lowprice = high_price


print(money)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split( )))
start = 0
def f(tail,head):
    if tail < head:
        return 1
    elif tail > head:
        return -1
    else:
        return 0
i = 0
actions = ['stay' for _ in range(N)]
while f(A[i],A[i+1]) == 0:
    i += 1
if f(A[i],A[i+1]) == 1:
    actions[i] = 'buy'
else:
    actions[i] = 'stay'
before = f(A[i],A[i+1])
for j,(tail,head) in enumerate(zip(A[i+1:],A[i+2:])):
    now = f(tail,head)
    if now == before:
        before = now
    elif now == 0:
        before = before
    else:
        if before == -1:
            actions[j+i+1] = 'buy'
        else:
            actions[j+i+1] = 'sell'
        before = now
actions[-1] = 'sell'

def action(stock,money,a,price):
    if a == 'stay':
        return stock,money
    elif a == 'buy':
        stock += money//price
        money = money%price
        return stock,money
    else:
        money += stock*price
        stock = 0
        return stock,money
    
stock = 0
money = 1000
for a,price in zip(actions,A):
    stock,money = action(stock,money,a,price)
print(money)

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
LIST_A = list(map(int,input().split()))

flag = True
money = 1000
i = 0
distance = 0
upstair = False
while flag == True:
  
  #print("i:",i,"distance:",distance)
  if LIST_A[distance+1] - LIST_A[distance] >= 0:
    #print(LIST_A[1+distance])
    #print(LIST_A[distance])
    if LIST_A[distance+1] - LIST_A[distance] > 0:
      upstair = True
    else:
      upstair = "updown"
    distance += 1
    
  else:
    #print("down")
    if upstair == True or upstair == "updown":
      money += (money//LIST_A[i])*(LIST_A[distance]-LIST_A[i])
      #print(money)
      upstair = False
    	
    i += distance+1
    distance += 1
    
  	
    
  if N <= distance+1:
    if upstair == True:
      #print("distance+1",distance+1)
      #print(money)
      money += (money//LIST_A[i])*(LIST_A[distance]-LIST_A[i])
    print(money)
    sys.exit()

Submission status: Runtime Error

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

hs = []
ls = []

i = 0
if As[1] > As[0]:
  ls.append((As[0],0))
  f = 1
elif As[1] < As[0]:
  hs.append((As[0],0))
  f = 0
else:
  for j in range(2,N):
    if As[j] > As[0]:
      ls.append((As[0],0))
      f = 1
      i = j
      break
    elif As[j] < As[0]:
      hs.append((As[0],0))
      f = 0
      i = j
      break
  
while i < N-1:
  if f == 1 and As[i] > As[i+1]:
    hs.append((As[i],i))
    f = 0
  elif f == 0 and As[i] < As[i+1]:
    ls.append((As[i],i))
    f = 1
  i += 1
    
if As[N-2] < As[N-1]:
  hs.append((As[N-1],N-1))
elif As[N-2] > As[N-1]:
  ls.append((As[N-1],N-1))

if len(ls) == 1 and len(hs) == 1 and ls[0][1] > hs[0][1]:
  print(1000)
  exit()
if ls[0][1] > hs[0][1]:
  del hs[0]
if hs[-1][1] < ls[-1][1]:
  del ls[-1]
  
memo = [[[0]*2 for _ in range(len(ls)+1)]  for _ in range(2)]
memo[0][0][0] = 1000
memo[0][0][1] = 0
memo[1][0][0] = 1000
memo[1][0][1] = 0

for i in range(1,len(ls)+1):
  a = memo[1][i-1][0] // ls[i-1][0]
  if a > memo[0][i-1][1]:
    memo[0][i][0] = memo[1][i-1][0]-a*ls[i-1][0]
    memo[0][i][1] = a
  else:
    memo[0][i][0] = memo[1][i-1][0]
    memo[0][i][1] = 0
  b = memo[0][i][1]*hs[i-1][0] + memo[0][i][0]
  if b > memo[1][i-1][0]:
    memo[1][i][0] = b
    memo[1][i][1] = 0
  else:
    memo[1][i][0] = memo[0][i][0]
    memo[1][i][1] = memo[0][i][1]
    
print(memo[1][-1][0])

Submission status: Runtime Error

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

ans=1000
kabu=0
flag=0

for i in range(n-1):
    if a[i]<a[i+1]:
        if flag <=0:
            kabu=int(ans/a[i])
            ans-=(kabu*a[i])
            #print(a[i],ans,kabu)
        flag=1
    elif a[i]>a[i+1]:
        if flag >0:
            ans+=(kabu*a[i])
            #print(ans)
        flag=-1
    else:
        if flag>0:
            flag=2
        else:
            flag=-2
    if i==(n-2) and flag>0:
        ans+=(kabu*a[i+1])
        #print(a[i+1],ans)

print(ans)n=int(input())
a=list(map(int,input().split()))

ans=1000
kabu=0
flag=0

for i in range(n-1):
    if a[i]<a[i+1]:
        if flag <=0:
            kabu=int(ans/a[i])
            ans-=(kabu*a[i])
            #print(a[i],ans,kabu)
        flag=1
    elif a[i]>a[i+1]:
        if flag >0:
            ans+=(kabu*a[i])
            #print(ans)
        flag=-1
    else:
        if flag>0:
            flag=2
        else:
            flag=-2
    if i==(n-2) and flag>0:
        ans+=(kabu*a[i+1])
        #print(a[i+1],ans)

print(ans)

Submission status: Runtime Error

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

for i in range(N-1,0,-1) :
    if A[i-1]>A[i] :
        A.pop(i)

if len(A)==1 :
    print(1000)
    exit()

n=len(A)
money=1000
kabu=0


for i in range(n-1) : 
    if i==n-2 :
        if A[i-1]<=A[i] :
            continue
        elif A[i-1]>A[i] :
            kabu+=money//A[i]
            money-=A[i]*(money//A[i])

    if A[i]<A[i+1] and money>=A[i] : #株を買う
        kabu+=money//A[i]
        money-=A[i]*(money//A[i])

    elif A[i]>A[i+1] and kabu>0 :    #株を売る
        if A[i+1]>=A[i+2] :          #下がり続けていれば何もしない
            continue
        elif A[i+1]<A[i+2] :
            money+=kabu*A[i]
            kabu=0

else :
    money+=kabu*A[n-1]
    print(money)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))

max_stock = 100000
dp = np.array([[-1 for i in range(max_stock)] for _ in range(n+1)])
dp[0][0] = 1000

for i in range(n):
    for j in range(max_stock):
        if dp[i][j] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j]) # do nothing
            dp[i+1][j + dp[i][j] // a[i]] = max(dp[i][j] % a[i], dp[i+1][j + dp[i][j] // a[i]]) # buy stock
            dp[i+1][0] = max(j * a[i] + dp[i][j], dp[i+1][0]) # sell stock
print(dp[n][0])

Submission status: Runtime Error

Solution code:
def resolve():
    '''
    code here
    '''
    N = int(input())
    As = [int(item) for item in input().split()]

    deff_list = [0]
    for i in range(1,N):
        deff_list.append(As[i] - As[i-1])

    res_list = []
    is_first = True
    any_plus = False
    for i in range(1,N):
        if is_first and any_plus and deff_list[i] < 0 :
            res_list.append([i-1, As[i-1]])
            is_first = False

        if deff_list[i-1] > 0 and deff_list[i] < 0:
            res_list.append([i-1, As[i-1]])
        
        if deff_list[i] > 0:
            any_plus = True

    else:
        if deff_list[N-1] > 0:
            res_list.append([N-1, As[N-1]])

    prev = 0
    res = 1000
    for i, val in res_list:
        temp_min = min(As[prev:i])
        temp_num = res //  temp_min
        res = temp_num * val + res % temp_min
        prev = i

    print(res)



if __name__ == "__main__":
    resolve()