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: Accepted

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

# 貪欲法
# a[i] < a[i+1]なら全部買う
# a[i] > a[i+1]なら全部売る

money = 1000
stock = 0
for i in range(n):
    if i == n-1 or a[i] > a[i+1]:
        money += stock * a[i]
        stock = 0
    elif money > a[i]:
        stock = money // a[i]
        money = money % a[i]

print(money)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = list(map(int, input().split()))
    flags = [0] * n
    up = False
    prev = 1000
    for i, a in enumerate(A):
        if up:
            if a < prev:
                flags[i-1] = -1
                up = False
        else:
            if a > prev:
                flags[i-1] = 1
                up = True
        prev = a

    money = 1000
    kabu = 0
    for flag, a in zip(flags, A):
        if flag == 1:
            kabu += money // a
            money %= a

        elif flag == -1:
            money += kabu * a
            kabu = 0

    if kabu:
        money += A[-1] * kabu

    print(money)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

fm = 1000
nm = (0, 0)

for a in A:
	nfm = max(fm, nm[0] * a + nm[1])
	nnm = max(nm, (fm//a, fm - fm//a*a))

	fm, nm = nfm, nnm

print(fm)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

# N = int(input())
# A = LI()

# tmp = 1000
# stocks = 0
# for i in range(N - 1):
#     if A[i] < A[i + 1]: # 明日の方が高い　買う
#         new_stocks = tmp // A[i]
#         stocks += new_stocks
#         tmp -= new_stocks * A[i]
#     else:# 明日の方が安い　うる
#         tmp += stocks * A[i]
#         stocks = 0
# tmp += stocks * A[-1]
# print(tmp)

N = int(input())
A = LI()

cash = 1000
stocks = 0
for i in range(N - 1): 
    if A[i] < A[i + 1]: # 明日の方が高いなら買えるだけ買い
        buy_stocks = cash // A[i]
        stocks += buy_stocks
        cash -= buy_stocks * A[i]
    else: # 値段が同じor安いなら全ての株を現金化しておく
        cash += stocks * A[i]
        stocks = 0
cash += stocks * A[-1] # 最終日には全てを現金化する
print(cash)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a = list(map(int, input().split()))
  a.append(-1)
  num_kabu = 0
  money = 1000
  for i in range(0, n):
    if a[i+1] >= a[i]:
      num_kabu += money//a[i]
      money %= a[i]
    if a[i+1] <a[i]:
      money += num_kabu*a[i]
      num_kabu = 0
  print(money)
  
if __name__ =="__main__":
  main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

cur = 1000
left = 0
right = 1
while left < N:
    while right < N and A[right] > A[right - 1]:
        right += 1
    if right - left > 1:
        stocks = cur // A[left]
        cur = cur % A[left]
        cur += A[right - 1] * stocks
    left = right
    right = left + 1
print(cur)

Submission status: Accepted

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

tmp = 1000
for i in range(n-1):
    s = 0
    if a[i] < a[i+1]:
        s = tmp//a[i]
        tmp += (a[i+1]-a[i])*s
print(tmp)

Submission status: Accepted

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

minval = 0
ans = 1000

for i in range(1, N):
  if A[i] > A[minval]:
    pstock = ans // A[minval]
    ans = ans%A[minval] + A[i]*pstock
  minval = i

print(ans)

Submission status: Accepted

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

left = 0
right = left + 1
money = 1000

while left < N - 1:

    if A[left] >= A[left+1]:
        left += 1
        right = left
        continue

    if right <= N-2:
        if A[right] <= A[right+1]:
            right += 1
            continue

    money += (money//A[left]) * (A[right]-A[left])
    left = right

print(money)

Submission status: Accepted

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

ans = 0
money = 1000

for idx in range(n-1):
    today = data[idx]
    tmr = data[idx+1]
    if tmr > today:
        money += (tmr-today) * (money//today)

print(money)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
money=1000
buy=0
for i in range(N-1):
    if A[i]<=A[i+1]:
        buy=money//A[i]
        money=A[i+1]*buy+money%A[i]
print(money)

Submission status: Accepted

Solution code:
INF = 300

n = int(input())
a = [INF] + list(map(int, input().split())) + [-INF]

money = 1000
stock = 0
for e1, e2 in zip(a, a[1:]):
    if e1 < e2:
        buy = money // e1
        money -= buy * e1
        stock += buy
    else:
        money += stock * e1
        stock = 0

print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
M = 1000
S = 0
for i in range(N-1):
  M+=S*A[i]
  S = 0
  if A[i+1]>=A[i]:
    tmp=M//A[i]
    M -= tmp*A[i]
    S+=tmp
M+=S*A[-1]
S = 0
print(M)

Submission status: Accepted

Solution code:
N = int(input())

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

dp = [0] * N
dp[0] = 1000

for i in range(1, N):
    dp[i] = dp[i - 1]
    t = dp[i - 1] + (A[i] - A[i - 1]) * (dp[i - 1] // A[i - 1])
    dp[i] = max(dp[i], t)

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
a_i = list(map(int, input().split()))
preval = a_i[0]
cnt = 0
money = 1000
for x in range(1,n):
    val = a_i[x]
    if cnt == 0 and preval < val:
        cnt = money // preval
        money = money % preval
    elif cnt != 0 and preval > val:
        money += cnt * preval
        cnt = 0
    preval = val
if cnt != 0:
    money += cnt * val
print(money)

Submission status: Accepted

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]:
        stock = money // a[i]
        money += (a[i+1] - a[i]) * stock
print(money)

Submission status: Accepted

Solution code:
N = int(input())
An = list(map(int, input().split()))
money = 1000
stock = 0
for i in range(N-1):
    if An[i+1] > An[i]:
        stock = money // An[i]
        money += (An[i+1] - An[i]) * stock
print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 1000
for i in range(N - 1):
    a = A[i]
    if a < A[i + 1]:
        units = ans // a
        ans = (ans - units * a) + units * A[i + 1]
    # print(i, ans)

print(ans)

Submission status: Accepted

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

d = {}
d[0] = 1000

for i in range(n):
    e = d.copy()
    for stock, money in e.items():
        # sell
        d[0] = max(d[0], money + stock * a[i])
        # buy
        k = money // a[i]
        stock += k
        money -= k * a[i]
        d[stock] = max(d.get(stock, 0), money)

print(d[0])

Submission status: Accepted

Solution code:
def find(A):
    increase = []
    for i in range(len(A)-1):
        if A[i] <= A[i+1]:
            increase += [1]
        else:
            increase += [0]
    increase += [0]
    
    val = 1000
    hold = 0
    for i in range(len(increase)):
        if i==0:
            if increase[i] == 1:
                hold = val//A[i]
                val -= A[i]*hold
        else:
            if increase[i] == 1:
                if increase[i-1] == 0:
                    hold = val//A[i]
                    val -= A[i]*hold 
            else:
                if increase[i-1] == 1:
                    val += A[i]*hold
                    hold = 0
    return val
N = input()
A = list(map(int,input().strip().split()))
print(find(A))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
money = 1000
cnt = 0
if A[0] < A[1]:
    cnt += 1000 // A[0]
    money = money % A[0]
for i in range(1, N-1):
    if A[i] <= A[i - 1] and A[i] < A[i + 1]:
        cnt += money // A[i]
        money = money % A[i]
    elif A[i] >= A[i-1] and A[i] > A[i + 1]:
        money += cnt * A[i]
        cnt = 0
if cnt != 0:
    money += cnt * A[N - 1]
    cnt = 0
print(money)

Submission status: Accepted

Solution code:
import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

n=r()
a=rl()
money=1000
s=0

for i in range(n):
    if i==n-1:
        money+=s*a[i]
    else:
        if a[i]<=a[i+1]:
            money+=s*a[i]
            s=money//a[i]
            money%=a[i]
        else:
            money+=s*a[i]
            s=0
print(money)

Submission status: Accepted

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

money = 1000
kabu = 0
memo = []

buy = True

for i in range(n-1):
    if buy:
        if A[i] < A[i+1]:
            kabu = money //A[i]
            money %= A[i]
            buy = False
    else:
        if A[i] > A[i+1]:
            money += kabu * A[i]
            kabu = 0
            buy = True

if kabu:
    money += kabu * A[n-1]

print(money)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
S = 1000
K = 0
b = 1
last = 0
			
for i in range(N):
	if i != N-1:
		if a[i]<=a[i+1]:
			S += a[i]*K
			K = S // a[i]
			S -= K*a[i]

		else:
			S += a[i]*K
			K = 0
	else:

		S += a[i]*K
print(S)

Submission status: Accepted

Solution code:
N = int(input())

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

money = 1000

for i in range(N-1):
    t = money + (A[i + 1] - A[i]) * (money // A[i])
    money = max(money, t)

print(money)

Submission status: Accepted

Solution code:
n= int(input())
arr = [int(x) for x in input().strip().split()]


def Greedy(arr):
    
    curr = 1000
    for i in range(len(arr)-1):
        if arr[i+1]>arr[i]:
            stocks = curr // arr[i]
            curr += (arr[i+1] - arr[i])*stocks
    return curr

print(Greedy(arr))

Submission status: Accepted

Solution code:
n= int(input())
arr = [int(x) for x in input().strip().split()]


def Greedy(arr):
    
    curr = 1000
    for i in range(len(arr)-1):
        if arr[i+1]>arr[i]:
            stocks = curr // arr[i]
            curr += (arr[i+1] - arr[i])*stocks
    return curr

print(Greedy(arr))

        
# mem = {}
# def helper(i, mon, stk):
#     key = (i, mon, stk)
#     if key in mem:
#         return mem[key]
    
#     if i==len(arr):
#         return mon
    
#     ans = helper(i+1, mon, stk)
#     buy = 1
#     while True:
#         if arr[i]*buy<=mon:
#             ans = max(ans, helper(i+1, mon - arr[i]*buy, stk+buy))
#         else:
#             break
        
#         buy += 1
    
#     for s in range(1, stk+1):
#         ans = max(ans, helper(i+1, mon+arr[i]*s, stk-s))
    
#     mem[key] = ans
#     return ans

    
# print(helper(0, 1000, 0))

Submission status: Accepted

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

W = [0] * N

for i in range(1, N):
    W[i] = A[i] - A[i - 1]
B = [0]
for w in W:
    if not w == 0:
        B.append(w)
l = len(B)
money = 1000
kabu = 0
value = A[0]
for i in range(l):
    value += B[i]
    if (i == l - 1) or (B[i] > 0 and B[i + 1] < 0):
        money += kabu * value
        kabu = 0
    elif (i == 0 and B[i + 1] > 0) or (B[i] < 0 and B[i + 1] > 0):
        n = money // value
        money -= n * value
        kabu += n

print(money)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
money = 1000
for i in range(n-1):
    stock  = 0 if a[i] > a[i+1] else money // a[i]
    money += (a[i+1]-a[i])*stock
print(money)

Submission status: Accepted

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

money = 1000;stack=0

for i in range(N-1):
    if A[i]<A[i+1]:
        stack+=money//A[i]
        money %= A[i]
    elif A[i]>A[i+1]:
        money += stack*A[i]
        stack=0

money += stack*A[N-1]
stack=0

print(money)

Submission status: Accepted

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

money = 1000
stocks = 0

for n in range(N-1):
  if A[n] < A[n+1]:
    stocks += money//A[n]
    money = money%A[n]
  elif A[n] > A[n+1]:
    money += stocks*A[n]
    stocks = 0
money += stocks * A[-1]
print(money)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
money = 1000
stock = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        money += A[i]*stock
        stock = 0
    elif A[i] < A[i+1]:
        stock += money//A[i]
        money = money%A[i]
money += stock*A[-1]
print(money)

Submission status: Accepted

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

dp = [0 for _ in range(n)]
dp[0] = 1000

kabu = [0 for _ in range(n)]

for i in range(1,n):
    kabu[i-1] = dp[i-1] // a[i-1] 
    oturi = dp[i-1] - kabu[i-1]*a[i-1]
    dp[i] = max(kabu[i-1]*a[i]+oturi, dp[i-1])

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
p = 1000
k = 0
for i in range(n-1):
    if k>0 and a[i]>a[i+1]:
        p += k*a[i]
        k = 0
    elif k==0 and a[i]<a[i+1]:
        k = p//a[i]
        p %= a[i]
if k>0:
    p += k*a[-1]
print(p)

Submission status: Accepted

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

kane=1000
kabu=0
for i in range(N-1):
    #print(kane,kabu)
    
    if A[i]<A[i+1]:
        kane=kabu*A[i]+kane
        kabu=kane//A[i]
        kane=kane-kabu*A[i]
    else:
        kane=kabu*A[i]+kane
        kabu=0
        
print(kane+kabu*A[N-1])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n-1):
    if(a[i] < a[i+1]):
        #if(b[i-1] < 1):
        b[i] = 1
        #else:
        #    b[i] = 2
    if(a[i] > a[i+1]):
        #if(b[i-1] > -1):
        b[i] = -1
        #else:
        #    b[i] = -2
    #else:
        #if(b[i-1] > 0):
    #       b[i] = 2
     #   else:
      #      b[i] = -2
b[-1] = -1
#print(b)
h = [1000,0]
for i in range(n):
    if(b[i] == 1):
        h[1] += h[0]//a[i]
        h[0] %= a[i]
    elif(b[i] == -1):
        h[0] += h[1]*a[i]
        h[1] *= 0
    #print(h)
print(h[0])

Submission status: Accepted

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

dp = [0]*(N)
dp[0] = 1000

for i in range(1,N):
    dp[i] = dp[i-1]
    for j in range(i):
        dp[i] = max(dp[i], (dp[j]//A[j])*A[i]+dp[j]%A[j])
ans = 0
for i in range(N):
    ans = max(ans, dp[i])
print(ans)

Submission status: Accepted

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

money = 1000
mount = 0

f = -1
pre = a[0]
for i in range(1, len(a)):
    if f < 0:
        if a[i] <= pre:
            pre = a[i]
            continue
        mount += money // pre
        money %= pre
        f *= -1
    else:
        if a[i] >= pre:
            pre = a[i]
            continue
        money += mount * pre
        mount = 0
        f *= -1

    pre = a[i]

money += mount * a[-1]
print(money)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

# dp[i] := i日目の売却時の所持金の最大
# dp[i] = max(i-1のまま, j日目時点で買えるだけ買った株全て売却)

dp = [0] * (N+1)
dp[0] = 1000

for i in range(1, N+1):
    # print(f'i = {i}')
    max_j = 0
    for j in range(1, i):
        # print(f'j = {j}')
        q, r = divmod(dp[j-1], A[j-1])
        # print(f'q, r = {q}, {r}')
        max_j = max(max_j, A[i-1] * q + r)
    # print(f'dp[i-1] = {dp[i-1]}, max_j = {max_j}')
    dp[i] = max(dp[i-1], max_j)

# pprint(dp)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
tmp = input().split(' ')
tmp_map = map(int,tmp)
prices = list(tmp_map)
money = 1000

for i in range(n-1):
  if prices[i] < prices[i+1]:
    stocks = int(money/prices[i])
    money += stocks*(prices[i+1]-prices[i])

print(money)

Submission status: Accepted

Solution code:
input()
A=list(map(int,input().split()))
M=[0,1000]
for i in range(0,len(A)-1):
    if A[i]>A[i+1]:
        M[1]+=A[i]*M[0]
        M[0]=0
    elif A[i]<A[i+1]:
        M[0]+=int(M[1]/A[i])
        M[1]=M[1]%A[i]
M[1]+=A[i+1]*M[0]
M[0]=0
print(M[1])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 1000
S = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        S = M // A[i]
        M = M % A[i] + S*A[i+1]
        S = 0
    else:
        pass
print(M)

Submission status: Accepted

Solution code:
n=int(input())
a = input().split(" ")
lista = [int(n) for n in a]
kane=1000
k=0
for i in range(n-1):
  c=lista[i]
  d=lista[i+1]
  if c<d:
    b=kane//c
    kane-=b*c
    k+=b
  elif c>=d:
    kane+=k*c
    k=0
  if i==n-2:
    kane+=k*lista[n-1]
    k=0
print(kane)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

# 常に金額で持ち、明日のほうが上がるときのみ、必ず買って売るを繰り返す

N = int(readline())
A = list(map(int,readline().split()))

money = 1000
for i in range(N - 1):
  if A[i] < A[i + 1]:
    kabu = money // A[i]
    money %= A[i]
    money += kabu * A[i + 1]
    
print(money)

Submission status: Accepted

Solution code:
import sys
from collections import deque,defaultdict

I=sys.stdin.readline

def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))

def mi():
	return map(int,I().strip().split())


def main():
	n=ii()
	arr=li()
	p=1000
	for i in range(n-1):
		if arr[i]<arr[i+1]:
			buy=p//arr[i]
			p+=(arr[i+1]-arr[i])*buy

	
	print(p)








		


		










		






if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from collections import deque,defaultdict

I=sys.stdin.readline

def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))

def mi():
	return map(int,I().strip().split())


def main():
	n=ii()
	arr=li()
	p=1000
	for i in range(n-1):
		if arr[i]==arr[i+1]:
			pass
		elif arr[i]<arr[i+1]:
			buy=p//arr[i]
			p+=(arr[i+1]-arr[i])*buy

	
	print(p)








		


		










		






if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
a = inpl()
sign = [-1]*n

pre = -1
for i in range(1,n):
    if a[i] > a[i - 1]:
        sign[i] = 1
        pre = 1
    elif a[i] < a[i - 1]:
        sign[i] = -1
        pre = -1
    else:
        sign[i] = pre

money = 1000
stock = 0
for i in range(n):
    if sign[i] == 0 or (i != n-1 and sign[i] == sign[i + 1]):
        continue

    if sign[i] == 1:
        #売る
        money += a[i] * stock
        stock = 0
    elif sign[i] == -1:
        flg = False
        if [j for j in sign[i:] if j == 1]:
            flg = True
        #買う
        if flg == True:
            buy =  money // a[i]
            stock += buy
            money -= a[i] * buy
print(money)

Submission status: Accepted

Solution code:
import copy
def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    money = 1000
    stock = 0
    day = 0

    while day < len(A) - 1:
        if A[day + 1] - A[day] > 0:
            cur = copy.deepcopy(day)
            while day < (len(A) - 1):
                if A[day + 1] - A[day] < 0:
                    break
                else:
                    day += 1

            r, m = divmod(money, A[cur])
            stock += r
            money -= r * A[cur]
            money += stock * A[day]
            stock = 0

        elif A[day + 1] - A[day] < 0:
            cur = copy.deepcopy(day)
            while day < (len(A) - 1):
                if A[day + 1] - A[day] > 0:
                    break
                else:
                    day += 1

            if day < len(A) - 1:
                r, m = divmod(money, A[day])
                stock += r
                money -= r * A[day]

        elif A[day + 1] - A[day] == 0:
            day += 1

    print(money)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    yt = []
    p = 1
    nk = 1000
    kb = 0
    for i,na in enumerate(a[1::]):
        ai = a[i]
        if p:
            if ai < na:
                p = 0
                kb = nk//ai
                nk %= ai
        else:
            if ai > na:
                p = 1
                nk += kb*ai
                kb = 0

    print(nk+kb*a[-1])
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Stock = 0
Money = 1000
 
for i in range(N-1):
    if A[i] < A[i + 1]:

        Stock = Money // A[i]
        Money %= A[i]
        Money += Stock * A[i+1]
print(Money)

Submission status: Accepted

Solution code:
N = int(input())

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

dp = [0] * N
dp[0] = 1000

for i in range(1, N):
    dp[i] = dp[i - 1]
    for j in range(i):
        kabu = dp[j] // A[j]
        money = dp[j] + (A[i] - A[j]) * kabu
        dp[i] = max(dp[i], money)

print(dp[-1])

Submission status: Accepted

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

money = 1000
stock = 0
pivot = []
upflag = 0
dnflag = 1

if(int(a[1]) - int(a[0]) > 0): # initial
    stock = int(money // (int(a[0])))
    money = int(money % (int(a[0])))
    upflag = 1
    dnflag = 0

for i in range(n-2): # i=0,1,,,,n-3 (for n=7, n-3=4)
    if(int(a[i+1]) == int(a[i])):
        if((int(a[i+2]) - int(a[i+1]) < 0) and upflag == 1): # i+1 is local max so that to sell stock
            money = money + stock * (int(a[i+1]))
            stock = 0
            upflag = 1
            dnflag = 0
        elif((int(a[i+2]) - int(a[i+1]) > 0) and dnflag == 1): # i+1 is local min so that to sell stock
            stock = int(money // (int(a[i+1])))
            money = int(money % (int(a[i+1])))
            upflag = 0
            dnflag = 1

    elif(int(a[i+1]) - int(a[i]) > 0):
        upflag = 1
        if(int(a[i+2]) - int(a[i+1]) < 0): # i+1 is local max so that to sell stock
            money = money + stock * (int(a[i+1]))
            stock = 0
            upflag = 0

    elif(int(a[i+1]) - int(a[i]) < 0):
        dnflag = 1
        if(int(a[i+2]) - int(a[i+1]) > 0): # i+1 is local min so that to buy stock
            stock = int(money // (int(a[i+1])))
            money = int(money % (int(a[i+1])))
            dnflag = 0

if(int(a[n-1]) - int(a[n-2]) > 0): # sell @ final
    money = money + stock * (int(a[n-1]))
elif(int(a[n-1]) - int(a[n-2]) == 0):
    if(upflag == 1):
        money = money + stock * (int(a[n-1]))

print(money)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

dp = [1000]*n

for i in range(n):
    dp[i]=max(dp[i-1],dp[i])
    st,rest=divmod(dp[i],L[i])
    for j in range(i+1,n):
        dp[j] = max(dp[j],L[j]*st+rest)
print(dp[-1])

Submission status: Accepted

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


# dp[i]: 
# i日目時点で，
# あらゆる売買の組み合わせを考慮したときの
# 最適な(最大化された)所持金の値
dp = [0] * N

dp[0] = 1000 # 初日は1000円が最適
for i in range(1, N):
  
  for j in range(0, i):
    # j日目に買える最大株数vは？
    v = int(dp[j] / A[j])
    
    # j日目にv株買って(マイナスv*A[j]円)，
    # i日目までガチホして，
    # i日目の株価で全部売った時(プラスv*A[i]円)，
    # i日目の所持金wはいくらになる？
    w = dp[j] - v*A[j] + v*A[i]
    
    dp[i] = max(dp[i-1], w)
    
print(max(dp))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
stk = 0
yen = 1000
for i in range(N):
    if i == 0:
        if A[i] < A[i+1]:
            stk += yen // A[i]
            yen %= A[i]
    elif i == N-1:
        yen += stk * A[i]
    else:
        if A[i-1] <= A[i] and A[i] > A[i+1]:
            yen += A[i]*stk 
            stk = 0
        if A[i-1] >= A[i] and A[i] < A[i+1]:
            stk += yen // A[i]
            yen %= A[i]
print(yen)

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Accepted

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

t = [-1] * (N + 1)
t[0] = 1000
for i in range(N):
    k = t[i] // A[i]
    y = t[i] % A[i]
    for j in range(i, N):
        t[j + 1] = max(t[j + 1], k * A[j] + y)
print(t[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
ans = 1000
left = 0
right = 0
while left < n:
    right = left
    while right + 1 < n and a[right] <= a[right + 1]:
        right += 1
    ans = ans // a[left] * a[right] + ans % a[left]
    left = right
    left += 1
print(ans)

Submission status: Accepted

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

iStock = 0
iMoney = 1000

for i in range(N-1):
    if A[i] < A[i + 1]:
        # A[i]Day 株購入 & A[i+1]Day 株売却
        iStock = iMoney // A[i]
        iMoney %= A[i]
        iMoney += iStock * A[i+1]
print(iMoney)

Submission status: Accepted

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

iStock = 0
iMoney = 1000

for i in range(N-1):
    if A[i] < A[i + 1]:
        # A[i]Day 株購入 & a[i+1]Day 株売却
        iStock = iMoney // A[i]
        iMoney %= A[i]
        iMoney += iStock * A[i+1]
print(iMoney)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans, b = 1000, 0
    def buy(a):
        nonlocal b, ans
        b += ans // a
        ans %= a
    def sell(a):
        nonlocal b, ans
        ans += b * a
        b = 0
    if A[0] < A[1]: buy(A[0])
    for i in range(1, n - 1):
        if A[i - 1] >= A[i] < A[i + 1]:
            buy(A[i])
        elif A[i - 1] <= A[i] > A[i + 1]:
            sell(A[i])
        else:
            continue
    if b > 0:
        sell(A[-1])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = [0] + list(map(int, readline().split()))
    dp = [0] * (n + 1)
    dp[0] = 1000

    for i in range(1, n + 1):
        dp[i] = dp[i - 1]
        for j in range(1, i):
            s = dp[j] // a[j]
            m = s * a[i] + dp[j] % a[j]
            dp[i] = max(dp[i], m)

    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 1000
for i in range(n - 1):
    if a[i] < a[i + 1]:
        ans = ans % a[i] + (ans // a[i]) * a[i + 1]

print(ans)

Submission status: Accepted

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

kabu = 0
money = 1000
for i in range(n-1):
    if al[i] < al[i+1]:
        # 全部売る
        money += kabu * al[i]
        kabu = 0
        # 全部買う
        kabu += money // al[i]
        money = money % al[i]
    else:
        # 全部売る
        money += kabu * al[i]
        kabu = 0

print(money+ kabu*al[-1])

Submission status: Accepted

Solution code:
n = int(input())
a = [-1] + list(map(int, input().split()))

# dp[i] = (i+1)日目終了時点での金額の最大値
# dp[i] = max(dp[i-1], {dp[j-1] % a[j] + (dp[j-1] // a[j]) * a[i] | j<i})
dp = [0] * (n + 1)
dp[0] = dp[1] = 1000
dp[2] = max(dp[0] % a[1] + (dp[0] // a[1]) * a[2], dp[1])

for i in range(1, n + 1):
    cand = dp[i - 1]
    for j in range(1, i):
        cand = max(cand, dp[j - 1] % a[j] + (dp[j - 1] // a[j]) * a[i])
    dp[i] = cand

print(dp[n])