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: Wrong Answer

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

#dp[d][kabu]=max(money)
dp=[[-float("inf")]*1001 for _ in range(N+1)]
dp[0][0]=1000

for i in range(1,N+1):
  for j in range(1001):
    dp[i][j]=dp[i-1][j]
    for k in range(1,1001):
      #dp[i][j]=max(dp[i][j],dp[i-1][j-1]-alist[i-1])
      if j-k>=0 and dp[i-1][j-k]-k*alist[i-1]>=0:
        #buy k
        dp[i][j]=max(dp[i][j],dp[i-1][j-k]-k*alist[i-1])
      if j+k<=1000:
        # sell k
        dp[i][j]=max(dp[i][j],dp[i-1][j+k]+k*alist[i-1])
        
answer=0
for j in range(1001):
  answer=max(answer,dp[N][j])

print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

# peak = n - 1
# for n in range(N - 2, -1, -1):
#     if As[n] > As[n + 1]:
#         peak = n
#     else:
#         break

def uniq(As):
    ret = []
    for a in As:
        if not ret:
            ret.append(a)
        else:
            if ret[-1] != a:
                ret.append(a)
    return ret

As = uniq(As)
N = len(As)

ans = 0
money = 1000
stock = 0
for n in range(N):
    ans = max(ans, money + stock * As[n])

    if n == N - 1:
        break

    if As[n] < As[n + 1]:
        stock, money = divmod(money, As[n])
    elif As[n] > As[n + 1]:
        money += stock * As[n]
        stock = 0
    # print("m, s = ", money, stock)

print(ans)

Submission status: Wrong Answer

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

money = 1000
stocks = 0

for i in range (0, N-1):
    if L[i+1] > L[i]:
        stocks = money//L[i]
        money = money%L[i]
    elif L[i+1] == L[i]:
        continue
    else:
        money+= stocks*L[i]
        stocks = 0

print(money+stocks*L[-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

n, *aaa = map(int, sys.stdin.buffer.read().split())
portfolio = {0: 1000}
for a in aaa:
    new_pf = defaultdict(int)
    for stock, cash in portfolio.items():
        if stock == 0:
            buy = cash // a
            new_pf[buy] = cash - a * buy
        new_pf[0] = max(new_pf[0], cash + a * stock)

    portfolio = new_pf
    
print(portfolio[0])

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())
rising_terms = []
tmp = []
for i in range(N - 1):
    if A[i] <= A[i + 1]:
        tmp.append(A[i])
    elif tmp:
        rising_terms.append(tmp)
        tmp = []
if A[N - 2] <= A[N - 1]:
    rising_terms.append(tmp + [A[N - 1]])
ans = 1000
for rising_term in rising_terms:
    stock, r_money = divmod(ans, rising_term[0])
    ans = r_money + stock * rising_term[-1]
print(ans)

Submission status: Wrong Answer

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

mon=1000
kabu=0

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

mon += kabu*A[N-1]

print(mon)

Submission status: Wrong Answer

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

start = [[0, 1000], [0, 1000]]
#0: all stack, 1: all money
max_index = [i for i, v in enumerate(A) if v == max(A)][-1]
#print(max_index)

ans = 0
for i in range(N):
  if i == max_index:
    ans = start[0][0] * A[i] + start[0][1]
  else:
    money = max([
      start[0][0] * A[i] + start[0][1],  start[1][0] * A[i] + start[1][1]
    ])
    start = [[money//A[i], money - (money//A[i])*A[i] ],  [0, money]]
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 1000
s = A[0]
S = A[0]
for i in range(1,N):
    if s >= A[i]:
        s = A[i]
    elif S <= A[i]:
        S = A[i]
    else:
        t = ans//s
        ans = ans % s
        ans += t*S
        if i == N-1:
            break
        s,S = A[i+1],A[i+1]
    if i == N-1 and s < A[i]:
        t = ans//s
        ans = ans % s
        ans += t*A[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

    ans = 1000
    ll = rr = -1
    for a in A:
        if ll == -1:
            ll = rr = a
        elif rr <= a:
            rr = a
        else:
            q, r = divmod(ans, ll)
            ans = rr * q + r
            ll = -1

    if ll != -1:
        q, r = divmod(ans, ll)
        ans = rr * q + r

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

flg=-1
for i in range(n-1):
    if A[i]<A[i+1] and flg==-1:
        flg=1
        T.append(A[i])
    elif A[i]>A[i+1] and flg==1:
        flg=-1
        T.append(A[i])

if A[-2]<=A[-1]:
    T.append(A[-1])

kab=0
mon=1000

for i in range(len(T)):
    if i%2==0:
        kosuu=mon//T[i]
        kab+=kosuu
        mon-=kosuu*T[i]
    else:
        mon+=kosuu*T[i]
        kab=0

print(mon)

Submission status: Wrong Answer

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

print(money+stock*a_list[n-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()

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

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
uru = [0,0]
uruold = [0,1000]
kau = [0,0]
kauold = [1000 // A[0],1000 % A[0]]
for i in range(N):
    if uruold[0] * A[i] + uruold[1] < kauold[0] * A[i] + kauold[1]:
        uru[0] = 0
        uru[1] = kau[0] * A[i] + kau[1]
    else:
        uru = uruold
    if uruold[1] // A[i] + uruold[0] > kauold[1] // A[i] + kauold[0]:
        kau[0] = uruold[1] // A[i] + uruold[0]
        kau[1] = uruold[1] % A[i]
    else:
        kau = kauold
    uruold = uru
    kauold = kau
print(uru[1])

Submission status: Wrong Answer

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

cash = 1000
stock = 0

for i in range(n-1):
    if(a[i] > a[i+1]):
        cash += stock * a[i]
        stock = 0
    elif(a[i] < a[i+1]):
        stock += cash // a[i]
        cash %= a[i]
    print(cash,stock)
cash += stock * a[n-1]

print(cash)

Submission status: Wrong Answer

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=1000
num2=0
num3=-1
if max(a)!=a[0]:
    for i in range(1,n):
        if a[i-1]<a[i] and num3==-1:
            num2+=num//a[i-1]
            num-=a[i-1]*(num//a[i-1])
            num3=a[i]
        elif num3!=-1:
            if a[i-1]<a[i]:
                num3=a[i]
            if a[i-1]>a[i]:
                num+=a[i-1]*num2
                num2=0
                num3=-1
num+=max(a[-1],a[-2])*num2
print(num)

Submission status: Wrong Answer

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]:
        stock += money//a[i]
        money -= stock * a[i]
    else:
        money += stock *a[i]
        stock =0

if stock >0:
    money+=stock*a[-1]
    stock=0
print(money)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 1000
s = A[0]
S = A[0]
t = 0
for i in range(1,N):
    if s >= A[i]:
        s = A[i]
    elif S <= A[i]:
        S = A[i]
    else:
        t = ans//s
        ans = ans % s
        ans += t*S
        if i == N-1:
            break
        s,S = A[i+1],A[i+1]
    if i == N-1 and s < A[i]:
        t = ans//s
        ans = ans % s
        ans += t*S
print(ans)

Submission status: Wrong Answer

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

A.append(0)

en = 1000
kabu = 0

for i in range(N):
    if A[i] < A[i+1]:
        kabu = en//A[i]
        en %= A[i]
    if A[i] > A[i+1]:
        en += kabu*A[i]
        kabu = 0

print(en)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
n_money = 1000
n_stock = 0
for i in range(N-1):
    if A[i+1] > A[i]:
        # buy
        n_stock = n_money // A[i]
        n_money = n_money - n_stock * A[i]
    else:
        # sell
        n_money += n_stock * A[i]
        n_stock = 0
n_money += n_stock * A[N-1]
print(n_money)

Submission status: Wrong Answer

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

mon=1000
kabu=0

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

mon += kabu*A[N-1]

print(mon)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

money = 1000
stocks = 0

for i in range (0, N-1):
    if L[i+1] > L[i]:
        stocks = money//L[i]
        money = money%L[i]
    else:
        money+= stocks*L[i]
        stocks = 0

print(money+stocks*L[-1])

Submission status: Wrong Answer

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

start = [[0, 1000], [0, 1000]]
#0: all stack, 1: all money
max_index = A.index(max(A))

ans = 0
for i in range(N):
  if i == max_index:
    ans = start[0][0] * A[i] + start[0][1]
  else:
    money = max([
      start[0][0] * A[i] + start[0][1],  start[1][0] * A[i] + start[1][1]
    ])
    start = [[money//A[i], money - (money//A[i])*A[i] ],  [0, money]]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

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

anow=0
anxt=0

m=1000
s=0

for i in range(n-1):
    if A[i+1]>A[i]:
        s=m//A[i]
        m-=A[i]*(m//A[i])
    elif A[i+1]<A[i]:
        m+=A[i]*s
        s=0

m+=A[n-1]*s
print(m)

Submission status: Wrong Answer

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]:
    kabu = money//A[i]
    money -= A[i]*kabu
  elif A[i] > A[i+1]:
    money += kabu*A[i]
    kabu = 0
money += A[-1]*kabu
print(money)

Submission status: Wrong Answer

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

cash = 1000
stock = 0

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

print(cash)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    i = 0
    stock = 0
    cash = 1000
    while i+1 < N:
        if A[i] < A[i+1]:
            stock += cash // A[i]
            cash -= stock * A[i]
            # print('buy {} at {} yen'.format(stock, A[i]))
        elif A[i] > A[i+1]:
            cash += stock * A[i]
            # print('buy {} at {} yen, total cash {}'.format(stock, A[i], cash))
            stock = 0
        i += 1
    else:
        cash += stock * A[-1]
    print(cash)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
MIN=INF
MAX=0
ans=1000
for x in A:
    if x<MIN:
        MIN=x
    elif x>MAX:
        MAX=x
    elif x<MAX and MIN<MAX:
        tmp=ans//MIN
        ans-=tmp*MIN
        ans+=tmp*MAX
        MIN=x
        MAX=0
if MIN<MAX:
    tmp=ans//MIN
    ans-=tmp*MIN
    ans+=tmp*MAX
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_cur = a[0]

m = 1000
s = 0

for i in range(1, n):
    a_next = a[i]
    if a_cur > a_next:
        # sell
        m += s * a_cur
        s = 0
    elif a_cur < a_next:
        # buy
        s = m // a_cur
        m -= s * a_cur
    a_cur = a_next
if s > 0:
    m += s * a[-1]
print(m)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
MIN=INF
MAX=0
ans=1000
for x in A:
    if x<MIN:
        MIN=x
    elif x>MAX:
        MAX=x
    elif x<MAX and MIN<MAX:
        tmp=ans//MIN
        ans-=tmp*MIN
        ans+=tmp*MAX
        MIN=INF
        MAX=0
if MIN<MAX:
    tmp=ans//MIN
    ans-=tmp*MIN
    ans+=tmp*MAX
print(ans)

Submission status: Wrong Answer

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

print(m)

Submission status: Wrong Answer

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

money += sp_list[N-1] * stock

print(money)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 1000
s = A[0]
S = A[0]
t = 0
for i in range(1,N):
    if s >= A[i]:
        s = A[i]
    elif S <= A[i]:
        S = A[i]
    else:
        t = ans//s
        ans = ans % s
        ans += t*S
        s = 400
        S = 50
    if i == N-1 and s < A[i]:
        t = ans//s
        ans = ans % s
        ans += t*S
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    A=[*pin()]

    mon=1000
    stocks=0
    final=0
    for i in range(N-1):

        if A[i]>=A[i+1]:
            if stocks>0:
                mon+=stocks*A[i]
                stocks=0
            final=0
            
        elif A[i]<A[i+1]:
            stocks=mon//A[i]
            mon=mon%A[i]
            final=1

    print(mon+final*stocks*A[-1])
            
#%%submit!
resolve()

Submission status: Wrong Answer

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]: # 明日の方が高い　買う
        stocks = tmp // A[i]
        tmp -= stocks * A[i]
    else:# 明日の方が安い　うる
        tmp += stocks * A[i]
        stocks = 0

tmp += stocks * A[-1]
print(tmp)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s, n, node):
    # 頂点が探索済みかどうかのチェック配列
    check = [False for _ in range(n)]
    check[s] = True
    # 次見る頂点を格納するキュー
    queue = deque([s])
    visited_num = 1

    # 問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color = [-1 for _ in range(n)]
    color[s] = 0

    while visited_num < n:
        # グラフが全連結ではない場合
        if len(queue) == 0:
            # 空配列を返す
            # 現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex = queue.popleft()
        # インデックスがない場合は
        for next_vertex in node[now_vertex]:

            if check[next_vertex] == True:
                continue

            queue.append(next_vertex)
            check[next_vertex] = True

            # 問題固有の計算
            color[next_vertex] = color[now_vertex]+1
            visited_num += 1

    return color


mod = 10**9+7
# n=int(input())
# n,m=list(map(int,input().split()))
# a=list(map(int,input().split()))
def ceil(x, y): return (x+y-1)//y
def input_list(): return list(map(int, input().split()))


def buy(buy_cost, sell_cost, money):
    return money % buy_cost+(money//buy_cost)*sell_cost


n = int(input())
a = input_list()

mon = 1000
i = 0
while i < n:
    for j in range(i+1, n):
        if a[j] > a[i]:
            mon = buy(a[i], a[j], mon)
            #print(i, ":", j, "->", mon)
            i += j
            break
        if a[j] <= a[i]:
            break
    i += 1


print(mon)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
#S = str(input())
#N, K= map(int, input().split())
A = list(map(int, input().split()))

money = 1000
book = 0
for i in range(1, N):
  if A[i] > A[i - 1]:
    book += int(money / A[i - 1])
    money -= book * A[i - 1]
  elif A[i] < A[i - 1]:
    money += book * A[i - 1]
    book = 0
  #print(money, book)  

money += book * A[-1]  
print(money)

Submission status: Wrong Answer

Solution code:
# import sys
import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    a = readInt()
    money = 1000
    stake = 0
    for i in range(n-1):
        if a[i]<a[i+1]:
            stake = money // a[i]
            money -= a[i] * stake
        elif a[i]>a[i+1]:
            money += a[i] * stake
            stake = 0
    money += a[-1] * stake
    print(money)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10
n = int(input())
a = [INF] + list(map(int, input().split())) + [-INF]
l = []
for i in range(n):
    if len(l) % 2 == 0:
        if a[i] > a[i + 1] <= a[i + 2]:
            l.append(a[i + 1])
    else:
        if a[i] < a[i + 1] >= a[i + 2]:
            l.append(a[i + 1])
t = 1000
for i in range(1, len(l), 2):
    t = t // l[i - 1] * l[i] + t % l[i - 1]
print(t)

Submission status: Wrong Answer

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


money = 1000
stock = 0

for i in range(n-1):
    if arr[i+1] > arr[i]:
        stock += money//arr[i]
        money -= arr[i]*stock
    else:
        money += stock*arr[i]
        stock = 0

    # print(money,stock)

money += stock * arr[-1]

print(money)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    M = 1000
    S = 0
    A.append(0)

    for i in range(N):
        if A[i] < A[i+1]:
            S = M // A[i]
            M -= S * A[i]
        elif A[i] > A[i+1]:
            M += S * A[i]
            S = 0
    print(M)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

money

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
MIN=INF
MAX=0
ans=1000
for x in A:
    if x<MIN:
        MIN=x
    elif x>MAX:
        MAX=x
    elif x<MAX and MIN<MAX:
        tmp=ans%MIN
        ans-=tmp*MIN
        ans+=tmp*MAX
        MIN=INF
        MAX=0
if MIN<MAX:
    tmp=ans//MIN
    ans-=tmp*MIN
    ans+=tmp*MAX
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
gold=1000
kabu=0
lst=list(map(int,input().split()))
for i in range(n-1):
    if lst[i]<lst[i+1]:
        kabu,gold=divmod(gold,lst[i])
    elif lst[i]>lst[i+1]:
        gold+=kabu*lst[i]
        kabu=0
gold+=kabu*lst[-1]
print(gold)

Submission status: Wrong Answer

Solution code:
import sys

n, *aaa = map(int, sys.stdin.buffer.read().split())
dp = [-1] * 100001
dp[0] = 1000
for a in aaa:
    ndp = dp.copy()
    for stock in range(101):
        cash = dp[stock]
        if cash == -1:
            break
        for buy in range(1, cash // a + 1):
            ndp[stock + buy] = max(ndp[stock + buy], cash - a * buy)
        for sell in range(1, stock + 1):
            ndp[stock - sell] = max(ndp[stock - sell], cash + a * sell)
    dp = ndp
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      while(yen>=list[t-1]):
        yen-=list[t-1]
        stock+=1
      yen+=list[t]*stock
      stock=0
print(yen)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  list2=sorted(list)
  list.index(list2[0])
  
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      while(yen>=list[t-1]):
        yen-=list[t-1]
        stock+=1
      yen+=list[t]*stock
      stock=0
print(yen)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  list2=sorted(list)
  list.index(list2[0])
  
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      while(yen>=list[t-1]):
        yen-=list[t-1]
        stock+=1
      while(stock>0):
        yen+=list[t]
        stock-=1
print(yen)

Submission status: Time Limit Exceeded

Solution code:
import threading
import sys
import functools


def main():
    N = int(input())
    A = [int(x) for x in input().split(" ")]

    @functools.lru_cache(maxsize=None)
    def solve(stock: int, money: int, day: int, end_day: int) -> int:
        if end_day == day:
            return money

        current_price = A[day]

        money_buy = money - (money // current_price) * current_price
        stock_buy = (money // current_price) + stock

        money_sell = money + stock * current_price
        stock_sell = 0

        return max(
            solve(stock, money, day + 1, end_day),
            solve(stock_buy, money_buy, day + 1, end_day),
            solve(stock_sell, money_sell, day + 1, end_day),
        )

    print(solve(0, 1000, 0, N))


if __name__ == "__main__":

    sys.setrecursionlimit(1024 * 1024 * 2)
    threading.stack_size(128 * 1024 * 1024 * 2)
    threading.Thread(target=main).start()

Submission status: Time Limit Exceeded

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

max = 1000
for i in range(2**(N-1)):
    possess = 1000
    for j in range(N-1):
        if (i >> j) & 1:
            stock = possess // A[j]
            possess = possess % A[j] + A[j+1] * stock
    if possess > max:
        max = possess

print(max)

Submission status: Time Limit Exceeded

Solution code:
# D - Road to Millionaire
def sell(asset, price):
  return price * asset[1] + asset[0]


def buy(money, price):
  stock = money // price
  remainder = money % price
  
  return (remainder, stock)


import copy

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

# タプルのset
assets = [(1000, 0)]


for i in range(N - 1):
  assets_copy = copy.deepcopy(assets)
  money = 0
  
  for a in assets_copy:
    money = max(money, sell(a, A[i]))  
  
    assets.append((money, 0))
    assets.append(buy(money, A[i]))

ans = 0

for a in assets:
  ans = max(ans, sell(a, A[N - 1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
ans = 1000
for ii in range(2 ** n):
    tmp = 1000
    kab = 0
    action = 'buy'
    for i in range(n):
        if (ii >> i) & 1:
            if action == 'buy':
                if tmp < A[i]:
                    break
                kab += tmp // A[i]
                tmp = tmp % A[i]
                action = 'sell'

            elif action == 'sell':
                if kab == 0:
                    break
                tmp += kab * A[i]
                kab = 0
                action = 'buy'
    else:
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
ans = 1000
for ii in range(2 ** n):
    for jj in range(2 ** n):
        tmp = 1000
        kab = 0
        for i in range(n):
            if (ii >> i) & 1:  # buy
                if tmp < A[i]:
                    break
                kab += tmp // A[i]
                tmp = tmp % A[i]

            if (jj >> i) & 1:  # sell
                if kab == 0:
                    break
                tmp += kab * A[i]
                kab = 0
        else:
            ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

ans = 0
for i in range(2**n):
  mo = 1000
  st = 0
  for j in range(n):
    if ((i>>j) & 1):
      s = mo//a[j]
      st += s
      mo -=a[j]*s
    else:
      mo+=st*a[j]
      st = 0
  ans = max(ans, mo)
print(ans)