Постановка задачи:
Наконец-то наступил сезон дождей. По данным метеорологического управления, в ближайшие 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)
Спасибо.
Инженер-программист