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:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
B = [0]*N # 1: top, -1: bottom

inc = 0 # 1: increasing, -1: decreasing
val = A[0]
bot = 0
for i, a in enu(A):
    if i == N-1:
        B[i] = 1
    if inc == 0:
        if val < a:
            inc = 1
            B[i-1] = -1
        elif val == a:
            continue
        else:
            inc = -1
            B[i-1] = 1
    elif inc == 1:
        if val < a:
            continue
        elif val == a:
            continue
        else:
            B[i-1] = 1
            inc = -1
    else:
        if val < a:
            inc = 1
            B[i-1] = -1
        elif val == a:
            continue
        else:
            continue
    val = a

# print(B)
money = 1000
stock = 0
for i, a in enu(A):
    if B[i] == -1:
        # print('buy')
        stock += money//A[i]
        money %= A[i]
    elif B[i] == 1:
        # print('sell')
        money += stock*A[i]
        stock = 0 

print(money)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    inlis = list(map(int, input().split()))
    
    kabu = 0
    tmp = inlis[0]
    shoji = 1000

    for i in range(0, n-1):
        if inlis[i] > tmp:
            shoji += inlis[i] * kabu
            tmp = inlis[i]
            kabu = 0
            #print(kabu, shoji)
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                #print(kabu, shoji)
        elif inlis[i] <= tmp:
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                #print(kabu, shoji)
    if inlis[n-1] > inlis[n-2]:
        shoji += inlis[n-1] * kabu
        kabu = 0
    print(shoji)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dp = [[0]*(200) for i in range(N)]#所持金jの時のi日目の最大株
kabu0 = 1000#株をひとつも持ってない状態での所持金最大

dp[0][1000%A[0]] = 1000//A[0]

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

print(kabu0)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
A = list(map(int,input().split()))
sell = [0]*N
buy = [0]*N
hand = [[1000,0] for i in range(N+1)]
for i in range(1,N-1):
    if A[i] >= A[i-1] and A[i] > A[i+1]:
        sell[i] = 1
    if A[i] <= A[i-1] and A[i] < A[i+1]:
        buy[i] = 1
if A[0] < A[1]:
    buy[0] = 1
if A[N-1] > A[N-2]:
    sell[N-1] = 1
for i in range(N):
    if buy[i] == 1:
        hand[i+1][0] = hand[i][0] % A[i]
        hand[i+1][1] += hand[i][1] + (hand[i][0] // A[i])
    elif sell[i] == 1:
        hand[i+1][0] = hand[i][0] + A[i]*hand[i][1]
        hand[i+1][1] = 0
    else:
        hand[i+1][0] = hand[i][0]
        hand[i+1][1] = hand[i][1]
print(hand[N][0])
    
print(hand)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
sign = 1
mountain, valley = [], []
if A[0] < A[1]:
  valley.append(0)
for i in range(N-1):
  if A[i] > A[i+1]:
    if sign == 1:
      mountain.append(i)
      sign = -1
  elif A[i] < A[i+1]:
    if sign == -1:
      valley.append(i)
      sign = 1
if A[-1] > A[-2]:
  mountain.append(N-1)
M = 1000
kb = 0
lm, lv = len(mountain), len(valley)
for i in range(lv):
  flg = True
  cnt = i
  while flg:
    if cnt == lm:
      flg = False
      break
    elif cnt < lm:
      if mountain[cnt] < valley[i]:
        cnt += 1
      else:
        break
  if flg:
    kb += (M // A[valley[i]])
    M -= (M // A[valley[i]]) * A[valley[i]]
    M += kb * A[mountain[cnt]]
    kb = 0
print(M)

Submission status: Wrong Answer

Solution code:
def main():
    import copy
    n = int(input())
    a = list(map(int,input().split()))
    ans = 1000
    for i in range(n-1):
        ls = [0 for i in range(n)]
        ls[i] = 1
        l = i
        m = 1000
        for j in range(i+1,n):
            if a[l]<a[j]:
                if ls[l]==1:
                    ls[j] = -1
                    l = j
            elif a[l]>a[j]:
                if ls[l]==-1:
                    ls[j] = 1
                    l = j
        for k in range(n):
            if ls[k]==1:
                cnt = m//a[k]
                m = m-cnt*a[k]
            elif ls[k]==-1:
                m += cnt*a[k]
                cnt = 0
        if cnt!=0:
            m+=cnt*a[-1]
        if m>ans:
            ans = m
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

genkin = 1000
kabu = 0

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

print(genkin + kabu * A[N-1])

Submission status: Wrong Answer

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

for i,price in enumerate(A):
    if price > prev:
        stock += money // prev
        money -= stock * prev

    elif price < prev and stock:
        money += prev * stock
        stock = 0
    prev = price

print(money)

Submission status: Wrong Answer

Solution code:

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

MAX = 10 ** 5
dp = [[-1] * MAX for _ in range(N + 1)]
dp[0][0] = 1000
for i in range(N):
    dp[i + 1][0] = dp[i][0]

    for j in range(MAX - 1):
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j],
                           dp[i + 1][j - 1] - X[i], dp[i][j - 1] - X[i])

    for j in reversed(range(MAX - 1)):
        if dp[i + 1][j + 1] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][j + 1] + X[i])
        if dp[i][j + 1] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j + 1] + X[i])

print(max(dp[-1]))

Submission status: Wrong Answer

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

money = 1000
stock = 0
left_money = money

# 買って個数または残金が多くなるか売って残金が多くなるか
for a in As:
    if money < left_money + a * stock:
        money = left_money + a * stock
        left_money = money
        stock = 0
    elif stock < money // a:
        if stock == money // a:
            if left_money < money - stock * a:
                left_money = money - stock * a
        else:
            stock = money // a
            left_money = money - stock * a

print(money)

Submission status: Wrong Answer

Solution code:
N = int(input())
line  =list(map(int, input().split()))
money = 1000
k = line[0]
ln = [line[0]]
for i in range(1,N):
    if line[i] != ln[-1]:
        ln.append(line[i])
#print(ln)
while len(ln) > 1:
    if ln[0] >  ln[1]:
        ln = ln[1:]
    else:
        break
#print(ln)
while len(ln) > 1:
    if ln[-1] < ln[-2]:
        ln = ln[:-2]
    else:
        break
#print(ln)
for i in range(int(len(ln)/2)):
    money = ln[2*i +1] * int(money / ln[2*i]) + (money %ln[2*i])
    #print(money)
print(money)

Submission status: Wrong Answer

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

sa = set(a)
sizea = len(sa)
ssa = sorted(list(sa))


for i in range(n):
    imj = False
    ilj = False
    for j in range(i+1,n):
        if a[i] < a[j]:
            imj = True
        elif a[i] > a[j]:
            ilj = True
        if imj and ilj:
            break
    
    if mny >= a[i] and imj:
        stc += mny//a[i]
        mny = mny - (a[i] * (mny//a[i]))
    elif ilj:
        mny += stc * a[i]
        stc -= stc


mny += stc * a[len(a)-1]

print(mny)

Submission status: Wrong Answer

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

    flg = 0
    MIN = []
    MAX = []
    i = 0
    while i <n-1:
        mi = A[i]
        ma = A[i]
        if flg == 0:
            for j in range(i+1,n):
                mi = min(mi,A[j])
                if A[i] < A[j]:
                    flg = 1
                    MIN.append(mi)
                    i = j
                    if j == n-1:
                        MAX.append(A[j])
                    break
                elif j == n-1:
                    i = j
                    break

        if flg == 1:
            for j in range(i+1,n):
                ma = max(A[i],ma)
                if A[i] > A[j]:
                    flg = 0
                    MAX.append(ma)
                    i = j
                    break
                elif j == n-1:
                    MAX.append(ma)
                    i = j
                    break
    s = 1000
    for i,j in zip(MIN,MAX):
        t = s//i
        s -= t*i
        s += t*j

    print(s)
main()

Submission status: Wrong Answer

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

stock=0
money=1000
#極小は-1、極大は1、何もしないは0
graph=[0]*n
if a[0]<a[1]:
    graph[0]=-1
    increase=1
elif a[0]==a[1]:
    increase=0
else:
    increase=-1

for i in range(1,n-1):
    #株価上昇中
    if increase==1:
        if a[i]>a[i+1]:
            graph[i]=1
            increase=-1
    #株価下落中
    if increase==-1:
        if a[i]<a[i+1]:
            graph[i]=-1
            increase=1
    if increase==0:
        if a[i]<a[i+1]:
            graph[i]=-1
            increase=1
        if a[i]>a[i+1]:
            graph[i]=1
            increase=-1

if a[n-2]<a[n-1]:
    graph[n-1]=1

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

print(money)

Submission status: Wrong Answer

Solution code:
""" D
    https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_d
"""
import sys
import math
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return [lambda _: readIntegerSet(m) for _ in range(0, n)]

def div_by(n, x, k):
    result = 0
    for i in n:
        if x[i] == "1":
            result = (result + pow(2, n-i-1)) % k
    return result

def popcount(x):
    return sum([int(c) for c in x])

def main(N, A):
    kabu = 0
    money = 1000
    for i in range(1, N):
        if A[i-1] < A[i]:
            kabu = money // A[i-1]
            money %= A[i-1]
        else:
            money += A[i-1] * kabu
            kabu = 0

    money += A[N-1] * kabu

    return money

if __name__ == "__main__":
    _N = readInteger()
    _A = readIntegerSet(_N)

    print(main(_N, _A))

Submission status: Wrong Answer

Solution code:
n=int(input())
ar=list(map(int,input().split()))
c=1000
p=0
cur=0
prev=0
for i in range(n):
    if i!=n-1 and ar[i+1]>ar[i]:
        prev=ar[i]
        cur=c//ar[i]
        c=c%ar[i]
##        print(i,'b')
    if i!=0 and ar[i]>ar[i-1]:
        p+=ar[i]*cur-prev*cur
        c+=cur*ar[i]
        cur=0
##        print(i,'s')
##    print(ar[i])
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
cash = 1000
kabu = 0
for i,j in zip(a[:-1], a[1:]):
  if i < j:
    kabu = cash // i
    cash = cash - i * kabu
  else:
    cash += kabu * i
    kabu = 0
  
print(cash + kabu * a[-1])

Submission status: Wrong Answer

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

dp = [[-1]*100000 for i in range(n+1)]
dp[0][0] = 1000


for i in range(n):
    for j in range(99999):
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i+1][j] >= a[i]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j]-a[i])
        
    for j in range(99999,0,-1):
        if dp[i+1][j] >= 0:
             dp[i+1][j-1] = max(dp[i+1][j-1],dp[i+1][j]+a[i])
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    c = 1000
    s = 0

    for i in range(0, n-1):
        j = i + 1  # 比較対象(翌日)
        diff = A[j] - A[i]
        # 次にup 今持っている現金を全て株にする
        if diff > 0:
            s = c // A[i]
            c = c % A[i]
        # 次にdown 今持っている株を全て現金にする
        if diff < 0:
            c += s * A[i]
            s = 0
        #print(i, s, c)

    # 最後に株を全て現金に戻す
    c += s * A[n-1]

    print(c)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

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

mon = 1000
stock = 0

lim_a = [a_list[0]]
for i in range(1,N-1):
    if lim_a[-1] == a_list[i]:
        continue
    if a_list[i] <= a_list[i+1] and a_list[i] <= a_list[i-1]:
        lim_a.append(a_list[i])
    elif a_list[i] >= a_list[i+1] and a_list[i] >= a_list[i-1]:
        lim_a.append(a_list[i])
lim_a.append(a_list[-1])

s = 0 if lim_a[0] < lim_a[1] else 1
e = 1 if lim_a[-1] < lim_a[-2] else 0
for i in range(s, len(lim_a)-e):
    if (i + s)%2 == 0:
        # buy
        stock += mon//lim_a[i]
        mon -= lim_a[i] * stock
    else:
        # sell
        mon += lim_a[i] * stock
        stock = 0
print(max(mon, 1000))

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    m = 1000
    s = 0

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

    m += a[n-1] * s

    print(m)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
list_A = list(map(int, input().split()))
money = 1000
stock = 0

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

money += stock * list_A[-1]
print(money)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N = int(input())
A = [300] + list(map(int, input().split()))

flg = [0] * (N+1)
buy_cnt = 0

for i in range(1, N+1):
    if i == N:
        if A[i] < A[i - 1]:
            flg[i] = 1
        if A[i-1] < A[i]:
            flg[i] = -1
    else:
        if A[i] <= A[i-1] and A[i+1] > A[i]:
            flg[i] = 1
            buy_cnt += 1
        if A[i-1] <= A[i] and A[i+1] < A[i]:
            flg[i] = -1

if buy_cnt == 0:
    print(1000)
    sys.exit()

ans = 1000
stock = 0
for i in range(1, N+1):
    if flg[i] == 1:
        stock = ans//A[i]
        ans = ans % A[i]
    elif flg[i] == -1:
        ans += stock * A[i]
        stock = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()
    # a.insert(0, INF)
    a.append(-INF)

    kabu = 0
    kane = 1000

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

    for i in range(len(turn)):
        if turn[i] == 1:
            kabu = kane // a[i]
            kane -= a[i] * kabu
        elif turn[i] == -1:
            kane += a[i] * kabu
            kabu = 0

    print(kane)


if __name__ == '__main__':
    main()

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
        else:
            money += a[i] * stake
            stake = 0
    money += a[-1] * stake
    print(money)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

wallet = 1000
stock = 0

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

wallet += stock * a[-1]

print(wallet)

Submission status: Wrong Answer

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

ans = 1000
cnt = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted(a, reverse=True)
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 += a[i] * kabu
        kabu = 0
print(money + a[-1] * kabu)

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):
    #day i behaviour
    if A[i]<A[i+1]:
        # buy as many as possible
        S=M//A[i]
        M-=S*A[i]
    elif A[i]>A[i+1]:
        #sell all
        M+=S*A[i]
        S=0
print(M+S*A[-1])  # last day sell all stocks

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [300]
a += list(map(int,input().split()))
a += [0]
#print(a)

d = []
for i in range(1,len(a)-1):
  if a[i-1] > a[i] <= a[i+1]:
    d.append((a[i],-1))
  elif a[i-1] < a[i] >= a[i+1]:
    d.append((a[i],1))

m = 1000
k = 0
for x,y in d:
  c = m//x
  if y == -1:
    k += c
    m -= x*c
  else:
    m += k*x
    k = 0
  #print(x,y,m,k)
print(max(m,1000))

Submission status: Wrong Answer

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

kau = [0]*n
index = []

if a[0] < a[1]:
    kau[0] = 1
for i in range(1, n-1):
    if a[i-1] > a[i]:
        for j in range(i+1, n):
            if a[i] < a[j]:
                kau[i] = 1
                break
            if a[i] > a[j]:
                break
for i, j in enumerate(kau):
    if j == 1:
        index.append(i)
index.append(n)

ans = 1000
for i in range(len(index)-1):
    kabu = ans//a[index[i]]
    ans -= a[index[i]]*kabu
    ans += max(a[index[i]:index[i+1]])*kabu
        
print(ans)

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

Submission status: Wrong Answer

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

arr = [tmp[0]]

for i in range(1, n):
    if arr[-1] != tmp[i]:
        arr.append(tmp[i])

m, s = 1000, 0
for i in range(1, len(arr)):
    if arr[i - 1] < arr[i]:
        s += m // arr[i - 1]
        m -= m // arr[i - 1] * arr[i - 1]
        m += s * arr[i]
        s = 0

Submission status: Wrong Answer

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

wallet = 1000
stock = 0

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

wallet += stock * a[-1]

print(wallet)

Submission status: Wrong Answer

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

money = 1000
stock = 0
buy_turn = True

for i, a in enumerate(A[:N]):
    if buy_turn:
        if A[i + 1] < A[i]:
            continue
        buy_turn = False
        stock += money // A[i]
        money = money % A[i]

    else:
        cnt = 0
        M = a
        for x in A[i + 1:]:
            if M <= x:
                cnt += 1
                M = x
            else:
                break

        if cnt == 1:
            continue
        else:
            buy_turn = True
            money += A[i] * stock
            stock = 0

print(money)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    inlis = list(map(int, input().split()))
    
    kabu = 1000 // inlis[0]
    tmp = inlis[0]
    shoji = 1000 % inlis[0]
    min = inlis[0]

    for i in range(1, n-1):
        if inlis[i] > tmp:
            shoji += inlis[i] * kabu
            tmp = inlis[i]
            kabu = 0
            #print(kabu, shoji)
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                #print(kabu, shoji)
        elif inlis[i] < tmp:
            if inlis[i+1] > inlis[i]:
                kabu += shoji // inlis[i]
                shoji -= inlis[i] * kabu
                #print(kabu, shoji)
    if inlis[n-1] > inlis[n-2]:
        shoji += inlis[n-1] * kabu
        kabu = 0
    print(shoji)





if __name__ == "__main__":
    main()

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

mon = 1000
stock = 0

lim_a = [a_list[0]]
for i in range(1,N-1):
    if lim_a[-1] == a_list[i]:
        continue
    if a_list[i] <= a_list[i+1] and a_list[i] <= a_list[i-1]:
        lim_a.append(a_list[i])
    elif a_list[i] >= a_list[i+1] and a_list[i] >= a_list[i-1]:
        lim_a.append(a_list[i])
lim_a.append(a_list[-1])

s = 0 if lim_a[0] < lim_a[1] else 1
for i in range(s, len(lim_a)):
    if (i + s)%2 == 0:
        # buy
        stock += mon//lim_a[i]
        mon -= lim_a[i] * stock
    else:
        # sell
        mon += lim_a[i] * stock
        stock = 0
print(max(mon, 1000))

Submission status: Wrong Answer

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

dp = [[-1]*10000 for i in range(n+1)]
dp[0][0] = 1000


for i in range(n):
    for j in range(9999):
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i+1][j] >= a[i]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j]-a[i])
        
    for j in range(9999,0,-1):
        if dp[i+1][j] >= 0:
             dp[i+1][j-1] = max(dp[i+1][j-1],dp[i+1][j]+a[i])
print(max(dp[-1]))

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


print(money)

Submission status: Wrong Answer

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

m = 1000
s = 0

mx = [0] * n
for i in range(1, n):
    if a[i-1] < a[i]:
        mx[i] = 1
        mx[i-1] = 0
        
mn = [0] * n
for i in range(1, n):
    if a[i-1] > a[i]:
        mn[i] = 1
        mn[i-1] = 0
        
if a[0] < a[1]:
    mn[0] = 1
    
mn[-1] = 0

for i in range(n):
    if mx[i] == 1:
        m += s * a[i]
        s = 0
    if mn[i] == 1:
        s += m//a[i]
        m -= m//a[i] * a[i]

print(m)

Submission status: Wrong Answer

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

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],A[i]
    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:
n=int(input())
a=list(map(int,input().split()))

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

m=1000
k=0
for i in range(n-1):
    if l[i]==1:
        p=m//a[i]
        k+=p
        m-=p*a[i]

    if l[i]==-1:
        m+=k*a[i]
        k=0
    print(k,m)
m+=k*a[n-1]
print(m)

Submission status: Wrong Answer

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

money = 1000
max_money = money

open_price = a[0]
close_price = a[0]

for i in range(1, n):
	if a[i] >= a[i - 1]:
		close_price = a[i]
	else:			
		#print(i, a[i])
		#print(open_price, close_price)
		num = money // open_price
		left = money - num * open_price
		money = left + num * close_price
		max_money = max(money, max_money)
		open_price = a[i]
		close_price = 0
		#print(money)

num = money // open_price
left = money - num * open_price
money = left + num * close_price
max_money = max(money, max_money)

print(max_money)

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:
    # print(i)
    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-1
            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()))
ans=1000
for i in range(1,n):
    if a[i]>a[i-1]:
        ans += (a[i]-a[i-1])*(ans//a[i-1])
        print(ans)
print(ans)