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: Runtime Error

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)+" "+str(rightindex))
        count = mizuyari(flowers[0:leftindex])+mizuyari(flowers[leftindex:])
        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: Runtime Error

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

def solve_range(h, start):
	ans = 0
	for i in range(start, len(h)):
		if h[i] > 0:
			h[i] -= 1
		else:
			break
	start = min((i for i in range(len(h)) if h[i] >0), default = -1)
	if start == -1:
		return ans+1
	else:
		ans += solve_range(h, start) + 1
		return ans

start = min((i for i in range(len(h)) if h[i] > 0), default = -1)
a=solve_range(h,start)
print(a)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int f(vector<int> v, int i, int a) {
    vector<int>::iterator maxIt = max_element(v.begin(), v.end());
    vector<int>::iterator minIt = min_element(v.begin(), v.end());
    if (v.size() == 0){
        return a;
    }
    if(*maxIt == *minIt) {
        return a + (*minIt) - i;
    }
    a+=*minIt-i;
    i = *minIt;
    size_t minIndex = distance(v.begin(), minIt);
    if (minIndex == 0) {
        vector<int> vec;
        copy(next(v.begin()), v.end(), back_inserter(vec));
        a = f(vec, i, a);
    } else if (minIndex == v.size()) {
        vector<int> vec;
        copy(v.begin(), prev(v.end()), back_inserter(vec));
        a = f(vec, i, a);
    } else {
        vector<int> vec1;
        copy(v.begin(), minIt, back_inserter(vec1));
        a = f(vec1, i, a);
        vector<int> vec2;
        copy(next(minIt), v.end(), back_inserter(vec2));
        a = f(vec2, i, a);
    }
    return a;
}


int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i=0; i<n; i++) {
        cin >> v[i];
    }
    int a = f(v, 0, 0);

    return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
H = np.array(input().split(), dtype=np.int32)

def myfunc(left, right):
    if right<left:
        return 0
    idx = left+H[left:right+1].argmin()
    m = H[idx]
    H[left:right+1]-=m
    return m+myfunc(left, idx-1)+myfunc(right, idx+1)

print(myfunc(0, N-1))

Submission status: Runtime Error

Solution code:
N = int(input())
H = np.array(input().split(), dtype=np.int32)

def myfunc(left, right):
    if right<left:
        return 0
    idx = left+H[left:right+1].argmin()
    m = H[idx]
    H[left:right+1]-=m
    return m+myfunc(left, idx-1)+myfunc(right, idx+1)

print(myfunc(0, N-1))

Submission status: Runtime Error

Solution code:
def all_water(h_list):
  if len(h_list) == 0:
    return 0
  min_h = min(h_list)
  new_list = [x - min_h for x in h_list]
  i = new_list.index(0)
  return min_h + all_water(new_list[:i]) + all_water(new_list[i+1:])

n = input()

height = list(map(int,input().split(" ")))

print(allwater(height))

Submission status: Runtime Error

Solution code:
def all_water(h_list):
  if len(h_list) == 0:
    return 0
  min_h = min(h_list)
  new_list = list(map(lambda x:x-minh, h_list))
  i = new_list.index(0)
  return min_h + all_water(new_list[:i]) + all_water(new_list[i+1:])

n = input()

height = list(map(int,input().split(" ")))

print(allwater(height))

Submission status: Runtime Error

Solution code:
def all_water(h_list):
  if len(h_list) == 0:
    return 0
  min_h = min(h_list)
  h_list = list(map(lambda x:x-minh, h_list))
  i = h_list.index(0)
  return min_h + all_water(h_list[:i]) + all_water(h_list[i+1:])

n = input()

height = list(map(int,input().split(" ")))

print(allwater(height))

Submission status: Runtime Error

Solution code:
N = int(input())
lst = list(map(int, input().split()))
boolean = False
updated_lst = []
minimum = min(lst)
min_num = 0
for i in lst:
  num = i % minimum
  if (i != minimum):
    updated_lst.append(num)
  else:
    updated_lst.append(minimum)
    min_num += 1
  if (num % 2 == 1):
    boolean = True

if (min_num == len(lst)):
  print(minimum)
else:
  if (boolean):
    print(1)
  else:
    print(2)

Submission status: Runtime Error

Solution code:

import numpy as np
n = int(input())
h = list(map(int, input().split()))
h = np.array(h)

count = 0

for k in range(max(h)):
    j = 0
    for i in range(0,len(h)):
        if h[i]==0 and i!=j:
            h[j:i] = h[j:i] -1
            count = count+1
            j = i + 1
        elif i ==len(h)-1 and h[n]!=0:
            count = count+1
            h[j:]= h[j:]-1
        elif h[i]==0 and i==j:
            j = i+1
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
h = list(map(int,input().split()))
if max(h) == min(h):
    ans = h[0]

else:
    same = []
    for i in range(N-1):
        if h[i] == h[i+1]:
            same.append(i)
    
    if len(same) >= 1:
        for k in range (len(same)):
            del h[same[k]]
            for j in range(len(same)):
                same[j] -= 1
    
    N = len(h)

    lmin = [] #極小値のリスト
    lmax = [] #極大値のリスト

    if N >=3:
        if max(h) != min(h):
            for i in range(1,N-1):
                if (h[i] > h[i-1]) and (h[i] > h[i+1]):
                    lmax.append(h[i])
            
            for k in range(1,N-1):
                if (h[k] < h[k-1]) and (h[k] < h[k+1]):
                    lmin.append(h[k])

            if h[0] == h[1]:
                lmax.append(h[j])
                
            if h[j] > h[j -1]:
                lmax.append(h[j])
                  
            if (len(lmax) == 1) :
                ans = max(h)

            else:
                ans = sum(lmax) - sum(lmin)
        else:
            ans = h[0]

    if N == 2:
        ans = max(h)

    if N == 1:
        ans = h[0]

#print(lmax)
#print(lmin)
print(ans)

Submission status: Runtime Error

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

lmin = [] #極小値のリスト
lmax = [] #極大値のリスト

for i in range(1,N-1):
    if (h[i] >= h[i-1]) and (h[i] > h[i+1]):
        lmax.append(h[i])
    
for k in range(1,N-1):
    if (h[k] <= h[k-1]) and (h[k] < h[k+1]):
        lmin.append(h[k])

if h[0] > h[1]:
    lmax.append(h[0])
if h[N-1] > h[N-2]:
    lmax.append(h[N-1])

ans = sum(lmax) - sum(lmin)

print(ans)

Submission status: Runtime Error

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

lmin = [] #極小値のリスト
lmax = [] #極大値のリスト

for i in range(i,N-1):
    if (h[i] >= h[i-1]) and (h[i] > h[i+1]):
        lmax.append(h[i])
    
for k in range(i,N-1):
    if (h[i] <= h[i-1]) and (h[i] < h[i+1]):
        lmin.append(h[i])

ans = sum(lmax) - sum(lmin)

print(ans)

Submission status: Runtime Error

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

lmin = [] #極小値のリスト
lmax = [] #極大値のリスト

for i in range(1,N-1):
    if (h[i] >= h[i-1]) and (h[i] > h[i+1]):
        lmax.append(h[i])
    
for k in range(1,N-1):
    if (h[i] <= h[i-1]) and (h[i] < h[i+1]):
        lmin.append(h[i])

ans = sum(lmax) - sum(lmin

print(ans)

Submission status: Runtime Error

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

Hk = set()
for h in H:
  Hk.add(h)

def po(h, s, e):
  if h >= Hk[-1]:
    return 1
  posS = s
  hit = False
  cnt = 0
  for posE in range(s, e+1):
    if posE >= e or H[posE] <= Hk[h]:
      hit or= (posE < e)
	if posS < posE:
      cnt += po(h+1, posS, posE)
  if hit:
    cnt += 1
  return cnt

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int, input().split()))
if n == 1:
    print(h[0])
else:
    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: Runtime Error

Solution code:
    n = int(input())
    arr = list(map(int, input().split()))
    print(max(arr) * n - sum(arr) + min(arr))

Submission status: Runtime Error

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

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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
#include<stdio.h>

int main() {
	int n, h[100], i, flg, cnt, stop;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &h[i]);

	cnt = 0;
	while (1) {
		flg = 0;
		stop = 1;
		for (i = 0; i < n; i++) {
			if (h[i] > 0) {
				if (flg) h[i]--;
				else {
					flg = 1;
					stop = 0;
					cnt++;
					h[i]--;
				}
			}
			else flg = 0;
		}
		if (stop) break;
	}

	printf("%d", cnt);
}

Submission status: Runtime Error

Solution code:
# coding: utf-8

n = int(input())
h = list(map(int, input().split()))
m = min(h)

c = 0
for i in range(n-1):
    if h[i] > h[i+1]:
        c += h[i] - m
        x = h[i+1]
        if i == n - 2:
             c += m
    elif i == n - 2:
        c += h[i+1] - x -m

print(c)

Submission status: Runtime Error

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=[i-1 if i>0 else 0 for i in h]
        sum+=1
    else:
        count0=[i for i, j in enumerate(h) if j==0]
        a=count0.copy() #copy()をつけないとaを変えるとcount0も変わる
        b=count0.copy()
        del a[0]
        del b[-1]
        c=[x-y for(x,y) in zip(a,b)]　#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: Runtime Error

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)