Problem:


Score: 400 points

Problem Statement

To become a millionaire, M-kun has decided to make money by trading in the next N days. Currently, he has 1000 yen and no stocks - only one kind of stock is issued in the country where he lives.

He is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next N days will be as follows:

A_1 yen on the 1-st day, A_2 yen on the 2-nd day, ..., A_N yen on the N-th day.

In the i-th day, M-kun can make the following trade any number of times (possibly zero), within the amount of money and stocks that he has at the time.

Buy stock: Pay A_i yen and receive one stock.

Sell stock: Sell one stock for A_i yen.

What is the maximum possible amount of money that M-kun can have in the end by trading optimally?

Constraints

2 \leq N \leq 80

100 \leq A_i \leq 200

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the maximum possible amount of money that M-kun can have in the end, as an integer.

Sample Input 1

7
100 130 130 130 115 115 150

Sample Output 1

1685

In this sample input, M-kun has seven days of trading. One way to have 1685 yen in the end is as follows:

Initially, he has 1000 yen and no stocks.

Day 1: Buy 10 stocks for 1000 yen. Now he has 0 yen.

Day 2: Sell 7 stocks for 910 yen. Now he has 910 yen.

Day 3: Sell 3 stocks for 390 yen. Now he has 1300 yen.

Day 4: Do nothing.

Day 5: Buy 1 stock for 115 yen. Now he has 1185 yen.

Day 6: Buy 10 stocks for 1150 yen. Now he has 35 yen.

Day 7: Sell 11 stocks for 1650 yen. Now he has 1685 yen.

There is no way to have 1686 yen or more in the end, so the answer is 1685.

Sample Input 2

6
200 180 160 140 120 100

Sample Output 2

1000

In this sample input, it is optimal to do nothing throughout the six days, after which we will have 1000 yen.

Sample Input 3

2
157 193

Sample Output 3

1216

In this sample input, it is optimal to buy 6 stocks in Day 1 and sell them in Day 2, after which we will have 1216 yen.



Sample input:
7
100 130 130 130 115 115 150


Sample output:
1685

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache

    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
    
    @lru_cache(None)
    def transaction(self, money, stock, i, _inner_max):
        if stock == 0 and money < _inner_max - 1:
            return
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock = stock
        _money = money
        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            # print("buy",money,stock,i)
            self.transaction(money, stock, i + 1, _inner_max)
        # backtracking
        money,stock = _money,_stock

        ## sell
        if stock > 0:
            stock, money = 0, stock * self.prices[i] + money
            if money > _inner_max:
                _inner_max = money
                self.transaction(money, 0, i + 1, _inner_max)
        # backtracking
        money,stock = _money,_stock

        ## do nothing
        self.transaction(money, stock, i + 1, _inner_max)


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0,1000)
    print(solver._max)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    
    @lru_cache(None)
    def dp(i, m):
        if i == N-1:
            return m
        else:
            delta = A[i+1] - A[i]
            if delta > 0:
                maxa = m // A[i]
                return max(dp(i+1, m + delta*a) for a in range(maxa+1))
            else:
                return dp(i+1, m)

    print(dp(0, 1000))
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

ms = [[] for _ in range(n+1)]
ms[0] = [[1000, 0]] # 現金, 所有株数

def transaction(day, money, stock):
    # 何もしないケース
    ms[day+1].append([money, stock])
    if stock > 0:
        # 売るケース
        for s_n in range(1, stock+1):
            state = [money + a[i]*s_n, stock-s_n]
            if state not in ms[day+1]:
                ms[day+1].append(state)
    if money > 0:
        # 買うケース
        for s_n in range(1, math.floor(money / a[i])+1):
            state = [money - a[i]*s_n, stock+s_n]
            if state not in ms[day+1]:
                ms[day+1].append(state)

for i in range(n):
    for (money, stock) in ms[i]:
        transaction(i, money, stock)

print(max(np.array(ms[n])[:,0]))

Submission status: Time Limit Exceeded

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

from collections import defaultdict
k_y = defaultdict(int)
k_y[0] = 1000

#for hk,hy in k_y.items(): #所持株、金
#	print(hk,hy)

k_y_new = [ vvv for vvv in k_y.values()]
for i in range(n):
	for hk,hy in k_y.items(): #所持株、金
		kk = 0#想定所持株数
		while True:
			genkin = (hk - kk) * a[i] + hy
			
			if genkin < 0 :
				break
			else:
				if kk >= len(k_y_new):
					#print('add',genkin)
					k_y_new.append( genkin )
				else:
					#print('repl',k_y_new[kk], genkin)
					k_y_new[kk] = max(k_y_new[kk], genkin)
				kk = kk + 1
		#print( k_y_new )
	k_y = {x:y for x,y in enumerate(k_y_new)}
print( k_y_new[0] )

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

ans = 1000

def dfs(money, share, day):
    global ans
    if day > n:
        ans = max(ans, money)
        return
    max_buy = money//A[day-1]
    max_sel = share
#    for n_buy in range(-max_sel, max_buy+1):
#        dfs(money-n_buy*A[day-1], share+n_buy, day+1)
    for n_buy in [-max_sel, 0, max_buy]:
        dfs(money-n_buy*A[day-1], share+n_buy, day+1)

dfs(1000,0,1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split(" ")))
    
    ys_set = set([(1000,0)])
    for i in range(n):
        if 1<i:
            if a[i-1]<a[i]:
                ys_set, max_y = cal_set_sell(a[i], ys_set)
            elif a[i]<a[i-1]:
                ys_set, max_y = cal_set_buy(a[i], ys_set)
            else:
                continue
        else: 
            ys_set, max_y = cal_set_buy(a[i], ys_set)
            ys_set, max_y = cal_set_sell(a[i], ys_set)
    
    print(max_y)

def cal_set_sell(a_i, ys_set):
    ys_candidsate_set = set([])
    max_y = 0
    for one in ys_set:
        #sell
        for num_stock in range(one[1]+1):
            new_y = one[0] + num_stock*a_i
            new_s = one[1] - num_stock
            ys_candidsate_set.add((new_y, new_s))
            if max_y < new_y:
                max_y = new_y

    return ys_candidsate_set, max_y

def cal_set_buy(a_i, ys_set):
    ys_candidsate_set = set([])
    max_y = 0
    for one in ys_set:
        #buy
        for num_stock in range(one[0]//a_i+1):
            new_y = one[0] - num_stock*a_i
            new_s = one[1] + num_stock
            ys_candidsate_set.add((new_y, new_s))
            if max_y < new_y:
                max_y = new_y

    return ys_candidsate_set, max_y


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

ans = 1000

def dfs(money, share, day):
    global ans
    if day > n:
        ans = max(ans, money)
        return
    max_buy = money//A[day-1]
    max_sel = share
    for n_buy in range(-max_sel, max_buy+1):
        dfs(money-n_buy*A[day-1], share+n_buy, day+1)

dfs(1000,0,1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)
from functools import lru_cache

    
class Solution:
    def __init__(self,prices):
        self._max = 0
        self.prices = prices
    
    @lru_cache(None)
    def transaction(self, money, stock, i):
        if i == len(self.prices):
            self._max = max(self._max, money)
            return
        
        _stock = stock
        _money = money
        ## buy
        if money >= self.prices[i]:
            stock, money = divmod(money, self.prices[i])
            # print("buy",money,stock,i)
            self.transaction(money, stock, i + 1)
        # backtracking
        money,stock = _money,_stock

        ## sell
        if stock > 0:
            stock, money = 0, stock * self.prices[i] + money
            if money > 1000:
                self.transaction(money, 0, i + 1)
        # backtracking
        money,stock = _money,_stock

        ## do nothing
        self.transaction(money, stock, i + 1)


def main():
    n = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    solver = Solution(A)
    solver.transaction(1000, 0, 0)
    print(solver._max)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
B = [0] + LI()

A = [0,B[1]]
for i in range(1,N):
    if B[i] != B[i+1]:
        A.append(B[i+1])

N = len(A)-1

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] == min(A[i:j+1]) and A[j] == max(A[i:j+1]) and A[i] < A[j]:
                    res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
        return res

print(dfs(1,1000))

Submission status: Time Limit Exceeded

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

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

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

print(money)

Submission status: Time Limit Exceeded

Solution code:
import sys

#def input():
#    return sys.stdin.readline()[:-1]

class M_Kun:
    def __init__(self):
        self.money = 1000
        self.stock = 0
        
    def buy(self, value):
        num = 0
        while value * (num+1) <= self.money:
            num += 1
        self.money -= value * num
        self.stock += num
        
    def sell(self, value):
        self.money += value * self.stock
        self.stock = 0


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

    local_min = [False]*N
    local_max = [False]*N

    is_ascending = False
    for a in A[1:]:
        if a > A[0]:
            is_ascending = True
            break
        elif a < A[0]:
            break

    if is_ascending:
        local_min[0] = True
    else:
        local_max[0] = True

    for i in range(N-1):
        if A[i] == A[i+1]:
            continue
        elif is_ascending and A[i] > A[i+1]:
            local_max[i] = True
            is_ascending = False
        elif (not is_ascending) and A[i] < A[i+1]:
            local_min[i] = True
            is_ascending = True

    if is_ascending:
        local_max[-1] = True


    m_kun = M_Kun()

    for i in range(N):
        if local_min[i]:
            m_kun.buy(A[i])
        if local_max[i]:
            m_kun.sell(A[i])

    print(m_kun.money)
    
main()

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
lis = []
prv = -1
for i in range(n):
    if prv != A[i]:
        lis.append(A[i])
        prv = A[i]
#print(lis)
#dp = [[[0] * ]
def dfs(money,kabu,now):
    if now == len(lis):
        global ans
        ans = max(money,ans)
        return;
    if kabu != 0:
        dfs(money + kabu*lis[now],0,now+1)
    if money//lis[now] >= 1:
        dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
    dfs(money,kabu,now+1)
ans = 1000
dfs(1000,0,0)
print(ans)

Submission status: Time Limit Exceeded

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

A.append(0)

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


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

    print(res)

Submission status: Time Limit Exceeded

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

from itertools import product
a=[0,1]  #0:buy  1:sell
Ls = list(product(a, repeat=N-1))
# print('Ls:',Ls)

out=0
for L in Ls:
    # print('L:',L)
    money=1000
    kabu=0
    for i in range(N-1):
        if L[i]==0:
            kabu+=money // A[i]
            money=money % A[i]

        else:
            money+=kabu*A[i]
            kabu=0
        # print('money,kabu:',money,kabu)
    money+=kabu*A[N-1]  #last
    out=max(out,money)

print(out)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = list([int(x) for x in input().split()])

stack = deque()

stack.appendleft((0, 1000, 0))
max_money = 1000

while stack:
    target = stack.popleft()

    day = target[0]
    money = target[1]
    stock = target[2]

    if day + 1 <= N:
        stack.appendleft((day + 1, money + stock * A[day], 0))
        stack.appendleft(
            (day + 1, money - (money // A[day]) * A[day], money // A[day]))
    else:
        if max_money < money:
            max_money = money

print(max_money)

Submission status: Time Limit Exceeded

Solution code:
def INT():
    return int(input())

def MI():
    return map(int, input().split())

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

N = INT()
A = LI()
ans = 1000
purchase = 0

for i in range(1, N):
    tmp = ans
    
    if A[i] > A[i - 1]:
        while True:
            if tmp - A[i - 1] < 0:
                break
            tmp -= A[i - 1]
            purchase += 1
        ans = max(ans, tmp + A[i] * purchase)
        purchase = 0

print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = list([int(x) for x in input().split()])

stack = deque()

stack.appendleft((0, 1000, 0))
max_money = 1000

while stack:
    target = stack.popleft()

    day = target[0]
    money = target[1]
    stock = target[2]

    if day + 1 <= N:
        max_buy = money // A[day]
        max_fee = stock * A[day]

        stack.appendleft((day + 1, money + stock * A[day], 0))
        stack.appendleft(
            (day + 1, money - (money // A[day]) * A[day], money // A[day]))
    else:
        if max_money < money:
            max_money = money

print(max_money)

Submission status: Time Limit Exceeded

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

dp = [[-1]*n for i in range(5000)]
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(5000):
        for l in range(5000):
            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(5000):
    ans = max(ans, dp[m][n-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class M_Kun:
    def __init__(self):
        self.money = 1000
        self.stock = 0
        
    def buy(self, value):
        num = 0
        while value * (num+1) <= self.money:
            num += 1
        self.money -= value * num
        self.stock += num
        
    def sell(self, value):
        self.money += value * self.stock
        self.stock = 0

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


local_min = [False]*N
local_max = [False]*N

is_ascending = False
for a in A[1:]:
    if a > A[0]:
        is_ascending = True
        break
    elif a < A[0]:
        break

if is_ascending:
    local_min[0] = True
else:
    local_max[0] = True

for i in range(N-1):
    if A[i] == A[i+1]:
        continue
    elif is_ascending and A[i] > A[i+1]:
        local_max[i] = True
        is_ascending = False
    elif (not is_ascending) and A[i] < A[i+1]:
        local_min[i] = True
        is_ascending = True
        
if is_ascending:
    local_max[-1] = True
    

m_kun = M_Kun()

for i in range(N):
    if local_min[i]:
        m_kun.buy(A[i])
    if local_max[i]:
        m_kun.sell(A[i])
        
print(m_kun.money)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split(" ")))
    
    ys_set = set([(1000,0)])
    for i in range(n):
        ys_set = cal_set(a[i], ys_set)
    
    ans = 0
    for one in ys_set:
        new_ans = one[0]
        if ans < new_ans:
            ans = new_ans
    print(ans)

def cal_set(a_i, ys_set):
    ys_candidsate_set = set([])
    for one in ys_set:
        #buy
        for num_stock in range(one[0]//a_i+1):
            new_y = one[0] - num_stock*a_i
            new_s = one[1] + num_stock
            ys_candidsate_set.add((new_y, new_s))

        #sell
        for num_stock in range(one[1]+1):
            new_y = one[0] + num_stock*a_i
            new_s = one[1] - num_stock
            ys_candidsate_set.add((new_y, new_s))

    return ys_candidsate_set

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    K = 5*10**6
    INF = 10**18
    dp = [[-INF]*K for i in range(n+1)]
    dp[0][0] = 1000
    for i in range(n):
        for j in range(K):
            dp[i+1][j] = dp[i][j]
        # sell
        for j in range(K):
            if j == 0:
                continue
            if dp[i][j] >= 0:
                #if i == 2 and j == 10:
                    #print(dp[i+1][0], dp[i][j]+j*A[i])
                dp[i+1][0] = max(dp[i+1][0], dp[i][j]+j*A[i])
                #if i == 2 and j == 10:
                    #print(dp[i+1][0])

        # buy
        for j in range(K):
            if dp[i][j] >= 0:
                q, r = divmod(dp[i][j], A[i])
                dp[i+1][q] = max(r, dp[i+1][q])
    #print(dp[1])
    ans = -INF
    for j in range(K):
        ans = max(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: UTF-8
import itertools
  
#2≤N≤80
#100≤Ai≤200
#入力はすべて整数


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


T = list(itertools.product(range(3), repeat=N))
#print(T[:2])

maxM = 1000

#0なにもしない　1かう 2うる
for t in T:
  M = 1000 #金
  K = 0 #株
  for i in range(len(t)):
    if t[i] == 1:
      #買う
      K += int(M/A[i])
      M = M%A[i]
    elif t[i] ==2:
      #全売り
      M += K*A[i]
      K = 0
  
  #print(M)
  maxM = max(maxM,M)
    
    
print(maxM)

Submission status: Time Limit Exceeded

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

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

while(i<N-1):
    if A[i] >= A[i+1]:
        i += 1
        continue
    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

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

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

now = 1000
a = 0
ans = []


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

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[*map(int,input().split())]
a=1000
c=0
for i in range(n-1):
  if l[i]>l[i+1]:
    a+=c*l[i]
    c=0
  if l[i]<l[i+1]:
    while a>=l[i]:
      a-=l[i]
      c+=1
print(a+c*l[n-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = [0] + LI()

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] == min(A[i:j+1]) and A[j] == max(A[i:j+1]) and A[i] < A[j]:
                    res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
        return res

print(dfs(1,1000))

Submission status: Time Limit Exceeded

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

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

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

print(money)

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
lis = []
prv = -1
for i in range(n):
    if prv != A[i]:
        lis.append(A[i])
        prv = A[i]
#print(lis)
#dp = [[[0] * ]
def dfs(money,kabu,now):
    global ans
    if now == len(lis):
        ans = max(money,ans)
        return;
    if kabu != 0:
        dfs(money + kabu*lis[now],0,now+1)
    if money//lis[now] >= 1:
        dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
    dfs(money,kabu,now+1)
ans = 1000
dfs(1000,0,0)
print(ans)

Submission status: Time Limit Exceeded

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

from itertools import product
a=[0,1]  #0:buy  1:sell
Ls = list(product(a, repeat=N))
# print('Ls:',Ls)
out=0
for L in Ls:
    # print('L:',L)
    money=1000
    kabu=0
    for i in range(N):
        if L[i]==0:
            kabu+=money // A[i]
            money=money % A[i]

        else:
            money+=kabu*A[i]
            kabu=0
        # print('money,kabu:',money,kabu)
    out=max(out,money)

print(out)

Submission status: Time Limit Exceeded

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

memo = {}

def solve(mon, i, haveN):
    key = str(mon) + " " + str(i) + " " + str(haveN)
    if key in memo:
        return memo[key]
    if i >= len(listA):
        memo[key] = 0
        return memo[key]
    elif i == len(listA)-1:
        mon+=haveN*listA[i]
        haveN=0
        memo[key] = mon
        return memo[key]
    else:
        memo[key] =  max(solve(mon, i+1, haveN), solve(mon-listA[i]*(mon//listA[i]), i+1, haveN+mon//listA[i]), solve(mon+haveN*listA[i], i+1, 0))
        return memo[key]
print(solve(1000, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = [0] + LI()

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n,money):
    if n == N+1:
        return money
    else:
        res = money
        for i in range(n,N):  # 購入
            for j in range(i+1,N+1):  # 売却
                if A[i] < A[j]:
                    res = max(res,dfs(j+1,money+(A[j]-A[i])*(money//A[i])))
        return res

print(dfs(1,1000))

Submission status: Time Limit Exceeded

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

money=1000
stocks=0

for i in range(N): 
    if i==N-1:
        #売る
        while stocks>0:
            money += A[i]
            stocks-=1    
    elif A[i+1]>A[i]:
        #買う
        while money>=A[i]:
            money -= A[i]
            stocks+=1
    elif A[i+1]<A[i]:
        #売る
        while stocks>0:
            money += A[i]
            stocks-=1
print(money)

Submission status: Time Limit Exceeded

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

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

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

print(money)

Submission status: Time Limit Exceeded

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

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

print(money)

Submission status: Time Limit Exceeded

Solution code:
def allin(m,k,d):
  if k > 0:
    return m+k*a[d], 0
  else:
    max = m // a[d]
    return m-max*a[d], k+max
  

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

ans = -1

for i in range(2**n - 1):
  money = 1000
  kabu = 0
  for j in range(n-1):
    if ((i >> j) & 1):
      money, kabu = allin(money, kabu, j)
  if kabu > 0:
    money += kabu * a[n-1]
  if ans < money:
    ans = money
    
print(ans)

Submission status: Time Limit Exceeded

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

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

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

print(money)

Submission status: Time Limit Exceeded

Solution code:
def INT():
    return int(input())

def MI():
    return map(int, input().split())

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

N = INT()
A = LI()
ans = 1000

for i in range(1, N):
    purchase = 0
    tmp = ans
    
    if A[i] > A[i - 1]:
        while 1:
            if tmp - A[i - 1] < 0:
                break
            tmp -= A[i - 1]
            purchase += 1
        ans = max(ans, tmp + A[i] * purchase)
        
        
print(ans)