Постановка задачи:

Наконец-то наступил сезон дождей. По данным метеорологического управления, в ближайшие N дней в городе будут дожди. Изначально уровень воды в городе равен нулю миллиметрам. Количество дождя в i -й день можно описать целым числом Ai.

следующее:

  • If Ai>0

уровень воды в городе увеличивается на Ai миллиметров на i

  • -й день.
  • If Ai=0

, в i -й день дождя нет. Уровень воды в городе в такой день понижается на D миллиметра. Однако, если уровень воды меньше D миллиметров до i

  • -й день, тогда вместо этого он становится равным нулю.

Если уровень воды станет строго выше H, в городе появится красный сигнал тревоги.

миллиметров хотя бы на одном из N

дней. Определите, будет ли предупреждение красного цвета.

Формат ввода

  • Первая строка входных данных содержит единственное целое число T.

обозначает количество тестовых случаев. Описание для T

  • ниже приведены тестовые примеры.
  • Первая строка каждого тестового примера содержит три целых числа, разделенных пробелами N.

, D и H

  • Вторая строка содержит N

целые числа, разделенные пробелами A 1, A 2,…, AN

Формат вывода

Для каждого тестового примера выведите одну строку, содержащую строку "YES", если будет красный сигнал предупреждения, или "NO" в противном случае.

  • 1≤T≤103
  • 1≤N,D≤102
  • 0≤Ai≤102

для каждого действительного i

  • 1≤H≤104

Подзадачи

Подзадача №1 (100 баллов): исходные ограничения

Пример ввода 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

Пример вывода 1

NO
YES
NO
YES

Объяснение

Пример 1:

  • В первый день уровень воды в городе повышается до 1
  • миллиметр.
  • На вторые сутки уровень воды повышается на 3

миллиметров и становится 1 + 3 = 4

  • миллиметры.
  • На третьи сутки в городе нет дождя, поэтому уровень воды понижается на D = 2.

миллиметров и становится 4−2 = 2

  • миллиметры.
  • На четвертые сутки уровень воды повышается на 2

миллиметров и становится 2 + 2 = 4

  • миллиметры.

В городе не будет красного оповещения, потому что уровень воды не превышает H = 6.

миллиметров в любой из четырех дней.

Пример случая 2: Уровень воды в городе на 2

-й день равен 101 миллиметру, что больше H = 100

миллиметров, значит в городе будет красная тревога.

Пример 3: Уровень воды в городе за четыре дня составляет [1,3,1,3].

. Уровень воды равен H = 3.

миллиметров на второй и четвертый день, но не превышает порогового значения.

Пример случая 4: в городе 3-го

  • день третий.

Код и алгоритм

/* author : @akash */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mod 1000000007
#define ld long double
void solve()
{
   int N;
   int D;
   int H;
   int RED=0;
   cin>>N>>D>>H;
   int A[N];
   for(int i=0;i<N;++i)
   {
    cin>>A[i];
   }
int water=0;
   for(int i=0;i<N;++i)
   {
    if(A[i]>0)
    {
     water+=A[i];
     if(water>H)
     {
      RED=1;
      break;
     }
    }
    if(A[i]==0)
    {
     if(water<D)
     {
      water=0;
     }
     else
     {
      water-=D;
     }
    }
   }
   if(RED)
   {
    cout<<"YES";
   }
   else
   {
    cout<<"NO";
   }
}
int main()
{
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 int t;
 cin>>t;
 while(t--)
 {
            solve();
            cout<<"\n";     
 }
 return 0;
}
// time complexity of this algorithm is : T(n)=O(n)

Спасибо.

Акаш Кумар

Инженер-программист