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())
A = list(map(int, input().split()))

def ask_judge(asset_now, position):
    if ask[i]:
        position += asset_now // A[i]
        asset_now -= position * A[i]    
    return asset_now, position

def bid_judge(asset_now, position):
    if bid[i]:
        asset_now += position * A[i]    
        position = 0
    return asset_now, position


asset_now = 1000

ask = [True if A[i+1] - A[i] > 0 else False for i in range(N-1)]
bid = [True if A[i+1] - A[i] <= 0 else False for i in range(N-1)]
position = 0

for i in range(N):
    if i == 0:
        asset_now, position = ask_judge(asset_now, position)
    elif i == N-1:
        if position > 0:
            asset_now += position * A[N-1]
    else:
        asset_now, position = ask_judge(asset_now, position)
        asset_now, position = bid_judge(asset_now, position)

print(asset_now)

Submission status: Wrong Answer

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

ans = 1000
maxv = a[0]
minv = a[0]
for i in range(n):
    if i < n - 1:
        if a[i] < maxv:
            ans += (maxv - minv) * (ans // minv)
            maxv = a[i]
            minv = a[i]
        else:
            maxv = max(maxv, a[i])
            minv = min(minv, a[i])
    else:
        if a[i] > minv:
            ans += (a[i] - minv) * (ans // minv)

print(ans)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def tsune(pal,R,pre):
    c = 0
    ud = [0 for i in range(n)]
    for i in range(n):
        r = R[i]
        if pal*r > pal*pre:
            pal*=-1
            ud[i] = pal
        pre =r
    return  ud

def tot(ud):
    tmp = 1000
    kab = 0
    for i in range(n):
        if ud[i] ==1: #buy kab
            kab,tmp = divmod(tmp,A[i])
        elif ud[i] ==-1:
            tmp +=kab*A[i]
            kab = 0
    return tmp
n = ni()
A = list(ma())
ans = 0
ud = tsune(-1,A,1000)
tmp = tot(ud)
ans = max(ans,tmp)
ud = tsune(-1,A,0)
tmp = tot(ud)
ans = max(ans,tmp)
ud = tsune(1,A,1000)
tmp = tot(ud)
ans = max(ans,tmp)
ud = tsune(1,A,0)
tmp = tot(ud)
ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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 - s * a[i]
    else:
        m += s * a[i]
        s = 0
m += s * a[n - 1]
print(m)

Submission status: Wrong Answer

Solution code:
import math
a = input()
b = input().split(" ")
c = []
for i in b:
  c.append(i)
money = 1000
senet = 0
chk = 0
c.sort(reverse=True)
for i in range(int(a)):
  for j in range(int(a)):
    if j != int(a)-1:
      if b[j] >= b[j+1]:
        pass;
      else:
        chk = 1 
  if chk == 0:
    break;
  elif i == int(a)-1:
    if senet != 0:
      money = money + (senet * int(b[i]))
    else:
      pass;
  elif i == 0:
    senet += math.floor(money / int(b[i]))
    money = money-(math.floor(money / int(b[i]))*int(b[i]))
  elif int(b[i]) < int(b[i+1]):
    senet += math.floor(money / int(b[i]))
    money = money-(math.floor(money / int(b[i]))*int(b[i]))
  elif int(b[i]) > int(b[i+1]):
    money += senet * int(b[i])
    senet = 0 
  elif int(b[i]) == int(b[i+1]):
    pass;
print(money)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy import signal


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

    dA = list()
    for i in range(N-1):
        dA.append(A[i+1]-A[i])

    idn = list()
    upflag = False
    downflag = False
    if dA[0] > 0:
        upflag = True
        tmp = 0
    elif dA[0] < 0:
        downflag = True
    for i, a in enumerate(dA[1:], 1):
        if downflag and a > 0:
            tmp = i
            upflag = True
            downflag = False
        elif upflag and a < 0:
            idn.append((tmp, i))
            upflag = False
            downflag = True
    if upflag:
        idn.append((tmp, N-1))

    ans = 1000
    for n in idn:
        ans = (ans//A[n[0]]) * A[n[1]] + (ans % A[n[0]])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

money = 1000
stock = 0
leave_max = max(a[1:])

for i in range(n):
    if i == n-1:
        money += a[i] * stock
        break

    leave_max = max(a[i+1:])

    if a[i] >= a[i+1]:
        money += a[i] * stock
        stock = 0
        if a[i] > leave_max:
            break
        else:
            continue

    elif a[i] < a[i+1]:
        stock = money // a[i]
        money -= stock * a[i]

print(money)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
mon = 1000
kab = 0

for i in range(1,n+1):
    if i == n:
        if kab != 0:
            mon += kab * a[n-1]
            kab = 0
    else:
        if a[i-1] < a[i]:
            kab = int(mon/a[i-1])
            mon = mon%a[i-1]
        else:
            mon += kab * a[i-1]
            kab = 0
print(mon)

Submission status: Wrong Answer

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
    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
            continue
    i += 1

if i == N-2:
    if A[i] < A[N-1]:
        num = money // A[i]
        money -= A[i] * num
        money += A[N-1] * num
print(money)

Submission status: Wrong Answer

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

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

for i in range(1, n):
    for g in range(500):
        for l in range(500):
            if dp[l][i-1] >= 0:
                if l < g:
                    dp[g][i] = max(dp[l][i-1] - a[i]*(g-l), dp[g][i])
                else:
                    dp[g][i] = max(dp[l][i-1] + a[i]*(l-g), dp[g][i])
            else:
                break

ans = 0
for m in range(500):
    ans = max(ans, dp[m][n-1])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
temp = [int(i) for i in input().split()]
A = list(dict.fromkeys(temp)) + [0]

ls = []
bottom = A[0]
for i in range(1, len(A)-1):
    if A[i-1] < A[i] and A[i] > A[i+1]:
        ls += [bottom, A[i]]
    if A[i-1] > A[i] and A[i] < A[i+1]:
        bottom = A[i]

stucks = 0
money = 1000
for i in range(len(ls)):
    if i % 2 == 0:
        stucks = money // ls[i]
        money -= stucks * ls[i]
    else:
        money += stucks * ls[i]
        stucks = 0

print(money)

Submission status: Wrong Answer

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

kabu=0
ans=1000

for i in range(N-1):
    if A[i] > A[i+1]:
        ans=ans+kabu*A[i]
        kabu=0

    if A[i] < A[i+1]:
        kabu=ans // A[i]
        ans=ans % A[i]

ans=ans+kabu*A[N-1]

print(ans)

Submission status: Wrong Answer

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

money = 1000
stack = 0
up = []
last_high = 0
high = 0
low = a[0]

for i in range(n):
    if i == 0:
        up.append(-1)
    elif a[i] > a[i - 1]:
        if i == n - 1:
            up.append(1)
        elif a[i] <= a[i + 1]:
            up.append(0)
        else:
            up.append(1)
    elif a[i] < a[i - 1]:
        up.append(-1)
    else:
        up.append(0)
print(up)

for i in range(n):
    if up[i] == 1:
        high = a[i]
        for j in range(last_high, i):
            if up[j] == -1:
                low = a[j]
        stack = money // low
        money %= low
        money += stack * high

print(money)

Submission status: Wrong Answer

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

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

print(money)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline().rstrip("\n"))
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
m = 1000
bm = a[0]
for i in range(1,n):
    if bm > a[i]:
        bm = a[i]
    elif bm < a[i]:
        sm = a[i]
        kb,m = divmod(m, bm)
        m = m + sm * kb
        if i+1< n:
            bm = a[i+1]
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
cash = 1000
kabu = 0
up=False
down=False
sell = []*n
buy = []*n
first=True
for i,j in zip(a[:-1], a[1:]):
  if first:
    first=False
    if i < j:
      up = True
      buy.append(i)
      continue
    elif i > j:
      down=True
  if i < j:
    if down:
      buy.append(i)
    up = True
  elif i > j:
    if up:
      # sell
      sell.append(i)
    down=True
else:
  if up:
    sell.append(a[-1])

for i,j in zip(buy,sell):
  kabu = cash // i
  cash -= kabu * i
  cash += j*kabu
print(cash)

Submission status: Wrong Answer

Solution code:
n= int(input())
a = list(map(int,input().split()))
o = {}
for i in a:
    if not i in o:
        o[i] = 0
a = []
for i in o:
    a.append(i)
money = 1000
buy = 0
have = 0
for i in a:
    if i == max(a):
        money += have * i
        break
    if have == 0:
        have = money // i
        money -= i*have
        buy = i
    elif buy < i:
        money += i*have
        have = 0
print(money)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    stocks = 0
    money = 1000
    i = 0
    while i < N:
        buy = i
        sell = i
        while sell < N-1 and A[sell] <= A[sell+1]:
            print("{} <= {}".format(A[sell], A[sell+1]))
            print("B {}th day, stocks={}, money={}".format(sell, stocks, money))
            sell += 1
        if buy == sell:
            print(money)
            return
        
        stocks = money//A[buy]
        money = money - stocks*A[buy]
        money += stocks*A[sell]
        stocks = 0
        i = sell+1
    print(money)
    

if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

money = 1000
stock = 0
leave_max = max(a)

for i in range(n):
    if i == n-1:
        money += a[i] * stock
        break

    leave_max = max(a[i+1:])

    if a[i] >= a[i+1]:
        money += a[i] * stock
        stock = 0
        if a[i] > leave_max:
            break
        else:
            continue

    elif a[i] < a[i+1]:
        stock = money // a[i]
        money -= stock * a[i]

print(money)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    kai = A[0]
    uri = A[0]
    flag=0
    temoti = 1000
    for i in range(1,N-1):
        if kai < A[i] and uri<A[i]:
            uri=A[i]
            flag=1
        if flag==1:
            if uri>A[i]:
                temoti = temoti + temoti // kai *(uri-kai)
                kai = A[i]
                uri = A[i]
                flag=0
    
    if uri< A[N-1]:
        uri = A[N-1]
    if kai<uri:
        temoti = temoti + temoti // kai * (uri-kai)

    print(temoti)

Submission status: Wrong Answer

Solution code:
n = int(input(''))
alist = list(map(int,input('').split()))
money=1000
stock=0

for d in range(n-1):
    if alist[d+1] > alist[d]:
        # 買い
        stock+=int(money/alist[d])
        money-=stock*alist[d]
#        print("[buy] {}*{} [{}]".format(stock,alist[d],money))
    else:
        # 売り
        money+=stock*alist[d]
        stock=0
#        print("[sell] {}*{} [{}]".format(stock,alist[d],money))

money+=stock*alist[n-1]
stock=0
#print("[sell] {}*{} [{}]".format(stock,alist[d],money))
print(money)

Submission status: Wrong Answer

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

kane = 1000
kabu = 0

for i in range(n):
  if i == (n-1):
    if A[i] > A[i-1]:
      kane = kane + kabu * A[i]
      kabu = 0
    else:
      pass
  elif A[i] < A[i+1]:
    kabu = kane // A[i]
    kane = kane - (kabu * A[i])
  elif A[i] >= A[i+1]:
    kane = kane + kabu * A[i]
    kabu = 0
  else:
    pass
  
print(kane)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))

n = get_int()
ls = get_list()
peak_pts = []
inc = True
if ls[1]>ls[0]:
    peak_pts.append(0)
i = 1
while i<n:
    if ls[i]>=ls[i-1]:
        if not inc:
            peak_pts.append(i - 1)
            inc = not inc
    else:
        if inc:
            peak_pts.append(i-1)
            inc = not inc
    i += 1
if ls[-1]>=ls[-2]:
    peak_pts.append(n-1)

profit = 1000
le = len(peak_pts)
ava_bought,ava_sell = 1000,0
for ind in range(0,le,2):
    i = peak_pts[ind]
    if ind+1<le:
        midprofit = 0

        # Buy
        j = i
        totalshares = 0
        while j<peak_pts[ind+1]:
            shares = (ava_bought//ls[j])
            ava_bought -= shares*ls[j]
            midprofit -= shares*ls[j]
            ava_sell += shares*ls[j]
            totalshares += shares
            if ava_bought==0: break
            if j+1<n and ls[j+1]>ls[j]: break
            j += 1

        #Sell
        j = peak_pts[ind+1]
        midprofit += ls[j]*totalshares
        if midprofit>0:
            profit += midprofit
        ava_bought = profit
        #print(ava_bought, ava_sell, midprofit,totalshares)
print(profit)

Submission status: Wrong Answer

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

money = 1000
num = 0
flag = False
a.append(a[n - 1])
for i in range(n):
    #print(num, money)
    if flag:
        flag = False
        continue
    if a[i] < a[i + 1]:
        num += money // a[i]
        money -= a[i] * num
    else:
        money += num * a[i + 1]
        num = 0
        flag = True
print(money)

Submission status: Wrong Answer

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

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

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

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


for i in range(n-1) : 
    if A[i]<A[i+1] and money>=A[i] : #株を買う
        kabu+=money//A[i]
        money-=A[i]*(money//A[i])
    elif A[i]>A[i+1] and kabu>0 :    #株を売る
        money+=kabu*A[i]
        kabu=0
else :
    money+=kabu*A[n-1]
    print(money)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split())) 
m = 1000
tmp = 999

for i in range(n):
    if tmp > a[i]:
        kb = int(m / a[i])
        d = m - kb * a[i]
        tmp = a[i]
    elif tmp < a[i] and kb != 0:
        m = kb * a[i] + d
        tmp = a[i]
        kb = 0

print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
lis = [0]*n
sw = 0
for i in range(n):
    if sw == 0 and i >= 1 and a[0] > a[i]:
        sw = 1
    if i == n-1:
        break
    if a[i] > a[i+1]:
        lis[i] = -1
b = a[::-1]
for i in range(n-1):
    if b[i] < b[i+1]:
        if lis[n-i-1] == -1:
            pass
        else:
            lis[n-i-1] = 1
lis[-1] = -1
if sw == 0:
    lis[0] = 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())
A=list(map(int,input().split()))
money=1000
k=0
row=0
high=0

for i in range(N-1):
  if A[i]<A[i+1]:
    row=min(A[k:i+1])
    k=i+1
  if A[i]>A[i+1]:
    high=max(A[k:i+1])
    k=i+1
    if row==0:
      continue
    div,mod=divmod(money,row)
    money=div*high+mod
  if i==N-2:
    high=max(A[k:])
    if row==0:
      continue
    div,mod=divmod(money,row)
    money=div*high+mod
print(money)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

delta_a = [0] * (n-1)
for i in range(n-1):
  delta_a[i] = a[i+1] - a[i]

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

# どこで反転するかを記録する
pre = [0] * N
pre_index = 0
old_a = A[0]
if A[0] > A[1]:
    old_coef = -1
elif A[0] < A[1]:
    old_coef = 1
else:
    old_coef = 0

for i in range(1, N):
    if A[i] > old_a:
        coef = 1
    elif A[i] < old_a:
        coef = -1
    else:
        coef = 0
    if coef != 0 and coef != old_coef:
        for j in range(pre_index, i):
            pre[j] = i - 1
        pre_index = i
        old_coef = coef
    old_a = A[i]
for j in range(pre_index, N):
    pre[j] = N - 1
# print(pre)

shojikin = 1000
stock = 0
if A[0] < A[pre[0]]:
    q, mod = divmod(shojikin, A[0])
    stock += q
    shojikin = mod
elif pre[0] == N - 1:
    # 何もしないほうが良い場合
    print('1000')
    quit()

# print("1st shojikin: {} stock: {}".format(shojikin, stock))

pre = list(set(pre))
pre.sort()
# print("sorted: {}".format(pre))
for deal_index in pre:
    if stock:
        shojikin += stock * A[deal_index]
        stock = 0
        # print("uri deal: {} shojikin: {} stock: {}".format(deal_index, shojikin, stock))
    else:
        q, mod = divmod(shojikin, A[deal_index])
        stock += q
        shojikin = mod
        # print("kai deal: {} shojikin: {} stock: {}".format(deal_index, shojikin, stock))
print(shojikin)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int,input().split()))
saifu = 1000
kaine = None
urine = None
for i in range(n):
  if kaine == None:
    kaine = a[i]
    continue
  if urine == None:
    if i < n - 1 and kaine < a[i]:
      urine = a[i]
      continue
  if i < n - 1 and urine != None and urine <= a[i]:
    urine = a[i]
    continue
  if i == n - 1 and kaine < a[i]:
    urine = a[i]
  if kaine != None and urine != None:
    kabu = int(saifu / kaine)
    saifu += kabu * (urine - kaine)
    kaine = a[i]
    urine = None
print(saifu)

Submission status: Wrong Answer

Solution code:
MAX = 5000

n = int(input())
a = list(map(int, input().split()))
dp = [[-1 for j in range(MAX + 1)] for i in range(n)]
dp[0][0] = 1000
for k in range(1, MAX + 1):
    if 1000 - a[0] * k < 0:
        break
    dp[0][k] = 1000 - a[0] * k
# print(dp[0])
for i in range(1, n):
    for j in range(MAX + 1):
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        # 買うとき
        for k in range(1, MAX + 1):
            if j - k < 0:
                break
            if dp[i - 1][j - k] - a[i] * k < 0:
                break
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k] - a[i] * k)
        # 売る時
        for k in range(1, MAX + 1):
            if j + k >= MAX + 1:
                break
            if dp[i - 1][j + k] < 0:
                break
            dp[i][j] = max(dp[i][j], dp[i - 1][j + k] + a[i] * k)
    # print(dp[i])
# print(dp)
ans = max(dp[-1])
print(max(ans, 0))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
money = 1000
kabu = 0
A0 = A[0]
if min(A) == A0:
    kazu = int(money/A0)
    kabu += kazu
    money -= kazu * A0
    #print(money,kabu)

for i in range(1,N-1):
    #print(A[i])
    Ai = A[i]
    if A[i-1] < Ai:
        money += kabu*A[i]
        kabu = 0
        #print(money,kabu)
    if min(A[i:]) == A[i]:
        Ai = A[i]
        kazu = int(money/Ai)
        kabu += kazu
        money -= kazu * Ai
        #print(money,kabu)
AN = A[N-1]
if A[N-2] < AN:
    money += kabu*AN
    kabu = 0
    #print(money,kabu)

print(money)

Submission status: Wrong Answer

Solution code:
n, *a = map(int, open(0).read().split())
max_a = max(a)
money = 1000
stock = 0
if a[0] != max_a:
    stock += money // a[0]
    money = money % a[0]
    for i in range(1, n):
        if a[i] < a[i-1] and max(a[i:]) != a[i]:  # buy
            stock += money // a[i]
            money = money % a[i]
            # print('buy')
        elif a[i] > a[i-1] and (min(a[i:]) != a[i] or i == n-1):  # sell
            money += stock * a[i]
            stock = 0
            # print('sell')
        # print(i, money, stock)
print(money)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = list(map(int,input().split()))
reverseA = sorted(A,reverse = True)
money = 1000
stock = 0

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

Submission status: Wrong Answer

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

money=1000
sa=[]#差
stock=0

for num in range(len(a)-1):
  if a[num]<a[num+1]:
    sa.append("up")
  elif a[num]==a[num+1]:
    sa.append("same")
  elif a[num]>a[num+1]:
    sa.append("down")

what_to_do=[]#後ろから行動を決める

for num in range(len(sa)):
  if sa[num]=="up":
    try:
      if sa[num+1]!="up":
        what_to_do.append("sell")
      else:
        what_to_do.append("do nothing")

    except IndexError:
      what_to_do.append("sell")

  if sa[num]=="same":
    what_to_do.append("do nothing")

  if sa[num]=="down":
    try:
      if sa[num+1]!="down":
        what_to_do.append("buy")
      else:
        what_to_do.append("do nothing")

    except IndexError:
      what_to_do.append("do nothing")


first=[]
for command in what_to_do:
  if command=="buy":
    first.append("do nothing")
    break
  elif command=="sell":
    first.append("buy")
    break    
what_to_do=first+what_to_do    

cnt=0
for command in what_to_do:
  if command=="buy":
    stock=money//a[cnt]
    money=money%a[cnt]
    cnt+=1
  elif command=="sell":
    money+=stock*a[cnt]
    stock=0
    cnt+=1
  elif command=="do nothing":
    cnt+=1

print(money)

Submission status: Wrong Answer

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

if max(arr)==arr[0]:
    print(1000)
else:
    amari = 1000
    can_buy = int((amari-amari%arr[0])/arr[0])
    poss = can_buy
    amari -= can_buy*arr[0]

    for i in range(1,n-1):
        if arr[i+1] == arr[i]:
            continue
        elif arr[i+1] > arr[i]:
            can_buy = int((amari-amari%arr[i])/arr[i])
            poss+=can_buy
            amari -= can_buy*arr[i]
        else:
            amari += poss*arr[i]
            poss=0
    print(amari+poss*arr[n-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
A= list(map(int,input().split()))
kabu=0
kane=1000
kabukin=0
for a in range(N-1):
    if A[a]*int(kane/A[a])>A[a+1]*int(kane/A[a+1]):
        #if kabukin<A[a]*kabu:
            kabu=int(kane/A[a])
            kabukin=kabu*A[a]
            kane=kane-kabu*A[a]
    elif A[a]>A[a+1] and kabu>=1:
        kane=kane+kabu*A[a]
        kabu=0
    
if kabu>0:
    kane+=kabu*A[-1]
print(kane)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import itertools
import array
import textwrap
import math

N = int(input())
A = list(map(int, input().split()))
a = sorted(A, reverse=True)
if a == A:
    print('1000')
    sys.exit()
temp = A[0]
m = 1000
min = A[0]
temp0 = 0
max = 0
f = 0
for i in range(N):
    if i < temp0:
        continue
    for k in range(i, N):
        if temp > A[k]:
            min = A[k]
            # print(min)
        if temp < A[k]:

            m = A[k]*(m//min)+(m-(m//min)*min)
            if max < m:
                max = m
                f = 1
            min = A[k]
            temp = A[k]
            # print(m)
            if f == 1:
                temp0 = k
                f = 0
    m = max
    min = A[temp0]
    temp = A[temp0]
    # print(i)
print(m)

Submission status: Wrong Answer

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

dp=[[] for i in range(n)]
for i in range(0,1000//a[0]+ 1):
    dp[0].append(1000- i* a[0])

for i in range(1,n):
    for j in range(dp[i-1][0]//a[i] +1):
        dp[i].append(0)
    for j in range(len(dp[i-1])):
        for k in range(len(dp[i])):
            if dp[i-1][j]+ (j-k)*a[i]<0:
                break
            dp[i][k]=max(dp[i-1][j]+ (j-k)*a[i],dp[i][k])


print(dp[n-1][0])

Submission status: Wrong Answer

Solution code:
import  heapq
n=int(input())
aa=list(map(int,input().split()))
count=1
have=1000
l=[aa[0]]
ll=[-aa[0]]
heapq.heapify(l)
heapq.heapify(ll)
while count<n:
  mx=-heapq.heappop(ll)
  mn=heapq.heappop(l)
  if mx<=aa[count]:
    heapq.heappush(ll,-aa[count])
    heapq.heappush(l,aa[count])
    heapq.heappush(ll,-mn)
    heapq.heappush(l,mn)
    heapq.heappush(ll,-mx)
    heapq.heappush(l,mx)
    #print(l,ll)
  else:
    have+=(mx-mn)*int(have/mn)
    count+=1
    #print(mx,mn,l,ll)
    if count<=n-1:
      l=[aa[count]]
      ll=[-aa[count]]
      heapq.heapify(l)
      heapq.heapify(ll)
      heapq.heappush(ll,-aa[count])
      heapq.heappush(l,aa[count])
  count+=1
if len(l)!=0:
  mx=-heapq.heappop(ll)
  mn=heapq.heappop(l)
  have+=(mx-mn)*int(have/mn)
  
  
print(have)

Submission status: Wrong Answer

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

dp = [-1]*1000
dp[0] = 1000


for i in range(n):
    ndp = [-1]*1000

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

Submission status: Wrong Answer

Solution code:
import math
from itertools import groupby
N = int(input())
A = list(map(int, (input().split())))
cash = 1000
stock = 0
A = [i[0] for i in groupby(A)]
if (A[0] == max(A)):
    print(cash)
else:
    for i in range(len(A)-1):
        if (A[i] > A[i+1]):
            cash = cash + stock*A[i]
            stock = 0
        else:
            stock = stock + math.floor(cash/A[i])
            cash = cash - stock*A[i]
    cash = cash + stock*A[i+1]
    print(cash)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
money = 1000
peak = []
botom = []
kabu = 0

if a[0] < a[1]:
    botom.append(0)
if a[n-1] >= a[n-2]:
    peak.append(n-1)
for i in range(1, n-1):
    if a[i] >= a[i-1] and a[i] > a[i+1]:
        peak.append(i)
    elif a[i] <= a[i-1] and a[i] < a[i+1]:
        botom.append(i)

for i in range(n):
    if i in botom:
        kabu = money//a[i]
        money %= a[i]
    elif i in peak:
        money += kabu*a[i]
        kabu = 0

print(money)