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

Solution code:
def mizuyari2(row):
    cnt = 0
    _min = min(row)
    cnt += _min
    row2 = [i - _min for i in row]

    res = [[]]
    for e in row2:
        if e != 0:
            res[-1].append(e)
        else:
            res.append([])

    return cnt, res


def mizuyari(ll):
    cnt = 0

    for l in ll:
        if l:
            cnt2, hs = mizuyari2(l)
            # print(cnt2, hs)
            cnt += cnt2
            cnt += mizuyari(hs)
    return cnt


def main2():
    n = int(input())
    hs = [int(i) for i in input().split()]
    hs = [hs]
    cnt = mizuyari(hs)
    print(cnt)


if __name__ == '__main__':
    main2()

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int, input().split()))
def func(n):
    return n - 1
ans = 0
flag = True
flag2 = False
while True:
    for i in h:
        if i > 0:
            if flag2 == False:
                ans += 1
            flag = False
            flag2 = True
        else:
            flag2 = False
    if flag:
        break
    h = list(map(func, h))
    flag = True
    flag2 = False
    #print(h)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 20 20:52:23 2019

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

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

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')
"""
N = int(input())

h = [0]*N
h[:] = map(int, input().split())

h = np.array(h)

cnt = 0
while np.sum(h ==0) != N:
    if np.sum(h ==0) == 0:        
        h = h-1
        cnt +=1
    else:
        r=N-1
        for n in range(N-1):
            if h[n] == 0 and h[n+1] !=0:
                l = n+1
            elif h[0] != 0:
                l = 0
            else:
                pass
            if h[n] != 0 and h[n+1] == 0:
                r = n
                break
        for x in range(l, r+1):
            h[x] = h[x] -1
        cnt +=1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
h_list = np.array(list(map(int, input().split())))

def index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
  
num=0

def func(h_list):
    #print(h_list)
    global num
    num += min(h_list)
    #print(num)
    h_list = h_list - min(h_list)
    #print(h_list)
    index_list=index_multi(h_list,0)
    #print(index_list,"index")
    for i in range(len(index_list)):        
        if i ==0:
            if not index_list[i]==0:
                func(h_list[:index_list[i]])
                #print(h_list[:index_list[i]])
        else:
            if not index_list[i-1]+1 == index_list[i]:
                func(h_list[index_list[i-1]+1:index_list[i]])
                #print((h_list[index_list[i-1]+1:index_list[i]]))
                
        if i == len(index_list)-1:
            if not index_list[i]==len(h_list)-1:
                func(h_list[index_list[i]+1:])
                #print(h_list[index_list[i]+1:])

func(h_list)
print(num)

Submission status: Accepted

Solution code:
n=int(input())
h=list(map(int, input().split()))
ans=0
while max(h)!=0:
  l=0 
  for i, hi in enumerate(h):
    if hi==0 and l!=i:
      r=i
      n=min(h[l:r])
      h=[hi-n if i>=l and i<r else hi for i, hi in enumerate(h) ]
      ans+=n
      l=min(i+1,len(h)-1)

    elif hi==0 and l==i and i!=len(h)-1:
      l+=1

  else:
    r=i+1
    n=min(h[l:r])
    h=[hi-n if i>=l and i<=r else hi for i, hi in enumerate(h) ]
    ans+=n
    l=i+1

print(ans)

Submission status: Accepted

Solution code:
# C
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
N = getInt()
h = getIntList()
count = 0
def water(r,l):
    global count
    #print(r,l,h,count)#
    mn = min(h[r:l])
    count += mn
    for i in range(r,l):
        h[i] -= mn
    i = r
    #print(r,l,h,count)#
    while i<l:
        #print('i',i)#
        if h[i]>0:
            j = i+1
            #print('j',j)#
            while j<=l:
                #print(j)#
                if j>=l or h[j]==0:
                    water(i,j)
                    break
                j += 1
            i = j
        i += 1
water(0,N)
print(count)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
times=0

while True:
        i=0
        mins=9999999999
        f=False
        start=0
        while i<n:
                if l[i]>0:
                        if f==False:
                                f=True
                                start=i
                        mins=min(mins,l[i])
                elif f:
                        times+=mins
                        j=start
                        while j<i:
                                l[j]-=mins
                                j+=1
                        break
                i+=1
        if i>=n and f==True:
                times+=mins
                j=start
                while j<n:
                        l[j]-=mins
                        j+=1
                
        if f==False:
                break
print(times)

Submission status: Accepted

Solution code:
N=int(input())
F=list(map(int,input().split()))
s=0
ans=0
while True:
  while F[s]==0:
    s+=1
    if s==N:
      break
  if s==N:
    break
  t=s
  while F[t]!=0:
    t+=1
    if t==N:
      break
  m=min(F[s:t])
  for j in range(s,t):
    F[j]-=m
  ans+=m
print(ans)

Submission status: Accepted

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

ans_nums = [0]*n
start_i = 0
goal_i = 0
count = 0

while goal_nums != ans_nums:
    #水のあげ始めを決定
    for i in range(n):
        if goal_nums[i] != ans_nums[i]:
            start_i = i
            break
    #水のあげ終わりを決定
    for j in range(start_i, n):
        if goal_nums[j] == ans_nums[j]:
            goal_i = j
            break
        if j == n-1:
                goal_i = n

    #指定箇所に水を上げる
    for k in range(start_i, goal_i):
        ans_nums[k] += 1
    count += 1

print(count)

Submission status: Accepted

Solution code:
n=int(input())
h=[int(i) for i in input().split()]

ans=0

while sum(h)!=0:
    k=ans
    for i in range(n):
        if i==0 and h[i]!=0:
            ans+=1
        elif h[i]!=0 and h[i-1]==0:
            ans+=1
    if k==ans:
        ans+=1
        
    for i in range(n):
        if h[i]!=0:
            h[i]-=1


        
print(ans)

Submission status: Accepted

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

import numpy as np

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

counter=0
while(len(H[H>0]) >0):
  starti=0
  endi=0
  for i in range(N):
    if H[i]>0:
      starti=i
      break
  for i in range(starti, N):
    if H[i]>0:
      endi=i
    else:
      break
  H[starti:endi+1]-=1
  counter+=1
  
print(counter)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0] * n
ans = 0
while sum(b) < sum(a):
  c = 0
  while c < n:
    tmp = []
    while a[c] !=  b[c]:
      tmp.append(c)
      c+= 1
      if c >= n:
        break
    if tmp:
      ans += 1
    for i in tmp:
        b[i] += 1
    c += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2000)
import numpy as np

def solve(h):
  if len(h) < 1:
    return 0
  mizuyari = min(h)
  h -= mizuyari
  zero_index = np.array(np.where(h == 0)).flatten()
  starts = np.insert(zero_index+1,0, 0)
  ends = np.insert(zero_index,len(zero_index),len(h))
  for s, e in zip(starts,ends):
    mizuyari += solve(h[s:e])
  return mizuyari

N = int(raw_input())
H = np.array(map(int, raw_input().split()),dtype=np.int)
print solve(H)

Submission status: Accepted

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

cnt = 0
while a:
    for i in range(len(a)):
        if a[0] == 0:
            a.pop(0)
            break
        else:
            a[i] -= 1
            if i != len(a)-1:
                if a[i+1] == 0:
                    cnt += 1
                    break
            if i == len(a)-1:
                cnt += 1

print(cnt)

Submission status: Accepted

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

# m=min(h)
# for i in range(N):
# 	h[i]-=m
# ans=m
ans=0
def func(a):
	global ans

	if len(a)==0 or a==[0]:
		return
	
	m=min(a)
	for i in range(len(a)):
		a[i]-=m
	ans+=m


	for i in range(len(a)):
		if a[i]==0:
			break
	p=i
	tmp1=a[0:p]
	tmp2=a[p+1:N]


	func(tmp1)
	func(tmp2)

func(h)

print(ans)



# j=0

# while True:
# 	tmp=[]
# 	tmp.append(h[j])
# 	for i in range(j+1,N):
# 		if i>=1 and i+1<=N-1:
# 			if h[i]<h[i-1] and h[i]<h[i+1]:
# 				break
# 		tmp.append(h[i])
# 	j=i
# 	ans+=max(tmp)
# 	print(j, tmp, ans)
# 	if j>=N-1:
# 		break
	
# print(ans)

Submission status: Accepted

Solution code:
n=int(input())
h=[int(i) for i in 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:
import copy


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

i=0
leftH = copy.deepcopy(h)
while max(leftH) > 0:
    flag = False
    for j in range(N):
        if leftH[j] > 0:
            leftH[j] -= 1
            if flag == False:
                i += 1
            flag = True
        elif flag == True:
            flag = False
print(i)

Submission status: Accepted

Solution code:

ans = 0

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

    all_lst=[lst]
    make_lst(all_lst)
    print(ans)


def minus(lst):
    m = min(lst)
    global ans
    ans+=m
    return list(map(lambda x: x-m, lst))

def make_lst(all_lst):
    #tmp =0

    for lst in all_lst:
        #tmp +=1
        #if tmp >= 20:
        #    print(all_lst)
        #    exit()

        if lst != []:
            lst = minus(lst)
        lst = " ".join(map(str,lst)).split(" 0")
        for i in lst:
            if i.split() != []:
                sp_list = list(map(int,i.split()))
                if 0 in sp_list:
                    sp_list.remove(0)

                all_lst.append(sp_list)


if __name__ == "__main__":
        main()

Submission status: Accepted

Solution code:
n=int(input())
h=[int(i) for i in input().split()]
h.append(0)
#print(n,h)

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

Submission status: Accepted

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

sep = []
for i in range(1, N - 1):
    if H[i] < H[i-1] and H[i] < H[i+1]:
        sep.append(i)

stack = []
prev = -1
a = 0
for i, h in enumerate(H):
    if h == 0 and prev != 0:
        if H[a:i] != []:
            stack.append(H[a:i])
        a = i
    elif h != 0 and prev == 0:
        a = i
    prev = h
if H[a:] != []:
    stack.append(H[a:])

count = 0
while stack:
    lst = stack.pop()
    if min(lst) == 0:
        continue
    m = min(lst)
    count += m
    lst = [l-m for l in lst]
    a = 0
    prev = -1
    for i, h in enumerate(lst):
        if h == 0 and prev != 0:
            if lst[a:i] != []:
                stack.append(lst[a:i])
            a = i
        elif h != 0 and prev == 0:
            a = i
        prev = h
    if lst[a:] != []:
        stack.append(lst[a:])

print(count)

Submission status: Accepted

Solution code:
def minus_one(list_):
    return [i-1 if i > 0 else 0 for i in list_]


N = int(input())
h_list = list(map(int,input().split()))
h_list.append(0)
end_flg = False
time = 0

while end_flg == False:
    for i in range(0,len(h_list)-1):
        if not h_list[i] == 0 and h_list[i+1] == 0:
            time += 1
    if all([i==0 for i in h_list]):
        end_flg = True
    h_list = minus_one(h_list)

print(time)

Submission status: Accepted

Solution code:

def r(h):
    if all([0 == x for x in h]):
        return 0

    c = 0
    if 0 in h:
        hl = []
        if h.count(0):
            while h.count(0):
                v = h.index(0)
                hl.append(h[0:v])
                del h[0:v+1]
            hl.append(h)
        for hlx in hl:
            c += r(hlx)
    else:
        while 0 not in h:
            h = [x - 1 for x in h]
            c += 1
        c += r(h)

    return c


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

    print(r(h))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
inputs = [int(i) for i in input().split()]

ans = 0
tmp = 0
for i in range(1, N):
    if inputs[i-1] <= inputs[i]:
        pass
    else:
        ans += (inputs[i-1] - tmp)
        tmp = inputs[i]

if inputs[-1] > tmp:
    ans += inputs[-1] - tmp

print(ans)

Submission status: Accepted

Solution code:
c=0
def ans(a):
    global c
    b=a.index(min(a))
    f=min(a)
    a=[i-f for i in a]
    c+=f
    if a[:b]:ans(a[:b])
    if a[b+1:]:ans(a[b+1:])
n=input()
d=list(map(int, input().split()))
ans(d)
print(c)

Submission status: Accepted

Solution code:
n = int(input())
flowers = list(map(int, input().split()))
flowers.append(0)
cnt = 0
if(all([x<=0 for x in flowers])): print(0)
else: 
    for i in range(sum(flowers)+1):
        #print(i)
        if(all([x<=0 for x in flowers])): break
        #print(flowers, i, cnt)
        for j in range(n-2):
            if(flowers[j] > 0 and flowers[j+1] <= 0 and any([x>0 for x in flowers[j+2:]])): cnt+=1
        flowers = list(map(lambda x: (x-1), flowers))
    print(i + cnt)

Submission status: Accepted

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

ans = 0
while True:
    zf = True
    zc = 0

    for i, v in enumerate(h):
        if v <= 0:
            zf = True
            zc = zc + 1
        elif v > 0 and zf:
            ans = ans + 1
            zf = False

        h[i] = h[i] - 1

    if zc == len(h):
        break

print(ans)

Submission status: Accepted

Solution code:
def q1():
    a,b,c = map(int, input().split(" "))
    r = int(a*b/2)
    print(r)

def q2():
    def f(n):
        if n%2 == 0:
            return n//2
        else:
            return 3*n+1
    def solver(v):
        ary = []
        for i in range(10**6):
            if i == 0:
                ary.append(v)
            else:
                v = f(ary[-1])
                if v in ary:
                    return i+1
                else:
                    ary.append(v)
    s = int(input())
    print(solver(s))


"""
1. 最低値を数える (1)
2. 配列全体から最低値を減算する
3. 0で配列を分割する
4. 分割した配列に1～の処理を行う
5. 配列の長さが0になったら終わる
6. 全ての最低値を足した値が答え
"""
n = int(input())
h = list(map(int, input().split(" ")))

def water(ary):
    # 5
    if len(ary) == 0:
        return 0
    elif len(ary) == 1:
        return ary[0]

    # 1
    m = min(ary)
    #print("min = %d" % m)
    # 2
    new_ary = list(map(lambda x:x-m, ary))
    # 3
    tmp = []
    multi_ary = []
    for n in new_ary:
        if n != 0:
            tmp.append(n)
        else:
            multi_ary.append(tmp)
            tmp = []
    else:
        multi_ary.append(tmp)
    #print("%s -> %s -> %s" % (ary, new_ary, multi_ary))
    # 4
    cnt = sum(map(water, multi_ary))
    # 6
    #print("%d + %d" % (cnt,m))
    return cnt +m

print(water(h))

Submission status: Accepted

Solution code:
n = int(input()) #整数
h = [int(i) for i in input().split() ]

i = 0
l = [0 for i in range(n)]
ans = 0
while h != l:
    ans += 1
    start = False
    for i in range(n):
        if start == False:
            if h[i] > 0:
                start = True
                h[i] -= 1
        else:
            if h[i] > 0:
                h[i] -= 1
            elif h[i]== 0:
                break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
l = list(map(int, input().split()))


L = [l]
cnt = 0
while L:

    l = L.pop()
    if len(l) == 0:
        pass
    elif len(l) == 1:
        cnt += l[0]
    else:
        min_l = min(l)
        l = [s for s in map(lambda x: x-min_l, l)]
        cnt += min_l
        len_l = len(l)
        i = 0
        temp = []
        while i != len_l:

            if l[i] != 0:
                temp.append(l[i])
            else:
                L.append(temp)
                temp = []
            i += 1
        if len(temp) != 0:
            L.append(temp)

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
flowers = list(map(int, input().split()))
flowers.append(0)
ans=0

while(flowers!=[0]*(N+1)):
  for i in range(N+1):
    if flowers[i] != 0:
      index = i
      break
  
  mmm=flowers[index]
  num = mmm
  for i in range(index, N+1):
    if flowers[i] >= num:
      num = flowers[i]
    else:
      mmm = num-flowers[i]
      stop = i
      break
      
  ans += mmm
  for i in range(index, stop):
    flowers[i] -= mmm
      
  
print(ans)

Submission status: Accepted

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

count = 0

for i in range(max(h)):
	
	state = 0
	for j in range(N):
		if h[j] > i:
			 if state == 0:
			 	count += 1
			 	state = 1
		else:
			state = 0

print(count)

Submission status: Accepted

Solution code:

iN = int(input())
aH = [int(_) for _ in input().split()]

if iN == 1:
    print(aH[0])
    exit()

iC = 0
for _ in range(100):
    iM = max(aH)
    if iM == 0:
        break
    iH = aH.index(iM)
    if iH == iN-1:
        iC += iM - aH[iH-1]
        aH[iH] = aH[iH-1]
    elif iH == 0 :
        iR = 1
        while True:
            if aH[iH + iR] != iM:
                i2 = aH[iH+iR]
                iC += iM - i2
                for i in range(iH,iH+iR):
                    aH[i]=i2
                break
            else:
                iR += 1
                if iH +iR == iN:
                    iC += iM
                    for i in range(iH,iH+iR):
                        aH[i] =0
                    break
    else:
        iLM = aH[iH-1]
        iR = 1
        while True:
            if aH[iH +iR] != iM:
                i2 = aH[iH+iR]
                if i2 >= iLM:
                    iC += iM - i2
                    for i in range(iH,iH+iR):
                        aH[i]=i2
                else:
                    iC += iM -iLM
                    for i in range(iH,iH+iR):
                        aH[i]=iLM
                break
            else:
                iR += 1
                if iH +iR == iN:
                    iC += iM - iLM
                    for i in range(iH,iH+iR):
                        aH[i] =iLM
                    break
print(iC)

Submission status: Accepted

Solution code:
n = int(input())
flower = list(map(int, input().split()))
water = 0
empty = [0] * len(flower)
left, right = 0, 0
flag = 0
while(flower != empty):
  for i in range(len(flower)):
    if (flower[i]):
      flower[i] -= 1
      if (flag == 0):
        water += 1
        flag = 1
    else:
      flag = 0
  if (flower[0]):
    water += 1
    flag = 1
print(water)

Submission status: Accepted

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

count = 0

for i in range(n):    
    while h[i] >= 1:
        wid = 0
        for l in range(i,n):
            if h[l] >= 1:
                    wid = wid + 1
            else:
                break
        
        #widの分だけ水をやる
        for k in range(wid):
            h[i + k] = h[i+k] - 1
        
        count = count + 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
a = 0
while sum(h) > 0:
    lst = [i for i, x in enumerate(h) if x > 0]
    mx = min(lst)
    for i in range(len(lst) -1):
        if lst[i] + 1 == lst[i+1]:
            mx += 1
        else:
            break
    h = [x - 1 if i >= min(lst) and i <= mx else x for i, x in enumerate(h)]
    a += 1
print(a)

Submission status: Accepted

Solution code:
N = int(input())
hs = [int(n) for n in input().split()]
# print(N, hs)

def mkgrp(level, hl):
    # is_in_grp = False
    grps = []
    grp_start = None
    for i, h in enumerate(hl):
        if grp_start == None:
            if h >= level:
                grp_start = i
        if grp_start != None:
            if h >= level:
                pass
            else:
                grps.append((grp_start, i-1))
                grp_start = None
    if grp_start != None:
        grps.append((grp_start, i))
    return grps

def ma():
    ans = 0
    for i in range(1, max(hs)+1):
        grps = mkgrp(i, hs)
        ans += len(grps)
    return ans

print(ma())

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int, input().split()))
hl = [h]
cnt = 0
while hl != []:
  h = hl.pop(0)
  z = [i for i, x in enumerate(h) if x == 0]
  #print(0, z)
  if z == []:
    h = [i-1 for i in h]
    cnt += 1
    if any(h) == True:
      #print(3, h)
      hl.append(h)
  else:
    #print(1, h[:z[0]], h[z[0]+1:])
    if h[:z[0]] != []:
      hl.append(h[:z[0]])
    if h[z[0]+1:] != []:
      hl.append(h[z[0]+1:])
  #print(2, cnt, h)

print(cnt)

Submission status: Accepted

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

ans = 0

def mizu(h,l,r) :
    for i in range(l,r+1) :
        h[i] -= 1

while True :
    for i in range(n) :
        l = n + 0
        if h[i] == 0 :
            pass
        else :
            l = i + 0
            break

    for j in range(l,n) :
        r = n-1
        if h[j] == 0 :
            r = j - 1
            break
        else :
            pass

    if l==n :
        break
    else :
        mizu(h,l,r)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int,input().split()))
s = [0]*(N)
cnt = 0
#i = n のとき区間の幅n
for i in range(N,0,-1):
    for j in range(N-i+1):
        a = [0]*(i)
        for k in range(i):
            a[k] = h[j+k] - s[j+k]
        if all (s > 0 for s in a):
            ok = min(a)
            cnt += ok
            for p in range(i):
                s[j+p] += ok


print(cnt)

Submission status: Accepted

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

if sum(H) == 0:
    print(0)
    exit()

for _ in range(100000):
    status = 0
    for i, x in enumerate(H):

        if x != 0:
            H[i] = x - 1
            status = 1
        elif ((x == 0) and (status == 1)):
            break
        else:
            pass
    if sum(H) == 0:
        break

print(_ + 1)

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:
N = int(input())
h = [int(i) for i in input().split()]

def check(l):
    for i, n in enumerate(l):
        if n == 0:
            yield i

def f(l):
    # print("a", l)

    a = min(l)
    l_ = [i - a for i in l]
    m = [-1]
    m.extend(list(check(l_)))
    m.append(len(l))

    # print(" ", a, l_, m)
    if not any(l):
        return a

    s = 0
    for x, y in zip(m, m[1:]):
        if y - x > 1:
            s += f(l_[x+1:y])
    return s + a

print(f(h))

Submission status: Accepted

Solution code:
N = int(input())
h_list = list(map(int, input().split())) # "1 2 3"と入力

made=0
water=0
h_list.append(0)

while len(h_list)!=0:
    made=h_list.index(0)
    if made==0:
        h_list.pop(0)
    else:
        water+=1
        h_list[0:made]=[i-1 for i in h_list[0:made]]
print(water)

Submission status: Accepted

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

def s(l):
    x = list(map(str,l))
    x = [ 'a' + i for i in x ]

    x = ''.join(x)
    x = x.split('a0')
    x = [ i.split('a') for i in x ]
    for i in x:
        i.remove('')

    while [] in x:
        x.remove([])
        
    x = [list(map(int,i)) for i in x]
    return x

def f(l):

    if 0 in l:
        x = s(l)
        y = [f(i) for i in x]
        return sum(y)
    else:
        m = min(l)
        x = [ i-m for i in l]
        return m + f(x)
    
print(f(h))

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int, input().split()))
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
if sum(h)==0:
  print(0)
else:
  count = 0
  while sum(h) > 1:
    while h[0] == 0:
      h = h[1::]
    p = my_index(h, 0, -1)
    if p >= 0:
      d = min(h[:p])
      count += d
      for i in range(p):
        h[i] = h[i] - d
    else:
      d = min(h)
      count += d
      h = [x - d for x in h]
  print(count + sum(h))

Submission status: Accepted

Solution code:
# ABC116
# C
import numpy as np
N = int(input())
h_list = list(map(int, input().split()))

def shorten(idx_list, current_h):
    for idx in idx_list:
        current_h[idx] -= 1
    return current_h

def get_highest_idx(current_h):
    max_h = np.max(current_h)
    max_flower_idx = []
    for idx, h in enumerate(current_h):
        if h == max_h:
            max_flower_idx.append(idx)
    return max_flower_idx

ans = 0
while(np.max(h_list) > 0):
    highest_idx_list = get_highest_idx(h_list)
    mizunuki_idx = []
    
    for i, idx in enumerate(highest_idx_list):
        hight = h_list[idx]
        if i==len(highest_idx_list)-1:
            break
        else:
            if idx+1 == highest_idx_list[i+1]:
                j = 0
                while(True):
                    try:
                        if idx+j == highest_idx_list[i+j]:
                            j += 1
                        else:
                            break
                    except:
                        break

                mizunuki = np.array(highest_idx_list)[np.arange(i, i+j,1)]
                mizunuki_idx.append(mizunuki)
    if len(mizunuki_idx) == 0:
        mizunuki_ = [highest_idx_list[0]]
    else:
        mizunuki_ = mizunuki_idx[0]
    
    new_h = shorten(mizunuki_, h_list)
    h_list = new_h
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
flag = 0
mizu = 0

while True:

    for b in range(n):
        if a[b] == 0 and flag == 1:
            break

        if a[b] > 0:
            a[b] -= 1
            flag = 1
    
    if flag == 1:
        mizu += 1
        flag = 0
    else: break

print(mizu)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
H = np.array(list(map(int,input().split())),dtype=np.int)

def grandgarden(h):
#    print("h",h)
    m = h.min()
#    print("m",m)
    h -= m
    hills = np.where(h>0)[0]
#    print("hills",hills)

    mountains = [[]]
    i = 0
    for i in range(len(hills)):
        mt = mountains[-1]
        if len(mt)==0 or hills[i]==mt[-1]+1:
            mt.append(hills[i])
        else:
            mountains.append([hills[i]])
    if len(mountains[-1]) == 0:
        mountains.pop()
#    print("mountains",mountains)
    ret = m + sum([ grandgarden(h[np.array(mt,dtype=np.int)]) for mt in mountains])
    return ret

print(grandgarden(H))

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
n = int(input())
h_arr = np.array(list(map(int, input().split())))
ans = 0
h_min = min(h_arr)
if h_min > 0:
    h_arr -= h_min
    ans += h_min
while True:
    s = 0
    tmp = 0
    for i in range(n):
        if i == n-1:
            if h_arr[i] > 0:
                h_min = min(h_arr[s:])
                tmp += h_min
                h_arr[s:] = h_arr[s:] - h_min
            elif s < i:
                h_min = min(h_arr[s:i])
                tmp += h_min
                h_arr[s:i] = h_arr[s:i] - h_min
        elif h_arr[i] == 0:
            if s == i:
                s += 1
            else:
                h_min = min(h_arr[s:i])
                tmp += h_min
                h_arr[s:i] = h_arr[s:i] - h_min
                s = i + 1
    if tmp == 0:
        break
    else:
        ans += tmp
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
h = [int(i) for i in input().split()]
ans = 0

def f(h):
    global ans
    if len(h) == 0:
        return 
    v = [[]]
    for i in h:
        if i != 0:
            v[-1].append(i)
        else:
            v.append([])
    n = []
    for i in v:
        if len(i) == 0:
            continue
        j = min(i)
        ans += j
        n += [k - j for k in i]
        n += [0]
    f(n)

f(h)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int, input().split()))
nflag = -1
count = 0
sum = 0
for i in range(N):
    sum += h[i]
while True:
    if sum == 0:
        print(count)
        break
    nflag = -1
    for i in range(N):
        if h[i] != 0 and nflag == -1:
            nflag = i
            if i == N - 1:
                h[i] -= 1
                sum -= 1
                count += 1
                break
        elif h[i] == 0 and nflag != -1:
            for j in range(nflag, i):
                h[j] -= 1
            sum -= i - nflag
            count += 1
            break
        elif i == N - 1 and nflag != -1:
            for j in range(nflag, i + 1):
                h[j] -= 1
            sum -= i - nflag + 1
            count += 1
            break

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
count = 0
sidx = 0
def div(l, ls):
    tmpl = []
    for i in l:
        if i == 0:
            if len(tmpl) != 0:
                ls.append(tmpl)
            tmpl = []
        else:
            tmpl.append(i)
    else:
        if len(tmpl) != 0:
            ls.append(tmpl)
    return ls

ls = [s]
count = 0
while len(ls) != 0:
    l = ls.pop()
    mins = min(l)
    for i in range(len(l)):
        l[i] -= mins
    count += mins
    div(l, ls)

print(count)