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:
# ABC116C - Grand Garden
n = int(input())
lst = [0] + list(map(int, input().rstrip().split()))
ans = 0
for i in range(1, n + 1):
    ans += max(0, lst[i] - lst[i - 1])
print(ans)

Submission status: Accepted

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

ans = 0
for h_ref in range(1, 101):
    prev = 0
    for i, hi in enumerate(h):
        curr = int(hi >= h_ref)
        if curr > prev: ans += 1
        prev = curr

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
H = [int(s) for s in input().split()]
H.append(0)
def sub(x,y):
    global H
    print(H,"H")
    
    for i in range(x,y):
        H[i] = H[i] -1
    print(H, "H[i]")
        
count = 0
for i in range(n):
    if H[i] > H[i+1]:
        count += H[i] - H[i+1]
print(count)
"""
def garden(a,b):
    global H
    global count
    if a==b :
        return count
    
    for i in range(a,b):
        if H[i] == 0:
            print("a=%d,b=%d,i=%d,1"%(a,b,i))
            return garden(a, i) + garden(i+1, b)
    
    if sum(H) == 0:
        return count
    sub(a,b)#全ての花を伸ばすべき
    count += 1
    print(count,"count")
    garden(a,b)
print(garden(0,n))
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
最初の方針
　例えば最大の高さの花に着目し、隣の花2つのうち、高い方の高さにも着目する。
　まずその差を求め、その分だけ花の高さを伸ばす。
　→難しそう

2つめの方針
　もともと花の高さがあり、そこから削っていくような考え方はどうか。
　まずひとつずつ削っていく。
　リストを走査していくイメージで進め、フラグを用意しておく。
　1で削り続けている限りは1。
　そして、高さ0の部分に行き当たるか、一周したら1をansに加算する。
　0の場合は、そのまま走査していき、1に行き当たったらまた上と同様のことを行う。

"""
import copy

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

ans = 0
while sum(H) > 0:
    tmp = []
    flag = 0
    for h in H:
        if h > 0:
            tmp.append(h - 1)
            if flag == 0:
                ans += 1
                flag = 1
        else:
            tmp.append(0)
            flag = 0
    H = copy.deepcopy(tmp)
    
print(ans)

Submission status: Accepted

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

for i in range(N):
	if A[i] > A[i+1]:
		cnt += A[i]-A[i+1]

print(cnt)

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 = list(map(int,input().split()))
h.append(0)
tmp = 0
water = 0
for i in h:
    if i < tmp:
        water += tmp - i
    tmp = i
print(water)

Submission status: Accepted

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

def split_list(_list):
    ret_list = []
    tmp_list = []
    for i in range(len(_list)):
        if _list[i] == 0:
            if len(tmp_list) != 0:
                ret_list.append(tmp_list)
                tmp_list = []

        else:
            tmp_list.append(_list[i])

    if len(tmp_list) != 0:
        ret_list.append(tmp_list)
    return ret_list

def give_min_water(_list):
    _min = min(_list)
    _list = [(num - _min) for num in _list]
    return _min, _list

ret = 0
new_list = split_list(h_list)
#print(new_list)
while len(new_list) != 0:
    new_list2 = []
    for _list in new_list:
        tmp_count, tmp_list = give_min_water(_list)
        # print(tmp_count)
        # print(tmp_list)
        ret += tmp_count
        tmp_list = split_list(tmp_list)
        if (len(tmp_list) != 0):
            for _list2 in tmp_list:
                new_list2.append(_list2)
    new_list = new_list2
print(ret)

Submission status: Accepted

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

def is_ok(state):
    flag = 0
    for i in range(N):
        if state[i] != h[i]:
            return False
    return True

i = 0
cnt = 0
state = [0 for _ in range(N)]
while not is_ok(state):
    if state[i] == h[i]:
        i += 1
        continue
    j = 0
    while i + j < N and state[i+j] != h[i+j]:
        j += 1
    for k in range(i, i+j):
        state[k] += 1
    cnt += 1
print(cnt)

Submission status: Accepted

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


if len(h) == 1:
    print(h[0])
    exit()
    
cnt = 0
cnt_line = 0
v = h[0]
for i in range(1, N):
    if h[i] < v:
        cnt += v - cnt_line
        cnt_line = h[i]
    v = h[i]
if h[-1] >= h[-2]:
    cnt += h[-1] - cnt_line
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def get_div_cnt(H):
    c = 1 if H[0] > 0 else 0

    for i in range(1,len(H)):
        if H[i-1] == 0 and H[i] > 0:
            c += 1

    return c

def solve(N: int, H: "List[int]"):
    R = 0
    while sum(H) > 0:
        R += get_div_cnt(H)
        for i in range(len(H)):
            if H[i] > 0:
                H[i] -= 1

    print(R)





# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, h)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(n):
    if ans == 0:
        ans += h[i]
    else:
        if h[i] > h[i-1]:
            ans += h[i]-h[i-1]
print(ans)

Submission status: Accepted

Solution code:
def water(H, start, stop):
    if max(H) == 0:
        return

    # water
    valley = min(H[start:stop])
    for i in range(start, stop):
        H[i] -= valley
    global ans
    ans += valley

    # search for next area
    valley_indices = [start + i for i, h in enumerate(H[start:stop]) if h == 0]
    if valley_indices[0] != start:
        valley_indices = [start - 1] + valley_indices
    if valley_indices[-1] != stop - 1:
        valley_indices += [stop]
    for i in range(len(valley_indices) - 1):
        if valley_indices[i + 1] - valley_indices[i] > 1:
            water(H, valley_indices[i] + 1, valley_indices[i + 1])


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

ans = 0
water(H, 0, N)
print(ans)

Submission status: Accepted

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

cn = 0
for i in range(n):
    if cn == 0:
        cn += H[i]
    else:
        cn += H[i]-H[i-1] if H[i] > H[i-1] else 0
print(cn)

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:
def oneIsland(lis):
    island=0
    newlis=lis
    newlis.append(False)
    for n,i in enumerate(newlis):
        if n==len(newlis)-1:break
        if i and (not newlis[n+1]):
            island+=1
    return(island)
N=int(input())
h=[int(i) for i in input().split()]
toGrowBoolean=[]
for i in range(max(h)):#長さi+1以上ならTrue
    toGrowBoolean.append([k>i for k in h])
print(sum([oneIsland(row) for row in toGrowBoolean]))

Submission status: Accepted

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

ans = 0
for i in range(0,101):
    count = 0
    for j in range(n):
        if h[j] - i <= 0 and h[j+1] - i > 0:
            count += 1
    ans += count

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def water(a):
    if len(a)==0:return 0
    ma=min(a)
    x=ma
    l=[]
    for i in range(len(a)):
        y=a[i]-ma
        if y>0:l.append(y)
        else:
            x+=water(l)
            l=[]
    x+=water(l)
    return x

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

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int,input().split()))
ans = 0
check  = 0
for i in h:
    if check<i:
        ans += i-check
    check = i
print(ans)

Submission status: Accepted

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

ans = 0
check = 0
for i in h:
    if check < i:
        ans += i-check
    check = i

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
H = [int(n) for n in input().split()]

def main():

    h = H
    max_h = max(h)

    ans = 0
    curr_h = 0

    while curr_h <= max_h:
        prev_h = 0
        for n in h:
            if n > curr_h and prev_h <= curr_h:            
                ans += 1
            prev_h = n
        curr_h += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - Grand Garden
https://atcoder.jp/contests/abc116/tasks/abc116_c

"""
import sys



def solve(heights):
    def w(arr):
        stack = []
        buff = []
        while arr:
            h = arr.pop(0)
            if h == 0:
                if buff:
                    stack.append(buff)
                    buff = []
            else:
                buff.append(h)
        if buff:
            stack.append(buff)
        return stack

    ans = 0
    stack = w(heights)
    while stack:
        arr = stack.pop()
        m = min(arr)
        ans += m
        s = w([a-m for a in arr])
        stack.extend(s)
    return ans


def main(args):
    N = int(input())
    heights = [int(h) for h in input().split()]
    ans = solve(heights)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

h = [0] + H
c = 0
for i in range(1, 100 + 1):
	for j in range(1, N + 1):
		if h[j - 1] < i and i <= h[j]:
			c += 1
print(c)

Submission status: Accepted

Solution code:
#C-116
n = int(input())
h_diff = [int(i) for i in input().split()]
ans = 0
for ni in range(n):
  while h_diff[ni] > 0:
    if 0 in h_diff[ni+1:]:
      r = h_diff[ni+1:].index(0) + (ni+1)
      ans += min(h_diff[ni:r])      
      h_diff[ni:r] = [i - min(h_diff[ni:r]) for i in h_diff[ni:r]]
    else:
      ans += min(h_diff[ni:])      
      h_diff[ni:] = [i - min(h_diff[ni:]) for i in h_diff[ni:]]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue May 14 19:41:33 2019

@author: avin"""

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

now = l[0]
sums = l[0]
for i in range(1,n):
    if now < l[i]:
        sums += l[i] - now
    now = l[i]
print(sums)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())
hh = inpl()

ans = 0
def bukatu(hh,L):
    global ans
    if L <= 0:
        return
    elif L == 1:
        ans += hh[0]
        return
    else:
        while not 0 in hh:
            ans += 1
            for i in range(L):
                hh[i] -= 1
        nexthh = [list(map(int,' '.join(h.split('*')).split())) for h in ('*'+'*'.join(map(str,hh))+'*').split('*0*')]
        #print(nexthh,ans)
        for hh in nexthh:
            bukatu(hh,len(hh))

bukatu(hh,N)
print(ans)

Submission status: Accepted

Solution code:
def daruma_drop(ls):
  if max(ls)==0:
    return 0
  
  can_drop = min(ls)
  dropped = [ v - can_drop for v in ls ]
  devided = []
  b_idx = -1
  for i in range(len(dropped)+1):
    if i==len(dropped):
      if b_idx!=-1:
        devided.append(dropped[b_idx:])
      break
    
    if b_idx==-1 and dropped[i]!=0:
      b_idx = i
      continue
    
    if b_idx!=-1 and dropped[i]==0:
      devided.append(dropped[b_idx:i])
      b_idx = -1
      continue
  
  return can_drop + sum(map(daruma_drop, devided))
  
n = int(input())
hs = list(map(int, input().split(' ')))
print(daruma_drop(hs))

Submission status: Accepted

Solution code:
def spritarr(arr):
  ret=[]
  for i in range(arr.count(0)):
    pos=arr.index(0)
    ret.append(arr[:pos])
    arr=arr[pos+1:]
  if len(arr)!=0:
    ret.append(arr)
  return ret

n=int(input())
arr=list(map(int,input().split()))
tmp=spritarr(arr)
ans=0
while len(tmp)!=0:
  tmp2=[]
  for i in range(len(tmp)):
    if len(tmp[i])!=0:
      tm=min(tmp[i])
      ans+=tm
      for j in range(len(tmp[i])):
        tmp[i][j]-=tm
    tmp2.extend(spritarr(tmp[i]))
  tmp=tmp2
print(ans)

Submission status: Accepted

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


test = []
tmp = []

while max(h) != 0:
    tmp = []
    for i in range(N):
        if h[i] == 0:
            tmp.append(0)
        else:
            tmp.append(1)
            h[i] -= 1
    test.append(tmp)

ans = 0
flag = 0
for i in test:
    if i[0] == 1:
        ans += 1
    for j in range(1,N):
        if i[j] == 0:
            continue
        elif i[j-1] == 0 and i[j] == 1:
            ans += 1
print(ans)

Submission status: Accepted

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

ret = H[0]
for i in range(1,N):
    if H[i] > H[i-1]:
        ret += H[i] - H[i-1]
    
print(ret)

Submission status: Accepted

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

ret = h[0]
for i in range(1, N):
    if h[i] > h[i - 1]:
        ret += h[i] - h[i - 1]
print(ret)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

ans = 0
while True:
    is_segment = False
    segment_count = 0
    for h in hs:
        if h > 0:
            if not is_segment:
                segment_count += 1
            is_segment = True
        else:
            is_segment = False
    if segment_count == 0:
        break
    else:
        ans += segment_count
        hs = [max(0, h-1) for h in hs]
print(ans)

Submission status: Accepted

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

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


def calc(list_h):
    if not list_h:
        return 0

    min_height = min(list_h)
    list_h = [list_h[i] - min_height for i in range(len(list_h))]
    zero_indexes = [i for i, x in enumerate(list_h) if x == 0]

    if not any(list_h):
        return min_height

    left_list = list_h[:zero_indexes[0]]
    right_list = list_h[zero_indexes[0]+1:]
    return calc(left_list) + calc(right_list) + min_height


print(calc(h))

Submission status: Accepted

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

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


def calc(list_h):
    if not list_h:
        return 0

    min_height = min(list_h)
    list_h = [list_h[i] - min_height for i in range(len(list_h))]
    zero_indexes = [i for i, x in enumerate(list_h) if x == 0]

    if not any(list_h):
        return min_height

    sum_cnt = 0
    left_list = list_h[:zero_indexes[0]]
    right_list = list_h[zero_indexes[0]+1:]
    sum_cnt += calc(left_list) + calc(right_list)

    return sum_cnt + min_height


print(calc(h))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
li = [ int(it) for it in input().split() ]

sss = 0

for i in range(10000000):
  ma = max(li)
  if (ma==0):
    break
  ind = li.index(ma)

  l = ind
  for i in range(ind,N):
    if ( li[i] != ma ):
      break
    else:
      l = i
  r = ind
  for i in range(ind,-1,-1):
    if ( li[i] != ma ):
      break
    else:
      r = i
  l,r=r,l
  nma = 0
  if (l>0):
    nma = max(nma,li[l-1])
  if (r<N-1):
    nma = max(nma,li[r+1])

  sss += ma-nma
  for i in range(l,r+1):
    li[i]-=ma-nma
print (sss)

Submission status: Accepted

Solution code:
'''
数列hを棒グラフと見て
0と0で挟まれた山の個数を数える→すべて-1して山を削っていく
出力例２なら
[3 1 2 3 1]をmax(h)回，-1ずつ減らしていく
[2, 0, 1, 2, 0]
[1, 0, 0, 1, 0]
[0, 0, 0, 0, 0]
0になると花に水をやってはいけないから
count0でその花が何番目にあるか，を取得
数列count0で前項との差が1より大きければ山がある＝水をかけれる
'''
n=int(input())
h=list(map(int, input().split()))
sum=0
for i in range(max(h)):
    if 0 not in h:
        h=[X-1 if X>0 else 0 for X in h]
        sum+=1
        # print(h,1)
    else:
        count0=[Y for Y, Z in enumerate(h) if Z==0]
        a=count0.copy()
        b=count0.copy()
        del a[0]
        del b[-1]
        c=[x-y for(x,y) in zip(a,b)]
        sum = sum + len(c)-c.count(1)
        if count0[0]>0 and count0[-1]<n-1:
            sum +=2
        elif count0[0]>0 or count0[-1]<n-1:
            sum +=1
        else:
            sum +=0
        h=[i-1 if i>0 else 0 for i in h]
print(sum)

Submission status: Accepted

Solution code:
n=int(input())
h=list(map(int, input().split()))
sum=0
for i in range(max(h)):
    if 0 not in h:
        h=[X-1 if X>0 else 0 for X in h]
        sum+=1
        # print(h,1)
    else:
        count0=[Y for Y, Z in enumerate(h) if Z==0]
        a=count0.copy()
        b=count0.copy()
        del a[0]
        del b[-1]
        c=[x-y for(x,y) in zip(a,b)]
        sum = sum + len(c)-c.count(1)
        if count0[0]>0 and count0[-1]<n-1:
            sum +=2
        elif count0[0]>0 or count0[-1]<n-1:
            sum +=1
        else:
            sum +=0
        h=[i-1 if i>0 else 0 for i in h]
print(sum)

Submission status: Accepted

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

link = 0
ans = 0
while True:
    for i in range(N):
        if i < N-1:
            if h[i] > 0:
                h[i] -= 1
                if h[i+1] > 0:
                    link = 1
                else:
                    link = 0
                if link == 0:
                    ans += 1
        else:
            if h[i] > 0:
                h[i] -= 1
                link = 0
                ans += 1

    if all([v == 0 for v in h]):
        print(ans)
        exit()

Submission status: Accepted

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

n = int(input())

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

ans = 0
active = 0

for i in range(n):
    if active >= h[i]:
        active = h[i]
    else:
        ans += h[i] - active
        active = h[i]
print(ans)

Submission status: Accepted

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

max_h = max(H)
AH = []
for i in H:
  AH.append([1 if j < i else 0 for j in range(max_h)])
  
AH = list(zip(*AH))

count= 0
for i in AH:
  prev = 0
  for j in i:
    if j != prev and j == 1:
      count += 1
    prev = j

print(count)

Submission status: Accepted

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


def water(x):
  global ans
#  print(x, ans)
  if any(x) == False:
#    print(0)
    return
  else:
#    print(1)
    if 0 in x:
#      print(2)
      x1, x2 = x[0:x.index(0)], x[x.index(0)+1:]
      water(x1)
      water(x2)
    else:
#      print(3)
      ans += min(x)
      x = list(map(lambda i:i-min(x), x))
      water(x)
  return    
  
water(h)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
H = list(map(int, input().split()))
H.append(0)
ans = []
start = 0
prev = 0
for i in H:
  if prev > i and prev != start:
    ans.append(prev - start)
    start = i
  elif start > i:
    start = i
  prev = i

print(sum(ans))

Submission status: Accepted

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

count = 0
sub_H_list = [H]
while True:
    if len(sub_H_list) == 0:
        break
    sub_H = sub_H_list.pop()
    min_hight = min(sub_H)
    if min_hight == 0:
        # 分割
        border = sub_H.index(0)
        if border == 0 and len(sub_H) == 1:
            pass
        elif border == 0:
            sub_H_list.append(sub_H[1:])
        elif border == len(sub_H)-1:
            sub_H_list.append(sub_H[:-1])
        else:
            sub_H_list.append(sub_H[0:border])
            sub_H_list.append(sub_H[border+1:])

    else:
        # 育成
        sub_H_list.append(list(map(lambda x: x-min_hight, sub_H)))
        count += min_hight

print(count)

Submission status: Accepted

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

def c(a,b): # b exclusive
  
  if b-a==1:
    return h[a]
  if b==a:
    return 0
  
  try:
    s = h.index(0,a,b)
  except ValueError:
    s = -1
  if s>=0:
    return c(a,s) + c(s+1,b)
  # no zeros
  m = min(h[a:b])
  for i in range(a,b):
    if h[i] == m:
      index = i
    h[i] -= m
  
  return m + c(a,index) + c(index+1,b)

print(c(0,N))

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())
h = list(map(int, sys.stdin.readline().split()))

max_h = max(h)

shakutori_list = []
shikiri = []
#0
phase = 0

total = 0

for i in range(max_h):
    current_height = i + 1
    phase = 0
    for j in range(N):
        if h[j] >= (current_height) and phase == 0:
            total += 1
            phase = 1
        if h[j] < current_height and phase == 1:
            phase = 0

print(total)

Submission status: Accepted

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

ans = 0
cur = 0
while h.count(0) != len(h):
    for i in range(N+2):
        if h[i] == 0:
            if cur > 0:
                ans += 1
            cur = 0
        elif h[i] > 0:
            h[i] -= 1
            cur += 1
print(ans)

Submission status: Accepted

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

def split_list(l, number=0):    
    if len(l) == 0:
        return []
    elif number not in l:
        return [l]
    first_occurance = l.index(number)
    result = []
    if first_occurance != 0:
        result.append(l[0:first_occurance])
    for s in split_list(l[first_occurance + 1:]):
        result.append(s)

    return result

queue = split_list(h)
count = 0
score = 0
while len(queue) != count:
    target = queue[count]
    mizu = min(target)
    target = [x - mizu for x in target]
    score += mizu

    for s in split_list(target):
        queue.append(s)
    count += 1

print(score)

Submission status: Accepted

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

zerobefore = True
times = 0
while sum(h) > 0:
    
    for i in range(len(h)):

        if h[i] == 0 and zerobefore:
            continue
        elif h[i] == 0 and not zerobefore:
            times += 1
            zerobefore = True #Trueに戻す
            break
        elif i == len(h) - 1 and not zerobefore and h[i] != 0:
            h[i] -= 1
            times += 1
            zerobefore = True  
        elif i == len(h) -1 and zerobefore and h[i] != 0:
            h[i] -= 1
            times += 1
            zerobefore = True
        else:
            h[i] -= 1
            zerobefore = False
        
        
        
    #print(h)
    #print(times)
            
print(times)

Submission status: Accepted

Solution code:
from math import factorial
from sys import exit, stdin
N = int(stdin.readline().rstrip())
H = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 0
for i in range(1,N):
    if H[i-1] > H[i]:
        ans += H[i-1]-H[i]
ans += H[-1]
print(ans)

Submission status: Accepted

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


def search(start, end):
    sub_list = []

    index = start
    is_searching = False

    sub = 100
    l = start
    while index <= end:

        if H[index] > 0 and not is_searching: 
            is_searching = True
            l = index

        if H[index] == 0 and is_searching: 
            is_searching = False
            r = index - 1
            sub_list.append((l,r, sub))

        if is_searching:
            sub =  min(sub, H[index])

        index += 1
 
    if is_searching:
        sub_list.append((l, end, sub))


    count = 0
    for l, r, s in sub_list:
        for index in range(l, r + 1):
            H[index] -= s

        count += s
        count += search(l, r)

    return count


        
print(search(0, N -1))

Submission status: Accepted

Solution code:
def water(l,x,c):
    if l==1:
        return x[0]
    if l==0:
        return 0
    k=j=0
    for i in x:
        if i==0:
            k=j
            break
        j+=1
    if j<l:
        c += water(k, x[:k], 0)
        c += water(l - (k+1) , x[k+1:], 0)
    else:
        c+=1
        for i in range(l):
            x[i]-=1
        i=0
        while x[i]==0 and i < l-1:
            i+=1
        c+=water(l-i,x[i:],0)
    return c

a=int(input())
b=[int(i) for i in input().split()]
c=water(a,b,0)
print(c)

Submission status: Accepted

Solution code:
def water(l,x,c):
    if l==1:
        return x[0]
    if l==0:
        return 0
    k=j=0
    for i in x:
        if i==0:
            k=j
            break
        j+=1
    if j<l:
        #print(k)
        #print(x[:k])
        c += water(k, x[:k], 0)
        #print(l - (k+1))
        #print(x[k+1:])
        c += water(l - (k+1) , x[k+1:], 0)
    else:
        c+=1
        for i in range(l):
            x[i]-=1
        i=0
        while x[i]==0 and i < l-1:
            i+=1
        c+=water(l-i,x[i:],0)
    return c

a=int(input())
b=[int(i) for i in input().split()]
c=water(a,b,0)
#print("A")
print(c)

Submission status: Accepted

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

Submission status: Accepted

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

n = max(lst)
h = 1
ret = 0
while n >= h:
    flg = True
    for x in lst:
        if x >= h and flg:
            ret += 1
            flg = False
        elif h > x:
            flg = True
    h += 1
print(ret)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
lst = [int(x) for x in input().split()]

lst2 = np.zeros((max(lst), N))
for idx, n in enumerate(lst):
    lst2[:n,idx] = 1

ret = 0
for x in lst2:
    flg = True
    for y in x:
        if flg and y == 1:
            ret += 1
            flg = False
        elif y == 0:
            flg = True
print(ret)

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 = [int(a) for a in input().split(" ")]
ans=0
while any([h!=0 for h in H]):
    i=0
    while i<N and H[i]==0:
        i+=1
    j=i
    minh=H[i]
    while j<N and H[j]!=0:
        minh = min(H[j], minh)
        j+=1
    for k in range(i,j):
        H[k]-=minh
    ans+=minh
print(ans)

Submission status: Accepted

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

ans = 0

while sum(h) > 0:
    diff = min([_h for _h in h if _h > 0])
    idx = h.index(diff)
    for i in range(idx, len(h)):
        if h[i] == 0:
            break
        h[i] -= diff
    for i in range(0, idx)[::-1]:
        if h[i] == 0:
            break
        h[i] -= diff
    ans += diff


print(ans)

Submission status: Accepted

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

ans = 0
flag = False

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

Submission status: Accepted

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

Submission status: Accepted

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

nums = [h[0]]

for i in range(N-1):
    if h[i+1] > h[i]:
        nums.append(nums[i] + (h[i+1] - h[i]))
    else:
        nums.append(nums[i])

print(nums[-1])

Submission status: Accepted

Solution code:
N = int(input())

lst = list(map(int, input().split()))

count = 0 #水をやる回数
def water(i, j): #lst[i:j]に水をやるとする
    count = 0
    #print ('A')
    #print ('lst', lst[i:j])
    #print ('i, j=', i, j)
    if i == j or lst[i:j] == [0]:
        #print ('X')
        return 0
    elif min(lst[i:j]) == 0: #lst[i:j]内の最小値が0の時
        a = lst[i:j].index(0)
        #print ('a=', a)
        #print ('B', count)
        count = water(i,i + a) + water(i + a+1, j)
        return count
    else: #lst[i:j]の最小値が0でない時
        for x in range(i,j):
            lst[x] = lst[x] - 1
        #print ('C', count)
        count += 1 + water(i, j)
        return count

print(water(0, N))

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int, input().split()))
ans = 0
INF = float("inf")
while True:
  # 左端から０以外の値（問題のｌ）を探す
  # 毎度左端から探すので、リスト中の０部分列が左から伸びてきても問題ない
  left = -1
  for i in range(N):
    if h[i] != 0:
      left = i
      break
  if left == -1:
    break #すべてが０になったので終了
  
  # leftの位置から０の手前まで（問題のr）を探す
  # index()は見つからない場合エラーが戻ってくるのでだめ
  right = -1
  for i in range(left, N):
    if h[i] == 0:
      right = i - 1
      break
      
    if i == N - 1:
      right = N - 1

  min_length = min(h[left:right+1])
  # 部分配列から一番小さい値を取り去る
  for i in range(left, right+1):
    h[i] -= min_length
  
  ans += min_length
  
  
  
print(ans)

Submission status: Accepted

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

ans = 0
current_height = 0
for i in range(N):
  # h[i-1]までの高さにはh[i]も育っているので、その差分だけ水をやる必要がある
  # current_height は一つ手前の花の高さ
  if h[i] > current_height:
    ans += h[i] - current_height
    current_height = h[i]
  else:
    # i-1番目の花の高さのほうがi番目より高いなら、水を新たにやる必要はない（i-1に水をやるときに同時に達成できるので）
    current_height = h[i]



print(ans)