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: Time Limit Exceeded

Solution code:
N = int(input())
prices = [int(n) for n in input().split()]
money = 1000
stock = 0
for n in range(N-1):
    p_today = prices[n]
    p_tomm = prices[n+1]
    if p_tomm >= p_today:
        while money >= p_today:
            stock += 1
            money -= p_today
    else:
        money += p_today * stock
        stock = 0

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

print(money)

Submission status: Time Limit Exceeded

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

s = (1000, 0, 0)
mmax = 1000

q = []
q.append(s)
while len(q) > 0:
    m,k,d = q.pop()
    if d == N-1:
        m += k*A[d]
        if mmax < m:
            mmax = m
    else:
        q.append((m,k,d+1))
        if m > A[d]:
            x = m // A[d]
            nm = m-x*A[d]
            nk = k+x
            q.append((nm,nk,d+1))
        if k > 0:
            nm = m+k*A[d]
            q.append((nm, 0, d+1))
            x = nm // A[d]
            if x > 0:
                q.append((nm - x*A[d], x, d+1))
print(mmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = list(map(int,input().split()))
m = 1000
ans = 1000
ans_list=[]

q = deque([[1000, 0, n, 0]])

while len(q) != 0:
    tmp = q.popleft()
    m,k,d,i = tmp[0],tmp[1],tmp[2],tmp[3]
    if d == 0 and m > ans:
        ans = m
        ans_list.append(m)
    elif d > 1:
        x = m//a[i]
        q.append([m-(x*a[i]),x+k,d-1,i+1])
        q.append([m+(k*a[i]),0,d-1,i+1])
        q.append([m,k,d-1,i+1])
    elif d == 1:
        q.append([m+(k*a[i]),0,d-1,i+1])

print(ans)

Submission status: Time Limit Exceeded

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

money = 1000
all_results = []
def dfs(day, money, kab):
    if day == N:
        money += A[-1]*kab
        all_results.append(money)

    else:
        # buy
        buy_kab = 1
        while money-A[day-1]*buy_kab >= 0:
            dfs(day+1, money-A[day-1]*buy_kab, kab+buy_kab)
            buy_kab += 1
        # sell or do nothing
        for sell_kab in range(0, kab+1):
            dfs(day+1, money+A[day-1]*sell_kab, kab-sell_kab)

dfs(1, 1000, 0)
print(max(all_results))

Submission status: Time Limit Exceeded

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)
def dfs(money,kabu,now):
    global ans
    if now == len(lis):
        ans = max(money,ans)
        return;
    dfs(money + kabu*lis[now],0,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: Time Limit Exceeded

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

money = 1000
num = 0
buy_p = 0
i = 0

while(i<N-1):
    if A[i] >= A[i+1]:
        i += 1
        continue
    elif i == N-2:
        if A[i] < A[N-1]:
            num = money // A[i]
            money -= A[i] * num
            money += A[N-1] * num
            break
    for j in range(i+2, N):
        if A[j-1] > A[j]:
            num = money // A[i]
            money -= A[i] * num
            money += A[j-1] * num
            i = j

print(money)

Submission status: Time Limit Exceeded

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

A.append(0)

B = []
f = True
for i in range(N):
    if f:
        if A[i] < A[i+1]:
            B.append(A[i])
            f = False
    else:
        if A[i] > A[i+1]:
            B.append(A[i])
            f = True


if len(B) == 0:
    print(1000)
else:
    res = 1000
    for i in range(2**len(B)):
        en = 1000
        ka = 0
        for j in range(len(B)):
            if (i>>j)&1:
                if j % 2 == 0:
                    if en // B[j] == 0:
                        break
                    ka = en//B[j]
                    en %= B[j]
                else:
                    if ka == 0:
                        break
                    en += ka*B[j]
                    ka = 0
        else:
            res = max(en, res)

    print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#n, k = map(int,input().split())
n = int(input())
al = list(map(int,input().split()))

ans = 0
for v in itertools.product(range(3),repeat=n):
    money = 1000
    kabu = 0

    for i in range(n):
        if v[i] == 0:
            kabu += money // al[i]
            money = money % al[i]
        elif v[i] == 1:
            money += kabu * al[i]
            kabu = 0
        else:
            continue
    ans = max(ans, money)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=10**30
N=int(input())
A=list(map(int,input().split()))
s=sum(A)
dp=[[-INF]*(s+1) for i in range(N+1)]
dp[0][0]=1000
for i in range(N):
    for j in range(s+1):
        if dp[i][j]==-INF:
            continue
        for x in range(j+1):
            dp[i+1][j-x]=max(dp[i+1][j-x],dp[i][j]+A[i]*x)
        for x in range(dp[i][j]//A[i]+1):
            dp[i+1][j+x]=max(dp[i+1][j+x],dp[i][j]-A[i]*x)
print(max(dp[N]))

Submission status: Time Limit Exceeded

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

ans = 1000
buy = -1
for bit in range(2 ** n):
    money = 1000
    stock = 0
    for i in range(n):
        if (bit >> i) & 1:
            buy = i
            stock += money // A[i]
            money -= A[i] * (money // A[i])
        else:
            if buy == -1:
                continue
            elif A[buy] < A[i]:
                money += stock * A[i]
                stock = 0
    money += stock * A[-1]
    if money > ans:
        ans = money

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 全部使え オールオアナッシングや

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


def rec(i, money, stock):
    if i == n:
        return money
    # 有り金全部株に変える
    ret2 = 0
    if money > 0:
        p = money // a[i]
        ret2 = rec(i + 1, money - p * a[i], stock + p)
    # 有り株全部金に変える
    ret3 = 0
    if stock > 0:
        ret3 = rec(i + 1, money + stock * a[i], 0)
    return max(money, ret2, ret3)


print(rec(0, 1000, 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(lambda: 0)
d[0] = 1000

for i in range(N):
    dd = d.copy()
    for s,m in dd.items():
        temp = m//A[i]
        for j in range(1,temp+1):
            if(d[s+j]<m-j*A[i]):
                d[s+j]=m-j*A[i]
        for j in range(1,s+1):
            if(d[s-j]<m+j*A[i]):
                d[s-j]=m+j*A[i]

print(d[0])

Submission status: Time Limit Exceeded

Solution code:
INF=10**30
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(dp[i][j]//A[i]+1):#売る
            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: Time Limit Exceeded

Solution code:
N = int(input())
price = list(map(int,input().split()))
price.append(0)
stock = 0
money = 1000
for i in range(N):
    if price[i] <= price[i+1]:
        while money >=price[i]:
            stock += 1
            money -= price[i]
    else:
        while stock>0:
            money += price[i]
            stock-=1
print(money)

Submission status: Time Limit Exceeded

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

now = 1000
a = 0
ans = []


for i in range(2**N):
    now = 1000
    a = 0
    for j in range(N):
        if i >> j & 1:
            t = now // A[j]
            a += t
            now -= A[j] * t
        else:
            now += a * A[j]
            a = 0
    now += a * A[-1]
    ans.append(now)

print(max(ans))

Submission status: Time Limit Exceeded

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

memo = {}


def solve(i, j, k):
    if i == N - 1:
        return j + A[i] * k
    if (i, j, k) in memo:
        return memo[(i, j, k)]
    res = max(solve(i + 1, j, k),
              solve(i + 1, j % A[i], k + j // A[i]),
              solve(i + 1, j + A[i] * k, 0))
    memo[(i, j, k)] = res
    return res


print(solve(0, 1000, 0))

Submission status: Time Limit Exceeded

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]:
        continue
    elif A[i] > A[i + 1]:
        while stock > 0:
            money += A[i]
            stock -= 1
    elif A[i] < A[i + 1]:
        while money >= A[i]:
            money -= A[i]
            stock += 1
while stock > 0:
    money += A[N - 1]
    stock -= 1

print(money)

Submission status: Time Limit Exceeded

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))
    memo[(idx, stocks)] = money
    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: Time Limit Exceeded

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]
N = rri()
arr = rrm()
def solve(N, arr):
    memo = {}
    def find(status, cur_money, idx):
        if (status, cur_money, idx) in memo:
            return memo[(status, cur_money, idx)]
        if idx == N-1:
            if not status:
                return cur_money
            else:
                return cur_money+ status * arr[idx]
        ans = cur_money
        if status == 0:
            nxt_status = cur_money//arr[idx]
            nxt_money = cur_money % arr[idx]
            for i in range(idx+1, N):
                ans = max(find(nxt_status, nxt_money, i), ans)
                ans = max(ans, find(status, cur_money, i))
        else:
            nxt_status = 0
            nxt_money = cur_money+status*arr[idx]
            for i in range(idx+1, N):
                ans = max(find(nxt_status, nxt_money, i), ans)
                ans = max(ans, find(status, cur_money, i))
        memo[(status, cur_money, idx)] = ans;
        return ans
    return find(0, 1000, 0)
print(solve(N, arr))

Submission status: Time Limit Exceeded

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

cur_m = 1000
cur_s = 0

state = -1 # 1:up 0:down
prev = 0
for ai in a:
  if state == -1:
    prev = ai
    state = 0
  elif state == 1:
    if prev > ai: # peak
      # sell at prev
      cur_m += (prev * cur_s)
      cur_s = 0
      state = 0
  else:
    if prev <= ai:
      # buy at prev
      while cur_m >= prev:
        cur_s += 1
        cur_m -= prev
      state = 1
  prev = ai

if cur_s > 0:
  cur_m += (a[-1] * cur_s)

print(cur_m)

Submission status: Time Limit Exceeded

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

ans = 1000
for bit in range(2 ** n):
    money = 1000
    stock = 0
    for i in range(n):
        if (bit >> i) & 1:
            stock += money // A[i]
            money -= A[i] * (money // A[i])
        else:
            money += stock * A[i]
            stock = 0
    if money > ans:
        ans = money

print(ans)

Submission status: Time Limit Exceeded

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())

dp = [[0]*1000 for _ in range(N+1)]
s = set([(1000, 0)])

money = 1000
for i in range(N):
    s = list(s)
    a = As[i]
    nx = set()
    for m, num in s:
        m2 = m
        cnt = 0
        while m2>=0:
            nx.add((m2, num+cnt))
            m2 -= a
            cnt += 1
        for n in range(1, num+1):
            nx.add((m+a*n, num-n))
    s = nx

lis = list(nx)
lis.sort()
print(lis[-1][0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
prices = list(map(int,input().split()))
stock_num = 0
cash = 1000

for i in range(n-1):
    if prices[i+1] >= prices[i]:
        while cash >= prices[i]:
            cash -= prices[i]
            stock_num += 1
    else:
        while stock_num != 0:
            cash += prices[i]
            stock_num -=1

while stock_num != 0:
    cash += prices[n-1]
    stock_num -=1

print(cash)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[[-1] * (5 * 10 ** 6) for _ in range(n + 1)] for _ in range(2)]
dp[0][0][1000] = 0
dp[1][0][1000] = 0
for i in range(n):
    for j in range(5 * 10 ** 6):
        dp[0][i + 1][j], dp[1][i + 1][j] = dp[0][i][j], dp[1][i][j]
    for j in range(5 * 10 ** 6):
        u, v = dp[0][i][j], dp[1][i][j]
        if max(u, v) < 0:
            continue
        dp[0][i + 1][j] = u
        dp[1][i + 1][j] = v
        # print(i, j, u, v)
        dp[0][i + 1][j + max(u, v) * a[i]] = 0
        dp[1][i + 1][j % a[i]] = max(u, v) + j // a[i]
ans = 0
for j in range(5 * 10 ** 6):
    if dp[0][n][j] != -1 or dp[1][n][j] != -1:
        ans = max(ans, j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
money = 1000
kabu = 0
for i in range(N-1):
    if A[i+1] < A[i]:
        while kabu != 0:
            money += A[i]
            kabu -= 1
    else:
        while money >= A[i]:
            money -= A[i]
            kabu += 1
while kabu != 0:
    money += A[-1]
    kabu -= 1
print(money)

Submission status: Time Limit Exceeded

Solution code:
import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    @lru_cache(maxsize=None)
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        # sell
        best = max(best, maxProfitAtEnd(i + 1, money + stocks * A[i], 0))
        # buy
        numStock = money // A[i]
        best = max(
            best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
        )

        return best

    return maxProfitAtEnd(0, 1000, 0)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from numba import jit

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


Money=1000
Kabu=0

#@jit
def MoneyWar(Money,Kabu,A,N):
  for i in range(N-1):
    if A[i]<A[i+1]:
      while True:
        if Money-A[i]>=0:
          Money-=A[i]
          Kabu+=1
        else:
          break
    if A[i]>A[i+1]:
      while True:
        if Kabu>0:
          Money+=A[i]
          Kabu-=1
        else:
          break

  if Kabu>0:
    Money+=Kabu*A[-1]
    
  return Money

print(MoneyWar(Money,Kabu,A,N))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
aa = tuple(map(int, input().split()))

def dfs(money, stock, i):
    global aa
    global n

    if i == n:
        return money

    ns = money // aa[i]
    return max(
        dfs(money, stock, i + 1),
        dfs(money + stock * aa[i], 0, i + 1),
        dfs(money - aa[i] * ns, stock + ns, i + 1)
    )

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
M = 1000
for i in range(n-1):
    dp = list(range(M+1))
    a, b = A[i], A[i+1]
    for j in range(M+1):
        if j >= a:
            dp[j] = max(dp[j-a]+b, dp[j])
    M = dp[M]
ans = M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        """
        # TLE
        # sell
        for numStock in range(1, stocks + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money + numStock * A[i], stocks - numStock)
            )
        # buy
        for numStock in range(1, (money // A[i]) + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
            )

        """
        # sell
        best = max(best, maxProfitAtEnd(i + 1, money + stocks * A[i], 0))
        # buy
        numStock = money // A[i]
        best = max(
            best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
        )

        return best

    return maxProfitAtEnd(0, 1000, 0)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)

Submission status: Time Limit Exceeded

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


Money=1000
Kabu=0

for i in range(N-1):
  if A[i]<A[i+1]:
    while True:
      if Money-A[i]>=0:
        Money-=A[i]
        Kabu+=1
      else:
        break
  if A[i]>A[i+1]:
    while True:
      if Kabu>0:
        Money+=A[i]
        Kabu-=1
      else:
        break

if Kabu>0:
  Money+=Kabu*A[-1]

print(Money)

Submission status: Time Limit Exceeded

Solution code:
import io
import os

from collections import Counter, defaultdict, deque


from functools import lru_cache
import sys

sys.setrecursionlimit(10 ** 5)


def solve(N, A):
    def maxProfitAtEnd(i, money, stocks):
        if i == N - 1:
            # Sell all remaining
            return money + stocks * A[i]

        # no op
        best = maxProfitAtEnd(i + 1, money, stocks)
        # sell
        for numStock in range(1, stocks + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money + numStock * A[i], stocks - numStock)
            )
        # buy
        for numStock in range(1, (money // A[i]) + 1):
            best = max(
                best, maxProfitAtEnd(i + 1, money - numStock * A[i], stocks + numStock)
            )
        return best

    return maxProfitAtEnd(0, 1000, 0)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    (N,) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)

Submission status: Time Limit Exceeded

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

B = [(1000, 0)]

for a in A:
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    B = C
    
answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)

Submission status: Accepted

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = float('inf')

N = int(input())    # 数字
A = list(map(int, input().split()))     # スペース区切り連続数字

mny = 1000
m = A[0]
for i in range(1, N):
    if A[i] < m:
        m = A[i]
    if A[i] > m:
        if i == N-1:
            num = mny // m
            mny += num * (A[i] - m)
        elif A[i+1] <= A[i]:
            num = mny // m
            mny += num * (A[i] - m)
            m = A[i+1]

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
INF=float('inf')
dp=[-INF]*(n+1)
dp[0]=1000

for i in range(1,n+1):
  dpi=dp[i-1]
  for j in range(1,i):
    dpi=max(dpi,dp[j]+(dp[j]//A[j-1])*(A[i-1]-A[j-1]))
  dp[i]=dpi
  
print(dp[n])

Submission status: Accepted

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

a.append(0)

money = 1000
h = a[0]
l = a[0]

for i in a:
  if h < i:
    h = i
  elif h > i and h > l:
    money = money//l * h + money%l
    h = l = i
  elif h > i:
    h = i
  if l > i:
    l = i

print(money)

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int,input().split()))
mon = 1000
beet = 0
p = []
m = []
if ls[1]-ls[0] > 0:
    beet += int(mon//ls[0])
    mon -= ls[0]*int(mon//ls[0])
    be = True
else:
    be = False
for i in range(n-1):
    if ls[i] < ls[i+1]:
        if be == False:
            beet += int(mon//ls[i])
            mon -= ls[i]*int(mon//ls[i])
            be = True
    if ls[i] > ls[i+1]:
        if be == True:
            mon += ls[i] * beet
            beet = 0
            be = False
if beet > 0:
    mon += beet*ls[-1]
print(mon)

Submission status: Accepted

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

flag = [-1]*n
t = 0
for i in range(n-1):
  if t == 0:
    if a[i] < a[i+1]:
      flag[i] = 0
      t = 1
  elif t == 1:
    if a[i+1] < a[i]:
      flag[i] = 1
      t = 0

if t == 1:
  for i in range(n-1, -1, -1):
    if flag[i] == 0:
      flag[i] == -1
      break
    if a[i] < a[i-1]: continue
    flag[i] = 1
    break
    
ans = 1000
s = 0
for i in range(n):
  if flag[i] == 0:
    s = ans//a[i]
    ans %= a[i]
  elif flag[i] == 1:
    ans += s*a[i]
    s = 0
print(ans)

Submission status: Accepted

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

def main(n,a):
    m = 1000
    f = 0
    for i in range(n):
        if i>0:
            if a[i]>a[i-1]:
                m += f*a[i]
                f = 0
        if i<n-1:
            if a[i]<a[i+1]:
                f += m//a[i]
                m %= a[i]
    if f!=0:
        m += f*a[i-1]
    print(m)
            

if __name__=="__main__":
    n,a = getval()
    main(n,a)

Submission status: Accepted

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

Submission status: Accepted

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

x = 1000
for i in range(n-1):
    if A[i] < A[i+1]:
        q, x = divmod(x, A[i])
        x += q*A[i+1]
print(x)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
 
x = 1000
for i in range(n-1):
    if A[i] < A[i+1]:
        q, x = divmod(x, A[i])
        x += q*A[i+1]
print(x)

Submission status: Accepted

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

buy = 201
ans = 1000
for i in range(n):
    if al[i] < buy:
        buy = al[i]

    elif al[i] > buy:
        ans = ans//buy*al[i] + ans%buy
        buy = al[i]
    # print(al[i], buy, ans)

print(int(ans))

Submission status: Accepted

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

flag = 0
y = 1000

for i in range(1,N):
    if A[i-1] < A[i] and flag == 0:
        x = y//A[i-1]
        y = y % A[i-1]
        flag = 1
    if (A[i-1] > A[i]) and flag == 1:
        y = y + A[i-1]*x
        flag = 0
    if flag == 1 and i == N-1:
        y = y + A[i]*x

print(y)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [1000] + A + [0]

ans = 1000
stock = 0

for i, a in enumerate(A):
    if i > 0 and i < N + 1:
        if A[i-1] >= a and A[i+1] >= a:
            stock += ans // a
            ans -= a * (ans // a)

        if A[i-1] <= a and A[i+1] <= a:
            ans += stock * a
            stock = 0
        
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A = LI()
    
    #DP[i][j]:=i日目に株j個持ってる場合の所持金最大値
    DP = [defaultdict(int) for _ in range(N+1)]
    DP[0][0] = 1000
    for i in range(N):
        for j,money in DP[i].items():
            #買わない
            DP[i+1][j] = max(DP[i+1][j], money)
            #売る
            DP[i+1][0] = max(DP[i+1][0], money + j*A[i])

        #0円のときのみ買う
        remain = DP[i][0]%A[i]
        buy = DP[i][0]//A[i]
        DP[i+1][0+buy] = max(DP[i+1][0+buy], remain)
    ans = DP[-1][0]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    a = LI()

    money = 1000
    mn, mx = a[0], a[0]
    up = True

    for price in a:
        if mx <= price:
            up = True
            mx = price
        else:
            if up:
                money = money//mn * mx + money%mn
            up = False
            mn, mx = price, price

    money = money//mn * mx + money%mn
    
    print(money)
            

main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
num = 1000
flag = True
flag2 = True
for i in range(1,N):
  if a[i-1]<a[i] and flag == True:
    mi = a[i-1]
    ma = a[i]
    flag = False
  elif a[i-1]<a[i] and flag == False:
    ma = a[i]
  elif a[i-1]>a[i] and flag == False:
    num = (num//mi)*ma+(num%mi)
    flag = True
  if i == N-1 and flag == False:
    num = (num//mi)*ma+(num%mi)
print(num)

Submission status: Accepted

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

groups = []
prev = A[0]
for i in range(1,n):
    if A[i] != prev:
        groups.append(prev)
        prev = A[i]
groups.append(prev)

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

money = 1000
stock = 0
if groups[0] < groups[1]:
    buy = money//groups[0]
    stock += buy
    money -= groups[0]*buy
    
for i in range(1,len(groups)-1):
    if groups[i-1] < groups[i] and groups[i] > groups[i+1]:# 周辺の最高値
        money += stock*groups[i]
        stock = 0
    elif groups[i-1] > groups[i] and groups[i] < groups[i+1]:# 周辺の最安値
        buy = money//groups[i]
        stock += buy
        money -= groups[i]*buy

money += stock*groups[-1]

print(money)