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:

import bisect
import collections
import itertools


def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n=getint()
hs=getints()

def solve(hs:list):
    if not hs or not max(hs):
        return 0
    add = min(hs)
    for i in range(len(hs)):
        hs[i] -= add
    res = add
    now = []
    for h in hs:
        if not h:
            res += solve(now)
            now = []
            continue
        now.append(h)
    res += solve(now)
    return res

print(solve(hs))

Submission status: Accepted

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

h.append(0)
i = 0
answer = 0
while i < n:
    if h[i] == 0:
        i += 1
    else:
        j = i
        while h[j] != 0:
            j += 1
        min_h = min(h[i:j])
        for k in range(i,j):
            h[k] -= min_h
        answer += min_h

print(answer)

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:
n = int(input())
h = list(map(int, input().split()))
ans = 0

while True:
#    print(h)
    if max(h) == 0:
        break
    maxV = max(h)
    count = 1
    prev = h.index(maxV)

    if prev != len(h)-1:
        for i in range(prev+1, len(h)):
            if h[i] == maxV:
                if i > prev+1:
                    count += 1
                    prev = i
                else:
                    prev = i

    ans += count
    for i in range(len(h)):
        if h[i] == maxV:
            h[i] -= 1
#    filter(lambda x: x == maxV, h)
#    h = list(map(lambda x: x - 1, filter(lambda x: x == maxV, h)))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
h=list(map(int,input().split()))
t=[0]*N
a=0
for i in range(N):
        while t[i]<h[i]:
                for j in range(i,N):
                        if t[j]<h[j]:
                                t[j]+=1
                        else:
                                break
                a+=1
print(a)

Submission status: Accepted

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

_min = min(H)
# print(_min)
counter = _min
for i in range(N):
    H[i] -= _min

buff = [0 for i in range(101)]

for j in range(1, 101):
    flag = False
    for i in range(N):
        if H[i] - j >= 0:
            buff[i] = 1
            if not flag:
                counter += 1
            flag = True
        else:
            if flag:
                flag = False



print(counter)

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

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

counter = 0
for i in range(100):
    count_flag = False
    for index, h in enumerate(h_list):
        if h > 0:
            count_flag = True
            h_list[index] = h - 1
        if (h == 0 or index == len(h_list) - 1) and count_flag:
            counter += 1
            count_flag = False

print(counter)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int, input().split()))
h = [h[i] if h[i] != 0 else "#" for i in range(n)]

ans = 0
cond = True
while cond:
    for i in range(n):
        if (i == 0 and h[i] != "#") or (h[i-1] == "#" and h[i] != "#"):
            ans += 1
        
        if h[i] != "#":
            h[i] -= 1

    h = [h[i] if h[i] != 0 else "#" for i in range(n)]

    if h.count("#") == n:
        cond = False

print(ans)

Submission status: Accepted

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

water = 0 #水あげた回数
h1 = 0
for n in range(N):
  h2 = H[n]
  if h1 < h2:
    water += (h2 - h1)
  h1 = h2

print(water)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
h=list(map(int,input().split()))
ans=0
for i in range(n):
  l=len(h)
  if(l==1):
    ans+=h[0]
  else:
    m=max(h)
    a=h.index(m)
    if(a==0):
      ans+=h[0]-h[1]
      h=h[1:]
    elif(a==l-1):
      ans+=h[l-1]-h[l-2]
      h=h[:l-1]
    else:
      ans+=h[a]-(max(h[a-1],h[a+1]))
      h=h[:a]+h[a+1:]
print(ans)

Submission status: Accepted

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

c = 0
for i in range(n):
    while h[i] > 0:
        for j in range(i, n):
            if h[j] == 0:
                break
            h[j] -= 1
        c += 1

print(c)

Submission status: Accepted

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

count = 0
while True:
    zero = True
    allzero = True
    for i in range(len(h)):
        if h[i]>0 and zero:
            zero = False
            allzero = False
            count += 1
            h[i] -= 1
        elif h[i]>0:
            allzero = False
            h[i] -= 1
        else:
            zero = True
    if allzero:
        break
print(count)

Submission status: Accepted

Solution code:
from collections import deque

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

# Initial settings
stack = deque()
stack.append(hhh)
n_operation = 0


def operation():
    global stack, n_operation

    flower_heights = stack.pop()
    args_zero_height = [i for i, v in enumerate(flower_heights) if v == 0]
    
    if args_zero_height == []:  # If there is no zero elem.
        flower_heights_minus1 = list(map(lambda x: x-1, flower_heights))
        n_operation += 1
        stack.append(flower_heights_minus1)
    else:  # If there are zero elems
        last_arg_zero = -1
        for i, arg in enumerate(args_zero_height):
            if i == 0:
                # Rightside
                non_zero_heights = flower_heights[:arg]
            else:
                # Middle
                non_zero_heights = flower_heights[last_arg_zero+1:arg]

            if non_zero_heights != []:
                non_zero_heights_minus1 = \
                    list(map(lambda x: x-1, non_zero_heights))
                n_operation += 1
                stack.append(non_zero_heights_minus1)
            last_arg_zero = arg
        # Add leftside
        if last_arg_zero < len(flower_heights)-1:
            non_zero_heights = flower_heights[last_arg_zero+1:]
            # The fucking code (DRY)
            non_zero_heights_minus1 = \
                list(map(lambda x: x-1, non_zero_heights))
            n_operation += 1
            stack.append(non_zero_heights_minus1)


# Do operations while stack is not empty
while stack:
    operation()

print(n_operation)

Submission status: Accepted

Solution code:
def Water( list1, n):
    sp = -1
    for i in range( n ):
        if list1[ i ] > 0:
            sp = i
            break
    for i in range(sp,n):
        if list1[ i ] > 0 :
            list1[ i ] -= 1
        else:
            break
    return list1

N = int(input())
Hlist = list(map(int,input().split()))
mizu = 0

while max(Hlist) > 0:
    mizu += 1
    Water( Hlist, N )

print( mizu )

Submission status: Accepted

Solution code:
def mizu(h):
    global count
    # 終端処理
    if len(h) is 0:
        return
    if len(h) is 1:
        count += h[0]
        return
    # その範囲の最小値
    m = min(h)
    count += m
    # 残りの高さ
    h = [i - m for i in h]
    while 0 in h:
        # （最小値だった）0の箇所で分割
        mizu(h[:h.index(0)])
        h = h[h.index(0)+1:]
    mizu(h)


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

count = 0
mizu(h)

print(count)

Submission status: Accepted

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

while True:
    counter = 0
    for i in range(n):
        if h[i] == 0:
            counter += 1
            continue
        elif h[i] != 0 and h[i + 1] == 0:
            h[i] -= 1
            ans += 1
        else:
            h[i] -= 1
    if counter == n:
        break

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""
# 連続していれば1を引く。
if __name__ == "__main__":
    N = int(sys.stdin.readline())
    L = list(map(int, sys.stdin.readline().split()))

    cnt = 0
    while True:
        if sum(L) == 0:
            print(cnt)
            exit()
        si = 0
        cont = False

        for i in range(len(L)):
            if L[i] != 0:
                if not cont:
                    cont = True
                    si = i
            elif L[i] == 0:
                if cont:
                    cont = False
                    for j in range(si, i):
                        L[j] -= 1
                    cnt += 1
            if cont and i == len(L) - 1:
                for j in range(si, i + 1):
                    L[j] -= 1
                cnt += 1

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int,input().split()))
if N == 1:
    print(h[0])
    exit()

cnt = 0
low = 0
for i in range(N-1):
    if h[i+1] < h[i] and cnt == 0:
        cnt += h[i]
        low = h[i+1]
    elif h[i+1] < h[i]:
        cnt += h[i] - low
        low = h[i+1]
    elif i == N-2:
        cnt += h[i+1] - low

print(cnt)

Submission status: Accepted

Solution code:
# 2019/08/09

n=int(input())
h=[0]+list(map(int,input().split()))+[0]
n+=2
cnt=0
btm=0
for i in range(n-1):
    if h[i]==h[i+1]:continue
    
    if h[i]<h[i+1]:
        btm=min(h[i],btm)
    else:
        cnt+=h[i]-btm
        btm=h[i+1]
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
count = 0
done = False
while done == False:
    for i in range(n):
        if h[i] >= 0:
            h[i] -= 1
        
        if i > 0 and h[i] < 0 and h[i-1] >= 0:
            count += 1

        if i == n-1 and h[i] >= 0:
            count += 1
    if max(h) <= 0:
        done = True
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd
from itertools import accumulate
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    h = list(map(int, sys.stdin.readline().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())
hl=list(map(int, input().split()))
p=sum=0
for i in range(n):
    if p < hl[i]:
        sum+=(hl[i]-p)
    p=hl[i]
print(sum)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
now = [0 for _ in range(n)]
cnt = 0
l = 0
while True:
  if now == h:
    break
  elif now[l] == h[l]:
    l += 1
  else:
    r = l
    try:
      while now[r] < h[r]:
        r += 1
    except:
      pass
    for i in range(l,r):
      now[i] += 1
    cnt += 1
    #print(now)
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.append(0)
a = [0] + a
hani = []

count = 0
def gen(x):
    return x-min(a)

a = list(map(gen, a))

for i in range(len(a)):
    b = [i for i,x in enumerate(a) if x == 0]
    
def gen(x):
    return x-min(hani)


while sum(a) != 0:
    for i in range(len(a)):
        b = [i for i,x in enumerate(a) if x == 0]
    for i in range(len(b)-1):
        
        hani = a[b[i]+1:b[i+1]]
        if len(hani) != 0:
            count += min(hani)
            a[b[i]+1:b[i+1]] = list(map(gen, hani))
print(count)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
h_ls = list(map(int,input().split(" ")))

h_ls = np.array(h_ls)
n = 0
h_len = len(h_ls)
while max(h_ls)!=0:
    max_ind = h_ls.argmax()
    d = 0
    while max_ind+d < h_len -1 and h_ls[max_ind+d+1]==h_ls[max_ind]:
        d+=1
    h_ls[max_ind:max_ind+d+1] =h_ls[max_ind:max_ind+d+1]-1
    n+=1

print(n)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
h = np.array(list(map(int, input().split())))
h_max = max(h)

ans = 0
for i in range(h_max):
    tmp = list(h >= 1)
    a = tmp.index(True)
    count = 0
    for j in range(a, len(tmp)-1):
        if tmp[j] == True and tmp[j+1] == False:
            count += 1
    if tmp[-1] == True:
        count += 1

    ans += count
    h -= 1

print(ans)

Submission status: Accepted

Solution code:
def decrease_height_by_one(hs):
    highest_indexes = [i for i, h in enumerate(hs) if h == max(hs)]
    is_indexes_discontinuous = (i1+1 < i2 for i1, i2 in
                                zip(highest_indexes, highest_indexes[1:]))
    for index in highest_indexes:
        hs[index] -= 1
    return 1 + sum(is_indexes_discontinuous)

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

n = 0
while max(hs):
  n += decrease_height_by_one(hs)
print(n)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
cnt = 0
def water(lst):
    global cnt
    if len(lst) == 0:
        return
    if len(lst) == 1:
        cnt = cnt + lst[0]
        return
    
    m = min(lst)
    cnt += m
    
    lst = [i - m for i in lst]
    while 0 in lst:
        water(lst[:lst.index(0)])
        lst = lst[lst.index(0)+1:]
    water(lst)


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

Submission status: Accepted

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

for i in range(n):
    a+=max(l[i+1]-l[i],0)

print(a)

Submission status: Accepted

Solution code:
n,a=open(0);l=a.split();print(sum(max(int(j)-int(i),0)for i,j in zip(["0"]+l,l)))

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split());print(sum(max(j-i,0) for i,j in zip([0]+a,a)))

Submission status: Accepted

Solution code:
n=int(input())
l=[0]+list(map(int,input().split()))
a=0
for i in range(n):
  a+=max(l[i+1]-l[i],0)
print(a)

Submission status: Accepted

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

h_min = min(h_list)
for i in range(N):
    h_list[i] -= h_min
ans = h_min
judge = 0
while judge == 0:
    for i in range(N):
        if h_list[i] != 0:
            r = i
            break
        r = -1
    if r == -1:
        break
    for j in range(r,N):
        if h_list[j] == 0:
            l = j-1
            break
        l = j
    temp = h_list[r:l+1]
    temp_min = min(temp)
    for k in range(r,l+1):
        h_list[k] -= temp_min
    ans += temp_min
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10**5)

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


# 貪欲に極大区間に対して水やりする
def f(y):
    L = next(
        (
            i
            for i, x in enumerate(y)
            if x > 0
        ),
        N
    )
    R = next(
        (
            i
            for i, x in enumerate(y[L:], L)
            if x == 0
        ),
        N
    )
    return (
        0 if L == N else
        1 + f(
            [x for x in y[:L]] +
            [x - 1 for x in y[L:R]] +
            [x for x in y[R:]]
        )
    )


ans = f(h)

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n = int(input())
	h = list(map(int,input().split()))
	ans=0
	while sum(h)>0:
		mx = max(h)
		t = zip(h)
		ans+=t.count(mx)
		for i in range(n):
			if(h[i]==mx):
				h[i]-=1
	print(ans)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Accepted

Solution code:
import copy

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

ctr = 0
while H:
	# print(H)
	if H[0] == 0:
		H.pop(0)
	else:
		H[0] -= 1
		for i in range(1, len(H)):
			if H[i] != 0:
				H[i] -= 1
			else:
				break
		ctr += 1
	
				
print(ctr)

Submission status: Accepted

Solution code:
n = int(input())
h = list(map(int,input().split()))
cnt2=0
while sum(h)>0:
  cnt=0
  if 0 in h:
    for i in range(1,n):
      if h[i]==0 and h[i-1]>0 and sum(h[i:])!=0:
        cnt+=1
  for i in range(n):
    if h[i]>0:
      h[i]-=1
  cnt2=cnt2+cnt+1

print(cnt2)

Submission status: Accepted

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

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

Submission status: Accepted

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

ans = 0

cnt = 0

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
h = list(map(int,input().split()))
c = 0
while h != [0]:
    b = max(h)
    if b == 0:break
    newh = []
    con = False
    for i in range(len(h)):
        if h[i] != b:
            newh.append(h[i])
            con = False
        else:
            if con == False:
                newh.append(b)
                con = True
    for j in range(len(newh)):
        if newh[j] == b:
            newh[j] -= 1
            c += 1
    h = newh
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = LI()
    a.sort()
    print(a[0]*a[1]//2)  
    return

#B
def B():
    d = defaultdict(int)
    s = II()
    def f(n):
        if n % 2:
            return 3 * n + 1
        return n // 2
    i = 1
    while not d[s]:
        d[s] = 1
        s = f(s)
        i += 1
    print(i)
    return

#C
def C():
    n = II()
    h = LI()
    ans = h[0]
    for i in range(n - 1):
        ans += max(0, h[i + 1] - h[i])
    print(ans)
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
N = int(input())
lst = list(map(int, input().split()))
cnt = 0
while sum(lst) > 0:
    idx0s = [idx for idx, i in enumerate(lst) if i == 0]
    if len(idx0s) == 0:
        for i in range(N):
            lst[i] -= 1
        cnt += 1
    else:
        if idx0s[0] != 0 and sum(lst[:idx0s[0]]) > 0:
            for i in range(idx0s[0]):
                lst[i] -= 1
            cnt += 1
        if idx0s[-1] != len(lst) - 1 and sum(lst[idx0s[-1]+1:]) > 0:
            for i in range(idx0s[-1]+1, len(lst)):
                lst[i] -= 1
            cnt += 1
        if len(idx0s) >= 2:
            for i in range(len(idx0s)-1):
                l = idx0s[i]
                r = idx0s[i+1]
                if l+1 < r:
                    for i in range(l+1, r):
                        lst[i] -= 1
                    cnt += 1


print(cnt)

Submission status: Accepted

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

res = h[0]
for i in range(1, n):
    h_ = h[i] - h[i-1]
    if h_ > 0:
        res += h_

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#ABC116C
import sys

n = int(input())
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))

sum=hoge[0]
for i in range(1,n):
	if(hoge[i]>hoge[i-1]):
		sum += (hoge[i]-hoge[i-1])
print(sum)

Submission status: Accepted

Solution code:
a = int(input())
h_list = input().split()
h_list = [int(i) for i in h_list]


def grand_garden(h_list, count):
    hana_list = []
    kari_list = []
    if len(h_list) == 0:
        return
    for i in range(len(h_list)):
        if h_list[i] != 0:
            kari_list.append(h_list[i])
        else:
            hana_list.append(kari_list)
            kari_list = []
    if kari_list != []:
        hana_list.append(kari_list)
    for u in hana_list:
        if len(u) == 0:
            continue
        min_index = u.index(min(u))
        count.append(u[min_index])
        u = [i - u[min_index] for i in u]
        grand_garden(u, count)


count = []
grand_garden(h_list, count)
print(sum(count))

Submission status: Accepted

Solution code:
# ABC 116 C

N = int(input())

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

def chomp0(arr):
    while len(arr) != 0 and arr[0] == 0:
        del arr[0]

    while len(arr) != 0 and arr[-1] == 0:
        del arr[-1]

    return arr

def solve(arr):
    arr = chomp0(arr)

    if len(arr) == 0:
        return 0

    ans = 0

    num0 = arr.count(0)
    if num0 != 0:
        for _ in range(num0):
            idx = arr.index(0)
            ans += solve(arr[:idx])
            arr = arr[idx+1:]

    minVal = min(arr)
    ans += minVal
    for i in range(len(arr)):
        arr[i] -= minVal

    if arr.count(0) != len(arr):
        ans += solve(arr)

    return ans

print(solve(h))

Submission status: Accepted

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

TMP = 1e9

ans = 0
while True:
    tmp = TMP
    left = -1
    right = 0
    for i in range(N):
        if H[i] != 0:
            left = i
            break
    if left == -1:
        break

    for i in range(left, N):
        if H[i] != 0:
            right = i
        else:
            break

    for i in range(left, right + 1):
        tmp = min(tmp, H[i])

    for i in range(left, right + 1):
        H[i] -= tmp

    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n = int(input())
nums = get_nums_l()

check = [False] * n
ans = 0

def need():
    for n in nums:
        if n > 0:
            return True
    return False

while need():
    left = -1
    right = -1
    for i,x in enumerate(nums):
        if x != 0:
            left = i
            break
    
    min_ = nums[left]
    prev = left
    for i in range(left+1, n):
        if nums[i] > 0:
            min_ = min(min_, nums[i])
            prev = i
        else:
            break
    right = prev

    for i in range(left, right+1):
        nums[i] -= min_
    ans += min_

    
print(ans)

Submission status: Accepted

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

def mizuyari(flo):
	cnt = 0
	if len(flo) == 0:
		return 0

	if 0 in flo:
		non = flo.index(0)
		left = flo[:non]
		right = flo[non+1:]
		cnt += (mizuyari(left) + mizuyari(right))
	else:
		minheight = min(flo)
		for i in range(len(flo)):
			flo[i] -= minheight
		cnt += mizuyari(flo) + minheight

	return cnt

ans = mizuyari(flo)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect


def mizuyari(flowers):
    if flowers == []:
        return 0
    # print(flowers)
    minheight = min(flowers)
    if minheight == 0:
        if max(flowers) == 0:
            return 0
        leftindex = flowers.index(0)
        # print("分割" + str(leftindex))
        if leftindex == len(flowers):
            count = mizuyari(flowers[0:leftindex])
        else:
            count = mizuyari(flowers[0:leftindex]) + \
                mizuyari(flowers[leftindex+1:])

        return count
    else:
        count = mizuyari([i - minheight for i in flowers]) + minheight
        return count


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

print(mizuyari(h_list))

Submission status: Accepted

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

x.append(0)

cnt=0

while sum(x)>0:
	for i in range(n):
		if x[i]>0:
			for j in range(i+1,n+1):
				if x[j]==0:
					for k in range(i,j):
						x[k]=x[k]-1
					cnt+=1
					break
			break

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
H = list(map(int, input().split()))
cnt = 0
while any(H):
  st = False
  for i, v in enumerate(H):
#    print(H, cnt)
#    print(v)
    if v > 0:
      st = True
      H[i] -= 1
#      print(H)
    else:
      if st == True:
        cnt += 1
        st = False
        break
  if st == True:
    cnt += 1
    st = False
print(cnt)

Submission status: Accepted

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

def solve(A):
    ret = 0
    if len(A) == 0:
        return 0

    if 0 in A:
        idx = A.index(0)
        left = A[:idx]
        right = A[idx+1:]
        ret += solve(left)
        ret += solve(right)
    else:
        min_a = min(A)
        for i in range(len(A)):
            A[i] -= min_a
        ret += solve(A) + min_a

    return ret

ans = solve(A)
print(ans)