PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester : Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given the prediction of rain in the upcoming N days in the city. Initially, the water level of the city is zero millimeters. The amount of rain on the i^{th} day can be described by an array A as follows:
- If A_i \gt 0, the water level of the city will increase by A_i millimeters.
- If A_i = 0 , there will be no rain on the i^{th} day. The water level of the city decreases by D millimeters on such days. If the water level is less than D millimeters before the i^{th} day, then the water level will become zero.
There will be a red alert in the city if the water level exceeds H millimeters on any of the N days. Print YES if there will be a red alert, otherwise print NO.
EXPLANATION:
We just need to find the water level for each day and if any day water level exceeds H millimeters we call that a Red Alert. So our main focus is on finding the water level for all the days. How we can do that? Just do what the problem says.
Let’s maintain the current water level which initially, is 0 millimeters. We can go to the next day with the following two cases:
- A_i \gt 0
\hspace{0.7cm} It means that there is rain in the i_{th} day and hence the current water level will rise by A_i millimeters. After that, we can check whether the current water level exceeds H millimeters or not.
- A_i = 0
\hspace{0.7cm} Since there is no rain, hence the current water level will decrease by D millimeters. If after decreasing, the current water level becomes less than 0, we can simply make that 0.
And yes we are done !!
TIME COMPLEXITY:
O(N) per test case
SOLUTIONS:
Author
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, d, h;
cin >> n >> d >> h;
vector<int> a(n);
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (i > 0) a[i] = a[i - 1];
if (x > 0) {
a[i] += x;
} else {
if (a[i] >= d) a[i] -= d;
else a[i] = 0;
}
}
if (*max_element(a.begin(), a.end()) > h) cout << "YES\n";
else cout << "NO\n";
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
int n, d, h;
cin >> n >> d >> h;
int w = 0;
bool ok = true;
rep(i, 0, n) {
int a;
cin >> a;
if(a == 0) w = max(0, w - d);
else w += a;
if(w > h) ok = false;
}
cout << (!ok ? "YES" : "NO") << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,d,h;
cin>>n>>d>>h;
bool ok = false;
int lev = 0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(x!=0)
lev+=x;
else
lev = max(0,lev-d);
if(lev>h)
ok = true;
}
if(ok)
cout<<"Yes"<<"\n";
else
cout<<"NO"<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
