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: Accepted

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
from scipy import optimize
# from numba import jit 
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, product
import string 
import math 
inf = float('inf')
from functools import lru_cache
sys.setrecursionlimit(10**7)
MOD = 10**9+7
# MOD = 998244353


class NumberTheory():
  def __init__(self, n=2*10**6, numpy=True):
    self.n = n
    self.np_flg = numpy 
    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)
  def sieve_of_eratosthenes(self, n):
    if self.np_flg:
      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0
      for i in range(2, int(n**.5)+1):
        if sieve[i]: sieve[i*2::i] = 0
      prime_numbers = np.flatnonzero(sieve)
    else:
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
    return sieve, prime_numbers 
  def prime_factorize(self, n):
    res = dict()
    if n < 2: return res
    border = int(n**.5)
    for p in self.prime_numbers:
      if p > border: break
      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
      if n == 1: return res
    res[n] = 1; return res
  def prime_factorize_factorial(self, n):
    res = dict()
    for i in range(2, n+1):
      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c
    return res
  def gcd(self, a, b): return self.gcd(b, a%b) if b else abs(a)
  def lcm(self, a, b): return abs(a // self.gcd(a, b) * b)
  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return divisors
  @staticmethod
  def base_convert(n, b):
    if not n: return [0]
    res = []
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res.append(r)
    return res

class UnionFind():
  def __init__(self, n=10**6):
    self.root = list(range(n))
    self.height = [0] * n 
    self.size = [1] * n 
  def find_root(self, u):
    if self.root[u] == u: return u
    self.root[u] = self.find_root(self.root[u])
    return self.root[u]
  def unite(self, u, v):
    ru = self.find_root(u)
    rv = self.find_root(v)
    if ru == rv: return 
    hu = self.height[ru]
    hv = self.height[rv]
    if hu >= hv:
      self.root[rv] = ru 
      self.size[ru] += self.size[rv]
      self.height[ru] = max(hu, hv+1)
    else:
      self.root[ru] = rv 
      self.size[rv] += self.size[ru]

class Combinatorics():
  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):
    self.mod = mod
    self.nCr = dict()
    self.np_flg=numpy
    self.make_mod_tables(N, n)

  sys.setrecursionlimit(10**6)
  def choose(self, n, r, mod=None): # no mod, or mod ≠ prime
    if r > n or r < 0: return 0
    if r == 0: return 1
    if (n, r) in self.nCr: return self.nCr[(n, r)]
    if not mod:
      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))
    else:
      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod
    return self.nCr[(n,r)]
  
  def cumprod(self, a):
    p = self.mod
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p
    return np.ravel(a)[:l]

  def make_mod_tables(self, N, n):
    p = self.mod
    if self.np_flg:
      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = self.cumprod(ifac)[n::-1]
      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;
      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
      n_choose = [None] * (n+1); n_choose[0] = 1
      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p
      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p
    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose

  def mod_choose(self, n, r):
    return self.fac[n]*self.ifac[r]%self.mod*self.ifac[n-r]%self.mod

def z_algorithm(s):
  n = len(s)
  a = [0] * n; a[0] = n
  l = r = -1
  for i in range(1, n):
    if r >= i: a[i] = min(a[i-l], r-i)
    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
    if i+a[i] >= r: l, r = i, i+a[i]
  return a

class ABC001():
  def A():
    h1, h2 = map(int, sys.stdin.read().split())
    print(h1-h2)
  def B(): pass
  def C(): pass 
  def D(): pass 

class ABC002():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(max(x, y))
  def B():
    vowels = set('aeiou')
    s = sys.stdin.readline().rstrip() 
    t = ''
    for c in s:
      if c in vowels: continue 
      t += c 
    print(t)
  def C():
    *coords, = map(int, sys.stdin.readline().split())
    def triangle_area(x0, y0, x1, y1, x2, y2):
      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;
      return abs(x1*y2 - x2*y1) / 2
    print(triangle_area(*coords))
  def D():
    n, m = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(m):
      x, y = map(int, sys.stdin.readline().split())
      x -= 1; y -= 1
      edges.add((x, y))
    cand = []
    for i in range(1, 1<<n):
      s = [j for j in range(n) if i>>j & 1]
      for x, y in combinations(s, 2):
        if (x, y) not in edges: break
      else:
        cand.append(len(s))
    print(max(cand))

class ABC003():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)*5000)
  def B():
    atcoder = set('atcoder')
    s, t = sys.stdin.read().split()
    for i in range(len(s)):
      if s[i] == t[i]: continue
      if s[i] == '@' and t[i] in atcoder: continue 
      if t[i] == '@' and s[i] in atcoder: continue
      print('You will lose')
      return 
    print('You can win')
  def C():
    n, k, *r = map(int, sys.stdin.read().split())
    res = 0
    for x in sorted(r)[-k:]:
      res = (res+x) / 2
    print(res)
  def D(): pass 

class ABC004():
  def A():
    print(int(sys.stdin.readline().rstrip())*2)
  def B():
    c = [sys.stdin.readline().rstrip() for _ in range(4)]
    for l in c[::-1]:
      print(l[::-1])
  def C():
    n = int(sys.stdin.readline().rstrip())
    n %= 30
    res = list(range(1, 7))
    for i in range(n):
      i %= 5
      res[i], res[i+1] = res[i+1], res[i]
    print(''.join(map(str, res)))
  def D(): pass 

class ABC005():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(y//x)
  def B():
    n, *t = map(int, sys.stdin.read().split())
    print(min(t))
  def C():
    t = int(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    m = int(sys.stdin.readline().rstrip())
    b = [int(x) for x in sys.stdin.readline().split()]
    i = 0
    for p in b:
      if i == n: print('no'); return 
      while p-a[i] > t:
        i += 1
        if i == n: print('no'); return 
      if a[i] > p: print('no'); return 
      i += 1
    print('yes')
  def D():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros((n+1, n+1), dtype=np.int64)
    for y in range(1, n+1):
      for x in range(1, n+1):
        max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
    res = np.arange(n**2+1)[:, None]
    i = np.arange(1, n+1)
    res = max_del[i, np.minimum(res//i, n)].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')

class ABC006():
  def A():
    n = sys.stdin.readline().rstrip()
    if '3' in n: print('YES')
    elif int(n)%3 == 0: print('YES')
    else: print('NO')
  def B():
    mod = 10007
    t = [0, 0, 1]
    for _ in range(1001001):
      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod
    n = int(sys.stdin.readline().rstrip())
    print(t[n-1])
  def C():
    n, m = map(int, sys.stdin.readline().split())
    cnt = [0, 0, 0]
    if m == 1: cnt = [-1, -1, -1]
    else:
      if m & 1: m -= 3; cnt[1] += 1; n -= 1
      cnt[2] = m//2 - n 
      cnt[0] = n - cnt[2]
    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
    else: print(*cnt, sep=' ')
  def D():
    n, *c = map(int, sys.stdin.read().split())
    lis = [inf]*n 
    for x in c: lis[bi_l(lis, x)] = x 
    print(n - bi_l(lis, inf))

class ABC007():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n-1)
  def B():
    s = sys.stdin.readline().rstrip()
    if s == 'a': print(-1)
    else: print('a')
  def C():
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())
    sy -= 1; sx -=1; gy -= 1; gx -= 1
    maze = [sys.stdin.readline().rstrip() for _ in range(r)]
    queue = deque([(sy, sx)])
    dist = np.full((r, c), np.inf); dist[sy, sx] = 0
    while queue:
      y, x = queue.popleft()
      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i += y; j += x
        if maze[i][j] == '#' or dist[i, j] != np.inf: continue 
        dist[i, j] = dist[y, x] + 1
        queue.append((i, j))
    print(int(dist[gy, gx]))
  def D():
    ng = set([4, 9])
    def count(d):
      return d if d<=4 else d-1
    def f(n):
      x = [int(d) for d in str(n)]
      flg = True
      dp = 0
      for d in x:
        dp = dp*8 + flg*count(d)
        if d in ng: flg = False
      return n-(dp+flg)
    a, b = map(int, sys.stdin.readline().split())
    print(f(b) - f(a-1))
        
class ABC008():
  def A():
    s, t = map(int, sys.stdin.readline().split())
    print(t-s+1)
  def B():
    n, *s = sys.stdin.read().split()
    res = defaultdict(int)
    for name in s: res[name] += 1
    print(sorted(res.items(), key=lambda x: x[1])[-1][0])
  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    c = n - np.count_nonzero(a[:, None]%a, axis=1)
    print(np.sum((c+1)//2/c))
  def D(): pass

class ABC009():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)//2)
  def B():
    n, *a = map(int, sys.stdin.read().split())
    print(sorted(set(a))[-2])
  def C():
    n, k = map(int, sys.stdin.readline().split())
    s = list(sys.stdin.readline().rstrip())
    cost = [1]*n
    r = k
    for i in range(n-1):
      q = []
      for j in range(i+1, n):
        if s[j] < s[i] and cost[i]+cost[j] <= r:
          heappush(q, (s[j], cost[i]+cost[j], -j))
      if not q: continue
      _, c, j = heappop(q); j = -j 
      s[i], s[j] = s[j], s[i]
      r -= c 
      cost[i] = cost[j] = 0
    print(''.join(s)) 
  def D(): pass 

class ABC010():
  def A():
    print(sys.stdin.readline().rstrip()+'pp')
  def B():
    n, *a = map(int, sys.stdin.read().split())
    tot = 0
    for x in a:
      c = 0 
      while x%2==0 or x%3==2:
        x -= 1
        c += 1
      tot += c
    print(tot)
  def C():
    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
    x, y = np.array(xy).reshape(-1, 2).T
    def dist(x1, y1, x2, y2):
      return np.sqrt((x2-x1)**2 + (y2-y1)**2)
    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
    print(ans)
  def D(): pass 

class ABC011():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n%12+1)
  def B():
    s = sys.stdin.readline().rstrip() 
    print(s[0].upper()+s[1:].lower())
  def C():
    n, *ng = map(int, sys.stdin.read().split())
    ng = set(ng)
    if n in ng: print('NO')
    else:
      r = 100
      while n > 0:
        if r == 0: print('NO'); return
        for i in range(3, 0, -1):
          if (n-i) in ng: continue 
          n -= i
          r -= 1
          break 
        else: print('NO'); return 
      print('YES')
  def D(): pass 

class ABC032():
  def A():
    a, b, n = map(int, sys.stdin.read().split())
    l = NumberTheory().lcm(a, b)
    print((n+l-1)//l*l)
  def B():
    s, k = sys.stdin.read().split()
    k = int(k)
    res = set()
    for i in range(len(s)-k+1):
      res.add(s[i:i+k])
    print(len(res))
  def C():
    n, k, *s = map(int, sys.stdin.read().split())
    if 0 in s: print(n); return 
    s += [inf]
    res = 0
    l = r = 0
    tmp = 1
    while r <= n:
      tmp *= s[r]
      while tmp > k:
        res = max(res, r-l)
        tmp //= s[l]
        l += 1
      r += 1
    print(res)
  def D(): pass 

class ABC033():
  def A():
    n = set(sys.stdin.readline().rstrip())
    print('SAME' if len(n)==1 else 'DIFFERENT')
  def B():
    n = int(sys.stdin.readline().rstrip())
    res = dict()
    for _ in range(n):
      s, p = sys.stdin.readline().split()
      p = int(p)
      res[s] = p 
    tot = sum(res.values())
    for s, p in res.items():
      if p > tot/2:
        print(s)
        return
    print('atcoder')
  def C():
    s = sys.stdin.readline().rstrip()
    res = sum(not '0' in f for f in s.split('+'))
    print(res)
  def D(): pass 

class ABC034():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print('Better' if y>x else 'Worse')
  def B():
    n = int(sys.stdin.readline().rstrip())
    print(n+1 if n&1 else n-1)
  def C():
    h, w = map(int, sys.stdin.read().split())
    combinatorics = Combinatorics(n=2*10**5, numpy=True, mod=MOD)
    print(combinatorics.mod_choose(h+w-2, h-1))
  def D():
    n, k, *wp = map(int, sys.stdin.read().split())
    w, p = np.array(wp).reshape(-1, 2).T 
    def f(x):
      return np.sort(w*(p-x))[-k:].sum()
    print(optimize.bisect(f, 0, 100))

class ABC035():
  def A():
    w, h = map(int, sys.stdin.readline().split())
    print('4:3' if 4*h==3*w else '16:9')
  def B():
    s, t = sys.stdin.read().split()
    y = 0
    x = 0
    z = 0
    for c in s:
      if c == '?': z += 1
      elif c == 'L': x -= 1
      elif c == 'R': x += 1
      elif c == 'D': y -= 1
      elif c == 'U': y += 1 
    d = abs(y)+abs(x)
    if t == '1':
      print(d+z)
    else:
      print(max(d-z, (d-z)&1))
  def C():
    n, q, *lr = map(int, sys.stdin.read().split())
    l, r = np.array(lr).reshape(q, 2).T
    res = np.zeros(n+1, dtype=int)
    np.add.at(res, l-1, 1)
    np.subtract.at(res, r, 1)
    np.cumsum(res, out=res)
    res = res&1
    print(''.join(map(str, res[:-1])))
  def D():
    n, m, t = map(int, sys.stdin.readline().split())
    point = np.array(sys.stdin.readline().split(), dtype=int)
    a, b, c = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(m, 3).T 
    a -= 1; b -= 1 
    d_1 = shortest_path(csr_matrix((c, (a, b)), (n, n)), method='D', directed=True, indices=0)
    d_2 = shortest_path(csr_matrix((c, (b, a)), (n, n)), method='D', directed=True, indices=0)
    print(int(np.amax((t-(d_1+d_2))*point)))

class ABC036():
  def A():
    a, b = map(int, sys.stdin.readline().split())
    print((b+a-1)//a)
  def B():
    n, *s = sys.stdin.read().split()
    n = int(n)
    for j in range(n):
      row = ''
      for i in range(n-1, -1, -1):
        row += s[i][j]
      print(row)
  def C():
    n, *a = map(int, sys.stdin.read().split())
    b = [None]*n
    prev = None
    j = -1
    for i, x in sorted(enumerate(a), key=lambda x: x[1]):
      if x != prev: j += 1
      b[i] = j
      prev = x     
    print(*b, sep='\n') 
  def D():
    n, *ab = map(int, sys.stdin.read().split())
    edges = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)]*2):
      a -= 1; b -= 1
      edges[a].append(b)
      edges[b].append(a)
    parent = [None]*n
    def count(u):
      black, white = 1, 1
      for v in edges[u]:
        if v == parent[u]: continue 
        parent[v] = u
        b, w = count(v)
        black *= w; black %= MOD 
        white *= (b+w)%MOD; white %= MOD
      return black, white
    print(sum(count(0))%MOD)

class ABC037():
  def A():
    a, b, c = map(int, sys.stdin.readline().split())
    print(c//min(a, b))
  def B():
    n, q, *lrt = map(int, sys.stdin.read().split())
    a = np.zeros(n, dtype=int)
    for l, r, t in zip(*[iter(lrt)]*3):
      a[l-1:r] = t 
    print(*a, sep='\n')
  def C():
    n, k, *a = map(int, sys.stdin.read().split())
    a = np.array([0]+a)
    np.cumsum(a, out=a)
    s = (a[k:] - a[:-k]).sum()
    print(s)
  def D():
    h, w = map(int, sys.stdin.readline().split())
    a = [[int(x) for x in sys.stdin.readline().split()] for _ in range(h)]
    dyx = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    path = [[None]*w for _ in range(h)]
    def paths(i, j):
      if path[i][j]: return path[i][j]
      val = a[i][j]
      cnt = 1
      for dy, dx in dyx:
        y = i+dy; x = j+dx
        if 0<=y<h and 0<=x<w and a[y][x]<val:
          cnt += paths(y, x)
          cnt %= MOD 
      path[i][j] = cnt 
      return cnt 
    tot = 0
    for i in range(h):
      for j in range(w):
        tot += paths(i, j)
        tot %= MOD 
    print(tot)

class ABC038():
  def A():
    s = sys.stdin.readline().rstrip()
    print('YES' if s[-1]=='T' else 'NO')
  def B():
    a, b, c, d = map(int, sys.stdin.read().split())
    print('YES' if a==c or b==c or a==d or b==d else 'NO')
  def C():
    n, *a = map(int, sys.stdin.read().split())
    a += [-1]
    cnt = n 
    tmp = 1
    for i in range(n):
      if a[i+1] > a[i]:
        tmp += 1
      else:
        cnt += tmp*(tmp-1)//2
        tmp = 1
    print(cnt)
  def D():
    n, *wh = map(int, sys.stdin.read().split())
    wh = sorted(zip(*[iter(wh)]*2), key=lambda x: (-x[0], x[1]))
    w = [x[1] for x in wh][::-1]
    res = [inf] * n 
    for x in w:
      res[bi_l(res, x)] = x
    print(bi_l(res, inf))

class ABC039():
  def A():
    a, b, c = map(int, sys.stdin.readline().split())
    print((a*b+b*c+c*a)*2)
  def B():
    x = int(sys.stdin.readline().rstrip())
    for n in range(1, int(x**0.5)+1):
      if pow(n, 4)==x:
        print(n); return
  def C():
    board = 'WBWBWWBWBWBW' * 3
    convert = 'Do, *, Re, *, Mi, Fa, *, So, *, La, *, Si'.split(', ')
    s = sys.stdin.readline().rstrip()
    print(convert[board.index(s)])
  def D():
    h, w = map(int, sys.stdin.readline().split())
    s = sys.stdin.read().split()
    dyx = list(product((-1, 0, 1), repeat=2))
    black_certain = set()
    black_before = set()
    for i in range(h):
      for j in range(w):
        black_cand = set()
        for dy, dx in dyx:
          y = i+dy; x = j+dx
          if y<0 or y>=h or x<0 or x>=w: continue 
          if s[y][x] == '.': break 
          black_cand.add((y, x))
        else:
          black_before.add((i, j))
          black_certain |= black_cand 
    for i in range(h):
      for j in range(w):
        if s[i][j]=='#' and not (i, j) in black_certain:
          print('impossible')
          return 
    print('possible')
    for i in range(h):
      row = ''
      for j in range(w):
        row += '#' if (i, j) in black_before else '.'
      print(''.join(row))
          
class ABC040():
  def A():
    n, x = map(int, sys.stdin.readline().split())
    print(min(x-1, n-x))
  def B():
    n = int(sys.stdin.readline().rstrip())
    res = inf 
    for i in range(1, int(n**.5)+1):
      res = min(res, n//i-i+n%i)
    print(res)
  def C():
    n, *h = map(int, sys.stdin.read().split())
    h = [h[0]]+h
    cost = [None] * (n+1); cost[0] = cost[1] = 0
    for i in range(2, n+1):
      cost[i] = min(
        cost[i-2] + abs(h[i]-h[i-2]),
        cost[i-1] + abs(h[i]-h[i-1])
      )
    print(cost[n])
  def D():
    n, m = map(int, sys.stdin.readline().split())
    uf = UnionFind(n=n)
    queue = []
    for _ in range(m):
      a, b, y = map(int, sys.stdin.readline().split())
      heappush(queue, (-(2*y), a-1, b-1))
    q = int(sys.stdin.readline().rstrip())
    for i in range(q):
      v, y = map(int, sys.stdin.readline().split())
      heappush(queue, (-(2*y+1), v-1, i))
    res = [None] * q
    while queue:
      y, i, j = heappop(queue)
      if y&1:
        res[j] = uf.size[uf.find_root(i)]
      else:
        uf.unite(i, j)
    print(*res, sep='\n')

class ABC041():
  def A():
    s, i = sys.stdin.read().split()
    i = int(i)
    print(s[i-1])
  def B():
    a, b, c = map(int, sys.stdin.readline().split())
    ans = a * b % MOD * c % MOD 
    print(ans)
  def C():
    n, *a = map(int, sys.stdin.read().split())
    for i, h in sorted(enumerate(a), key=lambda x: -x[1]):
      print(i+1)
  def D():
    n, m, *xy = map(int, sys.stdin.read().split())
    *xy, = zip(*[iter(xy)]*2)
    edges = [0] * n 
    for x, y in xy:
      x -= 1; y -= 1
      edges[x] |= 1<<y
    comb = [None] * (1<<n); comb[0] = 1
    def count(edges, bit):
      if comb[bit] is not None: return comb[bit]
      comb[bit] = 0
      for i in range(n):
        if (bit>>i) & 1 and not edges[i]:
          nxt_bit = bit & ~(1<<i)
          nxt_edges = edges.copy() 
          for j in range(n):
            nxt_edges[j] &= ~(1<<i)
          cnt = count(nxt_edges, nxt_bit)
          comb[bit] += cnt
      return comb[bit]
    print(count(edges, (1<<n)-1))

class ABC042():
  def A():
    a = [int(x) for x in sys.stdin.readline().split()]
    c = Counter(a)
    print('YES' if c[5]==2 and c[7]==1 else 'NO')
  def B():
    n, l, *s = sys.stdin.read().split()
    print(''.join(sorted(s)))
  def C():
    n, k, *d = sys.stdin.read().split()
    l = len(n)
    ok = sorted(set(string.digits)-set(d))
    cand = [int(''.join(p)) for p in product(ok, repeat=l)] + [int(min(x for x in ok if x > '0')+min(ok)*l)]
    print(cand[bi_l(cand, int(n))])
  def D():
    h, w, a, b = map(int, sys.stdin.read().split())
    combinatorics = Combinatorics(n=2*10**5, mod=MOD, numpy=True)
    tot = combinatorics.mod_choose(h+w-2, h-1)
    i = np.arange(h-a, h)
    ng = np.sum(combinatorics.mod_choose(i+b-1, i) * combinatorics.mod_choose(h-i+w-b-2, h-1-i) % MOD)
    tot -= ng; tot %= MOD
    print(tot)

class ABC043():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((1+n)*n//2)
  def B():
    s = sys.stdin.readline().rstrip()
    t = ''
    for c in s:
      if c == 'B': t = t[:-1]
      else: t += c
    print(t)
  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    x = np.around(a.sum()/n).astype(int)
    print(np.sum((a-x)**2))
  def D():
    s = sys.stdin.readline().rstrip()
    n = len(s)
    for i in range(n-1):
      if s[i] == s[i+1]:
        print(i+1, i+2); return 
    for i in range(n-2):
      if s[i] == s[i+2]:
        print(i+1, i+3); return 
    print(-1, -1)

class ABC170():
  def A():
    x = [int(x) for x in sys.stdin.readline().split()]
    for i in range(5):
      if x[i] != i+1:
        print(i+1)
        break
  def B():
    x, y = map(int, sys.stdin.readline().split())
    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
  def C():
    x, n, *p = map(int, sys.stdin.read().split())
    a = list(set(range(102)) - set(p))
    a = [(abs(y-x), y) for y in a]
    print(sorted(a)[0][1])
  def D():
    n, *a = map(int, sys.stdin.read().split())
    cand = set(a)
    cnt = 0
    for x, c in sorted(Counter(a).items()):
      cnt += c == 1 and x in cand
      cand -= set(range(x*2, 10**6+1, x))
    print(cnt)
  def E():
    n, q = map(int, sys.stdin.readline().split())
    queue = [] 
    m = 2*10**5
    infants = [[] for _ in range(m)]
    highest_rate = [None] * m
    where = [None] * n
    rate = [None] * n

    def entry(i, k):
      where[i] = k
      while infants[k]:
        r, j = heappop(infants[k])
        if where[j] != k or j == i: continue 
        if rate[i] >= -r:
          highest_rate[k] = rate[i]
          heappush(queue, (rate[i], k, i))
        heappush(infants[k], (r, j))
        break
      else:
        highest_rate[k] = rate[i]
        heappush(queue, (rate[i], k, i))
      heappush(infants[k], (-rate[i], i))

    def transfer(i, k):
      now = where[i]
      while infants[now]:
        r, j = heappop(infants[now])
        if where[j] != now or j == i: continue
        if highest_rate[now] != -r:
          highest_rate[now] = -r
          heappush(queue, (-r, now, j))
        heappush(infants[now], (r, j))
        break
      else:
        highest_rate[now] = None
      entry(i, k)

    def inquire():
      while True:
        r, k, i = heappop(queue)
        if where[i] != k or r != highest_rate[k]: continue 
        heappush(queue, (r, k, i))
        return r

    for i in range(n):
      a, b = map(int, sys.stdin.readline().split())
      rate[i] = a 
      entry(i, b-1)
    for _ in range(q):
      c, d = map(int, sys.stdin.readline().split())
      transfer(c-1, d-1)
      print(inquire())
    
  def F(): pass 

class ABC171():
  def A():
    c = sys.stdin.readline().rstrip()
    print('A' if c < 'a' else 'a')
  def B():
    n, k, *p = map(int, sys.stdin.read().split())
    print(sum(sorted(p)[:k]))
  def C():
    n = int(sys.stdin.readline().rstrip())
    n -= 1
    l = 1
    while True:
      if n < pow(26, l):
        break 
      n -= pow(26, l)
      l += 1
    res = ''.join([chr(ord('a')+d) for d in NumberTheory.base_convert(n, 26)][::-1])
    res = 'a'*(l-len(res)) + res
    print(res)
  def D():
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    s = sum(a)
    cnt = Counter(a)
    q = int(sys.stdin.readline().rstrip())
    for _ in range(q):
      b, c = map(int, sys.stdin.readline().split())
      s += (c-b)*cnt[b]
      print(s)
      cnt[c] += cnt[b]; cnt[b] = 0
  def E():
    n, *a = map(int, sys.stdin.read().split())
    s = 0
    for x in a: s ^= x 
    b = map(lambda x: x^s, a)
    print(*b, sep=' ')
  def F(): pass 

class ABC172():
  def A(): pass
  def B(): pass
  def C(): pass 
  def D(): pass 
  def E(): pass 
  def F(): pass 

class ABC173():
  def A():
    n = int(sys.stdin.readline().rstrip())
    charge = (n+999)//1000 * 1000 - n
    print(charge)
  def B():
    n, *s = sys.stdin.read().split() 
    c = Counter(s)
    for v in 'AC, WA, TLE, RE'.split(', '):
      print(f'{v} x {c[v]}')
  def C():
    h, w, k = map(int, sys.stdin.readline().split())
    c = [sys.stdin.readline().rstrip() for _ in range(h)]
    tot = 0
    for i in range(1<<h):
      for j in range(1<<w):
        cnt = 0
        for y in range(h):
          for x in range(w):
            if i>>y & 1 or j>>x & 1:
              continue 
            cnt += c[y][x] ==  '#'
        tot += cnt == k
    print(tot)
  def D():
    n, *a = map(int, sys.stdin.read().split())
    a.sort(reverse=True)
    res = a[0] + sum(a[1:1+(n-2)//2])*2 + a[1+(n-2)//2]*(n & 1)
    print(res)
  def E():
    MOD = 10**9+7
    n, k, *a = map(int, sys.stdin.read().split())
    minus = [x for x in a if x < 0]
    plus = [x for x in a if x > 0]
    if len(plus) + len(minus)//2*2 >= k: # plus 
      *minus, = map(abs, minus)
      minus.sort(reverse=True)
      plus.sort(reverse=True)
      cand = []
      if len(minus)&1: minus = minus[:-1]
      for i in range(0, len(minus)-1, 2):
        cand.append(minus[i]*minus[i+1]%MOD)
      if k & 1:
        res = plus[0]
        plus = plus[1:]
      else:
        res = 1
      if len(plus)&1: plus = plus[:-1]
      for i in range(0, len(plus)-1, 2):
        cand.append(plus[i]*plus[i+1]%MOD)
      cand.sort(reverse=True)
      for x in cand[:k//2]:
        res *= x
        res %= MOD 
      print(res)
    elif 0 in a:
      print(0)
    else:
      cand = sorted(map(abs, a))
      res = 1
      for i in range(k):
        res *= cand[i]
        res %= MOD
      res = MOD - res
      print(res)
      pass
  def F(): pass 

class MSolutions2020():
  def A():
    x = int(sys.stdin.readline().rstrip())
    x -= 400
    print(8-x//200)
  def B():
    r, g, b, k = map(int, sys.stdin.read().split())
    while k and g <= r:
      g *= 2
      k -= 1
    while k and b <= g:
      b *= 2
      k -= 1
    print('Yes' if r < g < b else 'No')
  def C():
    n, k, *a = map(int, sys.stdin.read().split())
    for i in range(k, n):
      print('Yes' if a[i] > a[i-k] else 'No')
  def D():
    n, *a = map(int, sys.stdin.read().split())
    a += [-1]
    m = 1000
    s = 0
    for i in range(n):
      if a[i+1] == a[i]: continue 
      elif a[i+1] > a[i]:
        cnt = m//a[i]
        m -= a[i]*cnt 
        s += cnt 
      else:
        m += a[i]*s
        s = 0
    print(m)

  def E(): pass 
  def F(): pass 

if __name__ == '__main__':
  MSolutions2020.D()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    b, h, s, = 0, 0, 1000

    for a in A:
        n_b, n_h = b % a, h + (b // a)
        if s // a == n_h:
            n_b = max(n_b, s % a)
        if s // a > n_h:
            n_h = s // a
            n_b = s % a
        s = max(s, b + h * a)
        b, h = n_b, n_h

    return s

print(main())