Problem:


Score : 300 points

Problem Statement

In a flower bed, there are N flowers, numbered 1,2,......,N. Initially, the heights of all flowers are 0.
You are given a sequence h=\{h_1,h_2,h_3,......\} as input. You would like to change the height of Flower k to h_k for all k (1 \leq  k \leq N), by repeating the following "watering" operation:

Specify integers l and r. Increase the height of Flower x by 1 for all x such that l \leq x \leq r.

Find the minimum number of watering operations required to satisfy the condition.

Constraints

1 \leq N  \leq 100

0 \leq h_i \leq 100

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 h_3 ...... h_N

Output

Print the minimum number of watering operations required to satisfy the condition.

Sample Input 1

4
1 2 2 1

Sample Output 1

2

The minimum number of watering operations required is 2.
One way to achieve it is:

Perform the operation with (l,r)=(1,3).

Perform the operation with (l,r)=(2,4).

Sample Input 2

5
3 1 2 3 1

Sample Output 2

5

Sample Input 3

8
4 23 75 0 23 96 50 100

Sample Output 3

221



Sample input:
4
1 2 2 1


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    h_li = list(map(int, input().split()))
    i = 0
    count = 0
    f = 0
    discount = max(h_li)
    while True:
        if h_li[i] >= discount:
            count += 1
            h_li[i] -= 1
            while i < len(h_li) - 1:
                if h_li[i + 1] >= discount:
                    i += 1
                    h_li[i] -= 1
                else:
                    break
        if i == len(h_li) - 1:
            i = 0
            discount -= 1
            if max(h_li) == 0:
                f = 1
        else:
            i += 1
        if f == 1:
            break
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
h_li = list(map(int, input().split()))
i = 0
count = 0
f = 0
discount = max(h_li)
while True:
    if h_li[i] >= discount:
        count += 1
        h_li[i] -= 1
        while i < len(h_li) - 1:
            if h_li[i + 1] >= discount:
                i += 1
                h_li[i] -= 1
            else:
                break
    if i == len(h_li) - 1:
        i = 0
        discount -= 1
        if max(h_li) == 0:
            f = 1
    else:
        i += 1
    if f == 1:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def get_max_connected_index(arr):
  arr_len = len(arr)
  for check_len in range(arr_len, 0, -1):
    for begin_i in range(arr_len-check_len+1):
      end_i = begin_i+check_len-1
      if arr[begin_i:end_i+1].all():
        return begin_i, end_i
      
def shorten_height(arr):
  begin_i, end_i = get_max_connected_index(arr)
  height = np.min(arr[begin_i:end_i+1])
  arr[begin_i:end_i+1] -= height
  return arr, height
      
if __name__ == "__main__":
  N = int(input())
  flower_str = input()
  flower = [int(h) for h in flower_str.split()]
  flower = np.array(flower)
  times = 0
  while flower.any():
    flower, height = shorten_height(flower)
    times += height
  print(times)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
h=list(map(int,input().split()))
ans=0
while any(h)==True:
    flag=0
    for i in range(n-1):
        if h[i]>0:
            h[i]-=1
            flag=1
        else:
            if flag==1:
                ans+=1
                flag=0
        if i==n-2:
            if h[n-1]>0:
                h[n-1]-=1
                ans+=1
            else:
                if flag==1:
                    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
h=list(map(int,input().split()))
ans=0
while any(h)==True:
    flag=0
    for i in range(n-1):
        if h[i]>0:
            h[i]-=1
            flag=1
        else:
            if flag==1:
                ans+=1
                flag=0
        if i==n-2:
            if h[n-1]>0:
                h[n-1]-=1
                ans+=1
                break
            else:
                if h[i]>-1 and flag==1:
                    ans+=1
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = list(map(int, input().split()))
res = 0
pre_left = 0
while True:
  Max = 0
  w = 0
  left = 0
  right = n
  flag = False
  for i in range(n):
    if lst[i] > 0 and not flag:
      if i == n-1:
        if Max:
          break
      w = 1
      pre_left = left
      left = i
      flag = True
      if i == n-1:
        right = n
        Max = 1
    elif lst[i] > 0 and flag:
      w += 1
      if i == n-1:
        if Max < w:
          Max = w
          right = n
        else:
          left = pre_left
    elif lst[i] <= 0 and flag:
      if Max < w:
        Max = w
        right = i
        flag = False
      else:
        left = pre_left
      w = 0
  if w == n:
    Max = n
  if Max == 0:
    break
  d = min(lst[left:right])
  for i in range(left, right):
    lst[i] -= d
  res += d
      
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))+[0]
ans=0

while 1:
  for i in range(n):
    if A[i]>0:
      A[i]-=1
      if A[i+1]==0:
        ans+=1
  if A==[0 for i in range(n)]:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = 0
n = int(input())
h = [int(i) for i in input().split()]
while True:
  if h.count(0)==n:
    break
  zero = [i for i, x in enumerate(h) if x==0]
  if zero==[]:
    s = 0
    e = n-1
  elif len(zero)==1:
    s = 0
    e = zero[0]
  else:
    s = zero[0]
    e = zero[1]
  for j in range(s, e+1):
    h[j] -= 1
  num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
h=list(map(int,input().split()))
a=0
for i in range(1,max(h)+1):
    s=0
    while s<n:
        if h[s]>=i:
            a+=1
            while s<n and h[s]>=i:
                s+=1
    s+=1
print(a)

Submission status: Time Limit Exceeded

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

ans = 0
given_water = False
while True:
  is_continuous = False
  for i in range(N):
    if h[i] > 0:
      if is_continuous is False:
        ans += 1
        is_continuous = True
      h[i] -= 1
      given_water = True
    else: # h[i] == 0
      is_continuous = False
  if given_water is False:
    break
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
h=list(map(int,input().split()))
cnt=0
l=[]
while set(h)!={0}:
  if h.count(0)==0:
    cnt+=min(h)
    for i in range(len(h)):
      h[i]=h[i]-min(h)
  else:
    for i in range(len(h)):      
      if h[i]==0:
        l.append(h[i])
      else:
        l.append(h[i])
        continue
      cnt+=min(l)
      l=[]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
h = list(int(i) for i in input().split())
count = 0
while not all(i==0 for i in h):
    if 0 in h:
        zero_index = [i for i,x in enumerate(h) if x==0]
        for i in range(len(zero_index)):
            if i==0:
                if not all(h[j]==0 for j in range(zero_index[i])):
                    for j in range(zero_index[i]):
                        h[j] -= 1
                    count += 1
            elif i==len(zero_index)-1 and not zero_index[i]==n-1:
                if not all(h[j]==0 for j in range(zero_index[i]+1,n)):
                    for j in range(zero_index[i]+1,n):
                        h[j] -= 1
                    count += 1
            else:
                if not all(h[j]==0 for j in range(zero_index[i-1]+1,zero_index[i])):
                    for j in range(zero_index[i-1]+1, zero_index[i]):
                        h[j] -= 1
                    count += 1
    else:
        for i in range(n):
            h[i] -=1
        count += 1
print(count)

Submission status: Accepted

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

def solve(heights, beg, end) -> int:
    if beg >= end: return 0
    try:
        idx = beg + heights[beg:end].index(0)
        return  solve(heights, beg, idx) + solve(heights, idx+1, end)
    except ValueError:
        pass
    
    minh = min(heights[beg:end])
    for i in range(beg, end):
        heights[i] -= minh
    return minh + solve(heights, beg, end)

cnt = solve(heights, 0, len(heights))
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(max(a)):
    cnt = 1 if a[0] - i >= 1 else 0
    for j in range(1, n):
        if a[j-1] - i < 1 and a[j] - i >= 1:
            cnt += 1
    ans += cnt
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0 for _ in range(n)]

ans=0

while a!=b:
  ch=0
  for i in range(n):
    if b[i]+1<=a[i]:
      b[i]+=1
      ch+=1
    elif b[i]+1>a[i] and ch>0:
      ch=0
      ans+=1
      
    if ch>0 and i==n-1:
      ans+=1
      
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int, input().split()))
hlst = [0]
for h in lst:
  if hlst[-1] != h:
    hlst.append(h)
hlst.append(0)
ans = 0
l = len(hlst)
for i in range(1, l - 1):
  if hlst[i - 1] < hlst[i] and hlst[i] > hlst[i + 1]:
    ans += hlst[i]
  elif hlst[i - 1] > hlst[i] and hlst[i] < hlst[i + 1]:
    ans -= hlst[i]
print(ans)

Submission status: Accepted

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

cnt=0

while 1:
    for i in range(len(h)-1,0,-1):
        if h[i]==h[i-1]:
            h.pop(i)

    if len(h)==1:
        break
    # mp:水やりポイント
    mp = h.index(max(h))

    if mp==0:
        cnt += h[mp] - h[mp+1]
    elif mp==len(h)-1:
        cnt += h[mp] - h[mp-1]
    else:
        cnt += h[mp] - max(h[mp-1],h[mp+1])

    h.pop(mp)

print(cnt+h[0])

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
hl = LI()
# count = 0

# len_h = len(hl)

# def m1(n):
#     if n > 0:
#         n = n - 1
#     else:
#         n = 0
#     return n

# max_hana = max(hl)
# if max_hana == 0:
#     print(0)
#     sys.exit()

# for i in range(max_hana):
#     for j in range(len_h):
#         if j == 0:
#             if hl[j] > 0:
#                 count += 1
#         else:
#             if hl[j] > 0 and hl[j-1] == 0:
#                 count += 1
#             elif hl[j] > 0 and hl[j-1] == 0:
#                 count += 1
#     hl = list(map(m1, hl))

# print(count)

######################
# 隣との差分を考えたほうが早い

# 1    2    4    2    1    0      計4
#   1    2    0    0     0

ans = hl[0]
for i in range(1, n):
    ans += max(0, hl[i] - hl[i - 1])
print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
hl = LI()
wl = []
count = 0

len_h = len(hl)

def m1(n):
    if n > 0:
        n = n - 1
    else:
        n = 0
    return n

max_hana = max(hl)
if max_hana == 0:
    print(0)
    sys.exit()

for i in range(max_hana):
    for j in range(len_h):
        if j == 0:
            if hl[j] > 0:
                count += 1
        else:
            if hl[j] > 0 and hl[j-1] == 0:
                count += 1
            elif hl[j] > 0 and hl[j-1] == 0:
                count += 1
    hl = list(map(m1, hl))

print(count)

Submission status: Accepted

Solution code:
a = int(input())
b = list(map(int,input().split()))
b.append(0)
ans = 0
while not max(b) == 0:
  for i in range(len(b)):
    if b[i] > 0 and b[i+1] <= 0:
      ans += 1
  b = list(map(lambda x: x-1,b))
print(ans)

Submission status: Accepted

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

cnt = 0

a = 0
for i in range(n-1):
  if h[i+1] < h[i]:
    cnt += h[i]-a
    a = h[i+1]
cnt += h[-1]-a
print (cnt)

Submission status: Accepted

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

ans = 0

for i in range(max(h)):
    if h[0] == 0:
        zeroFlag = True
        for j in range(0, n):
            if h[j] == 0:
                zeroFlag = True
            if h[j] != 0 and zeroFlag == True:
                ans += 1
                zeroFlag = False
            if h[j] > 0:
                h[j] -= 1
    else:
        numFlag = True
        for j in range(0, n):
            if h[j] == 0:
                numFlag = True
            if h[j] != 0 and numFlag == True:
                ans += 1
                numFlag = False
            if h[j] > 0:
                h[j] -= 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
hh = list(map(int, input().split()))
cnt = 0

while hh.count(0) != n:
  a = [i for i, x in enumerate(hh) if x == 0]
  
  if a != []:
    for i in range(len(a)-1):
      if a[i]+1 != a[i+1]:
        for j in range(a[i]+1 , a[i+1]):               
          hh[j] -= 1
        cnt += 1
        
    if a[0] != 0:       
      for j in range(a[0]):
        hh[j] -= 1
      cnt +=1
    
    if a[-1] != n-1:
      for j in range(a[-1]+1, n):      
        hh[j] -= 1
      cnt += 1
        
  else:
    for i in range(n):
      hh[i] -= 1
    cnt += 1
             
print(cnt)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
import collections

def main():
    n = int(input())
    h = input_list()
    count = 0
    while True:
        if list(set(h)) == [0]:
            break
        count += 1
        f = False
        for i, v in enumerate(h):
            if v == 0:
                if f:
                    break
            if v > 0:
                h[i] -= 1
                f = True
    print(count)


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
g = [0]*n
ans = 0
l = 0
while not h == g:
  if not g[l] == h[l]:
    r = l+1
    while r <= n-1 and not g[r] == h[r]:
      r += 1
    #lは水やりが必要な左端、rはlより右で水やりが必要ない左端
    for i in range(l,r):
      g[i] += 1
    ans += 1
  if g[l] == h[l]:
    l += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    # n, m = map(int, input().split())
    h = list(map(int, input().split()))
    # s = input()
    # h = [int(input()) for _ in range(n)]

    count = 0
    h.append(0)
    for j in range(max(h)):
        for i in range(n):
            if h[i] != 0 and h[i+1] == 0:
                count += 1
            if h[i] != 0:
                h[i] -= 1
    
    print(count)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
# import re
import collections
import bisect
import math
import fractions
import collections
import itertools
from functools import reduce

def main():
    n = int(input())
    h = list(input_list())
    count = 0
    while True:
        if list(set(h)) == [0]:
            break
        flag = False
        count += 1
        for i, v in enumerate(h):
            if v != 0:
                flag = True
                h[i] -= 1
            else:
                if flag:
                    break
    print(count)

def minus(numbers):
    for i, n in enumerate(numbers):
        if n == 0:
            break
        numbers[i] -= 1
    return numbers


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
h=[0]+list(map(int,input().split()))+[0]
ma=0
mi=float('inf')
ans=0
for i in range(n+1):
  if h[i]<=h[i+1]:
    ma=max(ma,h[i+1])
    mi=min(mi,h[i])
  else:
    ans+=ma-mi
    ma=h[i+1]
    mi=h[i+1]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 15 00:43:39 2020

@author: liang
"""

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

ans = 0
for i in range(max(H)):
    count = 0
    flag = False
    for j in range(N):
        if i < H[j]:
            if flag == False:
                count += 1
            flag = True
        else:
            flag = False
    ans += count
print(ans)

Submission status: Accepted

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

def solve(l):
    if len(l) == 1:
        return l[0]

    min_l = min(l)
    ans = min_l
    new_l = []
    for i in l:
        i -= min_l
        if i == 0:
            if len(new_l) > 0:
                    ans += solve(new_l)
                    new_l = []
        else:
            new_l.append(i)
    if len(new_l) > 0:
        ans += solve(new_l)

    return ans

print(solve(a))

Submission status: Accepted

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

res=0
temp = 0
for i in range(n):
    if al[i] >=temp:
        res += al[i]-temp
        temp = al[i]
    else:
        temp = al[i]

print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
h = na()
ans = h[0]
for i in range(1,n):
  ans += max(0, h[i]-h[i-1])
print(ans)

Submission status: Accepted

Solution code:
def dfs(left,right):
    if right-left==1:
        return h[left]
    elif right-left<=0:
        return 0
    else:
        ret=min(h[left:right])
        k=0
        for i in range(left,right):
            h[i]-=ret
            if h[i]==0:
                k=i
        ret+=dfs(left,k)
        ret+=dfs(k+1,right)
        return ret

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

print(dfs(0,N))

Submission status: Accepted

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

def grouping(v):
    #隣接する人同士のグルーピング
    groups = []
    tmp = 0
    zeros = 0
    for n in v:
        if n == 1:
            if zeros != 0:#直前まで０だったとき
                groups.append(zeros)
                zeros = 0#リセット
            tmp += 1
        elif n == 0:
            if tmp != 0:#直前まで１だったとき
                groups.append(tmp)
                tmp = 0#リセット
            zeros -= 1
    
    #終端の処理
    if tmp != 0:
        groups.append(tmp)
    if zeros != 0:
        groups.append(zeros)
    
    groups = [1 if x > 0 else 0 for x in groups]
    return groups

ans = 0
for i in range(max(H)):
    H = list(map(lambda x:x-1, H))
    vector = [1 if x >= 0 else 0 for x in H]
    ans += sum(grouping(vector))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
H = list(map(int, input().split()))
ans = H[0]
for i in range(N-1):
    if H[i] < H[i+1]:
        ans += H[i+1]-H[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
H = list(map(int, input().split()))
ans = H[0]
for i in range(N-1):
    if H[i] < H[i+1]:
        ans += H[i+1]-H[i]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N= int(input())
h = list(map(int,input().split()))
s=h[0]
for i in range(N-1):
    if h[i]<=h[i+1]:
        s=s+h[i+1]-h[i]
        #print('+',i+1,s)
print(s)

Submission status: Accepted

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

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


def need(L):
    if L == [] or max(L) == 0:
        return 0
    if min(L) > 0:
        l = [L[i]-1 for i in range(len(L))]
        return need(l)+1
    else:
        i = L.index(0)
        l = L[:i]
        m = L[i+1:]
        return need(l)+need(m)


print(need(H))

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int,input().split()))
ans = h[0]
for i in range(1,N):
    if h[i] > h[i-1]:
        ans += h[i] - h[i-1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce

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

    ans = 0
    while h != [0] * N:
        if h[0] != 0:
            ans += 1
        for i in range(1, N):
            if h[i - 1] == 0 and h[i] != 0:
                ans += 1
        for i in range(N):
            if h[i] > 0:
                h[i] -= 1
    print(ans)


def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def grand_garden(n, h):

    count = 0
    j = 100
    for i in range(n):
        if h[i] != 0:
            j = i
            break
    if j == 100:
        return count

    while h[j] != 0:
        l = j  # 左はしきめる
        r = l  # 動く右はし
        for k in range(l, n):  # 右端はZeroでないかぎりのばす、ゼロになる最初の位置を取得、すべてゼロでなければ配列の右端
            if k == n-1 and h[k] != 0:
                r = n
            elif h[k] == 0:
                r = k
                break

        min_val = min(h[l:r])  # 右はしから左はしまでの最小値を取得
        for x in range(l, r):  # 各要素から共通の最小値を差し引く
            h[x] -= min_val
        count += min_val  # 最小値分カウントを追加
        if h[j] == 0:  # もしも左端がゼロだったらゼロでない最初の位置へ移動
            for t in range(j, n):
                if h[t] != 0:
                    j = t
                    break

        if j >= n:
            break
    return count


def main():
    n = int(input())
    h = list(map(int, input().split()))

    answer = grand_garden(n, h)
    print(answer)


'''
数列に0が含まれない最大の幅を取得(0ではない最小の左から最大の右でもよいのか)
その幅に含まれる要素高さを1ずつへらす、
count +=1

0 <= l,r <= n-1
while True:
    if h[i] == 0:
        l += 1
        i += 1
        continue
        if l >= n:
            break

   for i in range(n):
        if h[i] != 0:
            l = i
            r = l
            for j in range(l, n):
                if h[j] != 0:
                    r += 1
            for k in range(l, r):
                h[k] -= min(h[l:r])
#            if h[l] != 0:
#                i -= 1
            count += 1


'''


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, hi):
    ans = 0
    for i in range(max(hi)):
        flg = False
        for n in range(N):
            if hi[n] != 0:
                if not flg:
                    flg = True
                    ans += 1
                hi[n] -= 1
            else:
                flg = False
    print(ans)


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    hi = [int(i) for i in input().split()]
    # Bi = [int(i) for i in input().split()]
    # ABi = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, hi)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int, input().split()))
max_ = 100*50
h = [0] + h + [0]
cnt = 0
if max(h) == 0:
    print(0)
    exit()
for _ in range(max_):
    for i in range(1, N+1):
        if h[i] == 0 and h[i-1] != 0:
            cnt += 1
            break
        if h[i] > 0:
            h[i] -= 1
            if h[i] == 0 and h[i+1] == 0:
                cnt += 1
                break
        if i == N:
            cnt += 1
            break
    if sum(h) == 0:
        break
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
*h,=map(int, input().split())
import numpy as np
h=np.array(h)

def rec(hh):
    if len(hh)==0:
        return 0
    if len(hh)==1:
        return hh[0]
    i=np.argmin(hh)
    res=hh[i]
    l=rec(hh[:i]-hh[i])
    r=rec(hh[i+1:]-hh[i])
    return res+l+r
print(rec(h))

Submission status: Accepted

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

def dfs(a):
  if not a:
    return 0
  cnt = 0
  while True:
    if 0 in a:
      z = [i for i,x in enumerate(a) if x==0]
      cnt += dfs(a[:z[0]])
      for i in range(1,len(z)):
        cnt += dfs(a[z[i-1]+1:z[i]])
      cnt += dfs(a[z[-1]+1:])
      return cnt
    else:
      a = [x-1 for x in a]
      cnt += 1

print(dfs(h))

Submission status: Accepted

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

cnt = 0
while True:
    zero_ind = []
    for i in range(n+2):
        if h[i] == 0:
            zero_ind.append(i)

    start, end = [], []
    for i in range(len(zero_ind)-1):
        if zero_ind[i+1] - zero_ind[i] > 1:
            start.append(zero_ind[i]+1)
            end.append(zero_ind[i+1])

    for s, e in zip(start, end):
        for i in range(s, e):
            h[i] -= 1
        cnt += 1

    if h.count(0) == n+2:
        break
print(cnt)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()	
	al=lin()
	ch=0
	ret=0
	for h in al:
		ret += max(h-ch, 0)
		ch = h
	return ret
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
h.append(101)
ans = 0
start = 0
i = 0
while sum(h[:n])!=0:
    if h[i]!=0:
        h[i] -= 1
    if h[i]==0:
        start = i+1    
    if h[i]>=h[i+1] or i==n-1:
        ans += 1
        i = start
        continue
    i += 1
print(ans)

Submission status: Accepted

Solution code:

url = "https://atcoder.jp//contests/abc116/tasks/abc116_c"

def main():
    input()
    h = list(map(int, input().split()))
    h.append(0)
    count = 0
    def start_end(h):
        s_e = [-1,-1]
        for i in range(len(h)):
            if h[i] != 0 and s_e[0] == -1:
                s_e[0] = i
            elif h[i] == 0 and s_e[0] != -1:
                s_e[1] = i
                break
        return s_e
    while True:
        s_e = start_end(h)
        if s_e[0] == -1 and s_e[1] == -1:
            print(count)
            exit()
        min_h = min(h[s_e[0]:s_e[1]])
        for i in range(s_e[0], s_e[1]):
            h[i] -= min_h
        count += min_h




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)

N,H = ilint()
H = [0]+H[:]
H = [-(H[i+1]-H[i]) for i in range(N)]+[INF]
ans = 0
for l in range(N):
    while H[l]<0:
        r = 0
        while r<N and H[r]<=0:
            r += 1
        tmp = min(-H[l],H[r])
        ans += tmp
        H[l] += tmp
        H[r] -= tmp
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
hs = list(map(int,input().split()))
c = 0
while True:
    pmi = 101
    start = 0
    flag = True
    for i in range(N):
        if hs[i] == 0:
            if pmi == 101:
                start += 1
                continue
            for j in range(start,i):
                hs[j] -= pmi
            #print(hs)
            c += pmi
            start = i+1
            pmi = 101
        else:
            flag = False
            pmi = min(pmi, hs[i])
    if flag:
        break
    else:
        if pmi != 101:
            for i in range(start,N):
                hs[i] -= pmi
            c += pmi
print(c)

Submission status: Accepted

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

count = 0

while h != [0]*(n+1):
    for i in range(len(h)):
        if h[i] != 0:
            break

    for j in range(i, len(h)+1):
        if h[j] == 0:
            break

    for x in range(i, j):
        h[x] -= 1

    count += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int, input().split()))
cnt=0
for i in range(n):
    while h[i] != 0:
        cnt+=1
        for j in range(i, n):
            if h[j] != 0:
                h[j] = h[j] - 1
            elif h[j] == 0:
                break
print(cnt)

Submission status: Accepted

Solution code:
N=int(input())

h=list(map(int,input().split()))
sw=True
temp=0
ans=0
for i in range(N-1):
    if sw==True:
        if h[i]>h[i+1]:
            ans+=h[i]-temp
            sw=False
    else:
        if h[i]<h[i+1]:
            temp=h[i]
            sw=True
if sw==True:
    ans+=h[N-1]-temp

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
tmp = [0 for i in range(n)]
ans = 0
right = 0
left = n-1

while tmp != h:
    for i in range(n):
        if tmp[i] != h[i]:
            right = i
            left = i
            break
    for i in range(i+1,n):
        if tmp[i] == h[i]:
            left = i-1
            break
        elif i == n-1 and tmp[n-1] != h[n-1]:
            left = n-1
            break
    for i in range(right,left+1):
        tmp[i] += 1
    ans += 1
#    print(right,left,ans)
#    print(tmp)

print(ans)