Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Finally a monsoon has come. According to the Meteorological Department, there will be rain in the upcoming N days in the city. Initially, the water level of the city is zero millimetres. The amount of rain on the i-th day can be described by an integer A_{i} as follows:
If A_{i} > 0, the water level of the city increases by A_{i} millimetres on the i-th day.
If A_{i} = 0, there is no rain on the i-th day. The water level of the city decreases by D millimetres on such a day. However, if the water level is less than D millimetres before the i-th day, then it becomes zero instead.

There will be a red alert in the city if the water level becomes strictly greater than H millimetres on at least one of the N days. Determine if there will be a red alert.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, D and H.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing the string "YES" if there will be a red alert or "NO" otherwise.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$1 ≤ N, D ≤ 10^{2}$
$0 ≤ A_{i} ≤ 10^{2}$ for each valid $i$
$1 ≤ H ≤ 10^{4}$

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
4
4 2 6
1 3 0 2
2 1 100
1 100
4 2 3
1 2 0 2
3 7 10
5 3 9 

----- Sample Output 1 ------ 
NO
YES
NO
YES
----- explanation 1 ------ 
Example case 1:
- On the first day, the water level of the city increases to $1$ millimtre.
- On the second day, the water level increases by $3$ millimeters and becomes $1 + 3 = 4$ millimtres.
- On the third day, there is no rain in the city, so the water level decreases by $D = 2$ millimtres and becomes $4 - 2 = 2$ millimtres.
- On the fourth day, the water level increases by $2$ millimtres and becomes $2 + 2 = 4$ millimtres.

There will be no red alert in the city because the water level does not exceed $H = 6$ millimtres on any of the four days.

Example case 2: The water level of the city on the $2$-nd day is equal to $101$ millimtres, which is greater than $H = 100$ millimtres, so there will be a red alert in the city.

Example case 3: The water levels of the city on the four days are $[1, 3, 1, 3]$. The water level is equal to $H = 3$ millimtres on the second and fourth day, but it does not exceed the threshold.

Example case 4: There will be a red alert in the city on the $3$-rd day.

Source: codechef | Difficulty: EASY
Tags: Complete search

Implementation

Ad-hoc


Solutions:
for _ in range(int(input())):
	(N, D, H) = input().split()
	(N, D, H) = (int(N), int(D), int(H))
	A = list(map(int, input().split()))
	sum = 0
	sumflag = False
	for i in A:
		if i == 0:
			sum -= D
			if sum < 0:
				sum = 0
		if i > 0:
			sum += i
		if sum > H:
			sumflag = True
	if sumflag:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	flag = 0
	s = 0
	for i in range(n):
		s = s + l[i]
		if l[i] == 0 and s >= d:
			s = s - d
		elif l[i] == 0 and s < d:
			s = 0
		elif s > h:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	count = 0
	b = 0
	for i in y:
		if i > 0:
			count = count + i
			if count > x[2]:
				b = 1
				break
		if i == 0:
			count = count - x[1]
			if count < 0:
				count = 0
			if count > x[2]:
				b = 1
				break
	if b == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	s = 0
	for j in range(n):
		if a[j] > 0:
			s += a[j]
		elif a[j] == 0 and s <= d:
			s = 0
		else:
			s -= d
		if s > h:
			break
		else:
			continue
	if s > h:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, d, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	w = 0
	flag = 0
	for a in arr:
		if a > 0:
			w += a
			if w > h:
				flag = 1
				break
		elif a == 0:
			if w >= d:
				w -= d
			else:
				w = 0
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	water_level = 0
	red_alert = False
	for i in range(n):
		if a[i] == 0:
			water_level = max(water_level - d, 0)
		else:
			water_level += a[i]
		if water_level > h:
			red_alert = True
			break
	if red_alert:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(d, n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	p = 0
	for i in x:
		if i != 0:
			p += i
			if p > m:
				break
		elif i == 0:
			if p > n:
				p = p - n
			elif p < n:
				p = 0
	if p > m:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	li = 0
	for i in l:
		if i > 0:
			li += i
			if li > h:
				break
		elif i == 0:
			if li >= d:
				li -= d
			elif li < d:
				li = 0
	if li > h:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	lim = 0
	for i in l:
		if i > 0:
			lim += i
			if lim > h:
				break
		elif i == 0:
			if lim >= d:
				lim -= d
			elif lim < d:
				lim = 0
	if lim > h:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = [int(x) for x in input().split()]
	c = 0
	ans = 'NO'
	for i in a:
		if i:
			c += i
			if c > h:
				ans = 'YES'
				break
		else:
			c = max([0, c - d])
	print(ans)


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	waterlevel = 0
	for i in range(n):
		if arr[i] == 0 and waterlevel > d:
			waterlevel -= d
		elif arr[i] == 0 and waterlevel < d:
			waterlevel = 0
		elif arr[i] > 0:
			waterlevel += arr[i]
		if waterlevel > h:
			print('YES')
			break
		elif i == n - 1:
			print('NO')


t = int(input())
while t != 0:
	(n, d, h) = map(int, input().split())
	list = [int(x) for x in input().split()]
	sum = 0
	c = 0
	for i in list:
		if i != 0:
			sum += i
			if sum > h:
				print('YES')
				c = 1
				break
		elif i == 0 and sum < d:
			sum = 0
			if sum > h:
				print('YES')
				c = 1
				break
		else:
			sum -= d
			if sum > h:
				print('YES')
				c = 1
				break
	if c == 0:
		print('NO')
	t -= 1


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	red_alert = False
	level = 0
	for i in l:
		if i != 0:
			level = level + i
			if level > h:
				print('YES')
				red_alert = True
				break
		elif i == 0 and level < d:
			level = 0
			if level > h:
				print('YES')
				red_alert = True
				break
		else:
			level = level - d
			if level > h:
				print('YES')
				red_alert = True
				break
	if red_alert == False:
		print('NO')


try:
	for _ in range(int(input())):
		(N, D, H) = map(int, input().split())
		A = list(map(int, input().split()))
		a = 0
		flag = 0
		for i in range(N):
			if A[i] > 0:
				a += A[i]
				if a > H:
					flag = 1
			elif A[i] == 0:
				a -= D
				if a < 0:
					a = 0
		if flag == 1:
			print('YES')
		else:
			print('NO')
except:
	pass


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	water = 0
	flag = 0
	for i in range(n):
		if a[i] == 0 and water < d:
			water = 0
		elif a[i] == 0 and water > d:
			water -= d
		elif a[i] > 0:
			water += a[i]
		if water > h:
			flag = 1
			break
	print('YES' if flag else 'NO')


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	r = list(map(int, input().split()))
	water = 0
	red = 0
	for i in r:
		if i > 0:
			water += i
		elif i == 0:
			if water >= d:
				water -= d
			else:
				water = 0
		if water > h:
			red = 1
	if red == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	level = 0
	for i in arr:
		if i > 0:
			level += i
		else:
			level = max(level - d, 0)
		if level > h:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	A = list(map(int, input().split()))
	x = 0
	flag = False
	for i in A:
		if i == 0:
			x = 0 if x - b < 0 else x - b
		else:
			x += i
		if x > c:
			flag = True
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	ok = False
	lv = 0
	ls = list(map(int, input().split()))
	for i in range(n):
		if ls[i] == 0:
			if lv < d:
				lv = 0
			else:
				lv -= d
		else:
			lv += ls[i]
		if lv > h:
			ok = True
	print('YES' if ok else 'NO')


test = int(input())
for i in range(test):
	(n, d, h) = map(int, input().split())
	List = list(map(int, input().split()))
	water = 0
	for i in range(n):
		if List[i] == 0 and water > d:
			water = water - d
		elif List[i] == 0 and water < d:
			water = 0
		elif List[i] > 0:
			water = water + List[i]
		if water > h:
			print('YES')
			break
		elif i == n - 1:
			print('NO')


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	n = [int(a) for a in input().split()]
	s = 0
	for j in range(a):
		if n[j] != 0:
			s = s + n[j]
		else:
			s = s - b
			if s < 0:
				s = 0
		if s > c:
			print('YES')
			break
		elif j == a - 1:
			print('NO')


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	level = 0
	alarm = 'NO'
	for v in a:
		if v > 0:
			level += v
			if level > h:
				alarm = 'YES'
				break
		else:
			level = max(level - d, 0)
	print(alarm)


for tc in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	level = 0
	redalert = 'NO'
	for i in range(n):
		if a[i] > 0:
			level += a[i]
		else:
			level -= d
			if level <= 0:
				level = 0
		if level > h:
			redalert = 'YES'
	print(redalert)


for _ in range(int(input())):
	(n, d, h) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	flag = False
	level = 0
	for i in arr:
		if i > 0:
			level += i
			if level > h:
				flag = True
		if i == 0:
			level -= d
			if level <= 0:
				level = 0
	if flag == True:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, d, h) = map(int, input().split())
	curr = 0
	c = 0
	l = list(map(int, input().split()))
	for x in l:
		if x != 0:
			curr += x
			if curr > h:
				c = 1
				break
		else:
			curr = curr - d
			if curr <= 0:
				curr = 0
	if c == 1:
		print('YES')
	else:
		print('NO')


tc = int(input())
for i in range(tc):
	(n, d, h) = map(int, input().split())
	l1 = list(map(int, input().split()))
	sum = 0
	c = 0
	for i in l1:
		if i != 0:
			sum = sum + i
			if sum >= h:
				c = c + 1
		elif sum < d:
			sum = 0
		else:
			sum = sum - d
	if c > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, d, h) = map(int, input().split())
	A = list(map(int, input().split()))
	sum1 = 0
	count = 0
	for x in range(n):
		if A[x] == 0:
			if sum1 < d:
				sum1 = 0
			else:
				sum1 = sum1 - d
		else:
			sum1 = sum1 + A[x]
			if sum1 > h:
				count = count + 1
	if count > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, d, h) = map(int, input().split())
	array = list(map(int, input().split()))
	sum1 = 0
	c = 0
	for i in array:
		if i == 0:
			if sum1 < d:
				sum1 = 0
			else:
				sum1 -= d
		else:
			sum1 += i
		if sum1 > h:
			c += 1
	if c > 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(n, d, h) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	r = 0
	for i in a:
		if i != 0:
			r += i
			if r > h:
				print('YES')
				break
		elif r < d:
			r = 0
		else:
			r -= d
	else:
		print('NO')


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	red = False
	for i in range(n):
		if a[i] > 0:
			c += a[i]
		elif a[i] == 0:
			if c > d:
				c -= d
			else:
				c = 0
		if c > h:
			red = True
	if red == True:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	r = 0
	red = False
	for i in range(n):
		if a[i] == 0:
			r -= d
			if r < 0:
				r = 0
		else:
			r += a[i]
		if r > h:
			red = True
			break
	if red == True:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = False
	c = 0
	for i in range(n):
		if a[i] > 0:
			c = c + a[i]
		elif c < d:
			c = 0
		else:
			c = c - d
		if c > h:
			ans = True
			print('YES')
			break
	if not ans:
		print('NO')


def solve(n, d, h, a):
	water = 0
	for i in range(n):
		if a[i] == 0:
			water -= d
			if water < 0:
				water = 0
		else:
			water += a[i]
			if water > h:
				return 'YES'
	return 'NO'
for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = [int(j) for j in input().split()]
	print(solve(n, d, h, a))


t = int(input())
for i in range(t):
	(n, d, h) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	count = 0
	for i in a:
		if i > 0:
			count += i
		elif count - d > 0:
			count -= d
		else:
			count = 0
		if count > h:
			print('YES')
			break
	if count <= h:
		print('NO')


def redalert(n, d, h, a):
	s = 0
	for i in a:
		if i > 0:
			s += i
		elif s - d < 0:
			s = 0
		else:
			s = s - d
		if s > h:
			return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	r = redalert(n, d, h, a)
	print(r)


for _ in range(int(input())):
	(n, d, H) = map(int, input().split())
	a = list(map(int, input().split()))
	h = 0
	m = 0
	for val in a:
		if val != 0:
			h += val
			if h > H:
				m = 1
				break
		elif h - d < 0:
			h = 0
		else:
			h -= d
	print('YES' if h > H else 'NO')


for i in range(int(input())):
	(n, d, h) = map(int, input().split())
	list1 = list(map(int, input().split()))
	okay = 0
	sum1 = 0
	for k in list1:
		if sum1 > h:
			okay = 1
			break
		if k == 0:
			if sum1 - d < 0:
				sum1 = 0
			else:
				sum1 -= d
		else:
			sum1 += k
	if sum1 > h:
		okay = 1
	if okay == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for x in range(T):
	(N, D, H) = map(int, input().split())
	A = list(map(int, input().split()))
	level = int('0')
	for lvl in A:
		if lvl != 0:
			level += lvl
		elif level < D:
			level = 0
		else:
			level -= D
		if level > H:
			print('YES')
			break
	else:
		print('NO')


for t in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	l = 0
	for x in a:
		if x > 0:
			l += x
		elif l < d:
			l = 0
		else:
			l -= d
		if l > h:
			break
	if l > h:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	m = list(map(int, input().split()))
	sum = 0
	for j in m:
		if j > 0:
			sum += j
		elif sum < b:
			sum = 0
		else:
			sum -= b
		if sum > c:
			break
	if sum > c:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, d, h) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = 0
	for i in range(n):
		if a[i] > 0:
			b += a[i]
		elif b < d:
			b = 0
		else:
			b -= d
		if b > h:
			break
	if b > h:
		print('YES')
	else:
		print('NO')


def bulk_input():
	return [int(j) for j in input().split()]

def problem():
	(n, d, h) = bulk_input()
	arr = bulk_input()
	(water_level, red_alert) = (0, False)
	for it in range(len(arr)):
		if arr[it] == 0:
			water_level = max(water_level - d, 0)
		else:
			water_level += arr[it]
		if water_level > h:
			red_alert = True
			break
	if red_alert:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	problem()


t = int(input())
for i in range(t):
	c = 0
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	for j in a:
		if j != 0:
			c += j
		else:
			c -= d
			if c < 0:
				c = 0
		if c > h:
			print('YES')
			break
	else:
		print('NO')


def Solution(l, n, d, h):
	level = 0
	for i in l:
		if i == 0:
			level = max(level - d, 0)
		else:
			level += i
			if level > h:
				return 'YES'
	return 'NO'
for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	print(Solution(l, n, d, h))


for _ in range(int(input())):
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	w = 0
	flag = 0
	for i in l:
		if i == 0:
			if w < d:
				w = 0
			else:
				w = w - d
		else:
			w += i
		if w > h:
			flag = 1
			break
	print('YES' if flag else 'NO')


for i in range(int(input())):
	s = 0
	(n, d, h) = map(int, input().split())
	l = list(map(int, input().split()))
	for j in range(len(l)):
		if l[j] != 0:
			s = s + l[j]
			if s > h:
				print('YES')
				break
		elif s > d:
			s = s - d
		else:
			s = 0
	if s <= h:
		print('NO')


for _ in range(int(input())):
	(N, D, H) = map(int, input().split())
	A = list(map(int, input().split()))
	cn = 0
	X = 0
	for i in A:
		if i == 0:
			cn = max(0, cn - D)
		elif i != 0:
			cn = cn + i
			if cn > H:
				X = 1
	print('YES' if X == 1 else 'NO')


for k in range(int(input())):
	(n, d, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	for j in range(n):
		if arr[j] == 0:
			count -= d
			if count < 0:
				count = 0
		else:
			count += arr[j]
			if count > h:
				print('YES')
				break
	if count <= h:
		print('NO')


for i in range(int(input())):
	(a, b, e) = list(map(int, input().split()))
	d = list(map(int, input().split()))
	c = 0
	l = 0
	for i in d:
		if i != 0:
			c += i
			if c > e:
				l = 1
		elif c > b:
			c -= b
		else:
			c = 0
	if l == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, d, h) = map(int, input().split())
	arr = list(map(int, input().split()))
	f = False
	level = 0
	for i in range(n):
		if arr[i] > 0:
			level = level + arr[i]
		elif arr[i] == 0 and level >= d:
			level = level - d
		elif arr[i] == 0 and level < d:
			level = 0
		if level > h:
			f = True
			break
	if f:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, d, h) = map(int, input().split())
	a = list(map(int, input().split()))
	temp = 0
	for ele in a:
		if temp > h:
			break
		elif ele != 0:
			temp += ele
		elif temp < d:
			temp = 0
		else:
			temp -= d
	if temp > h:
		print('YES')
	else:
		print('NO')