# PROBLEM LINK:

Division 1

Division 2

Practice

**Author:** Anton Trygub

**Tester:** Alexander Morozov

**Editorialist:** Colin Galen

# DIFFICULTY:

Cakewalk

# PREREQUISITES:

Basic Math, Observations

# PROBLEM:

You’re given a sequence of n integers a_1, a_2, \dots, a_n. You may perform some number (possibly zero) of the following operation: choose some i, and reduce the value of a_i by i. Find out if it’s possible to make the sum of all the integers equal to 0.

# QUICK EXPLANATION:

## Main solution

It’s possible if the initial sum is at least 0, otherwise impossible.

# EXPLANATION:

## Main solution

Notice that the operations you do can only decrease the overall sum. So if the overall sum is initially less than 0, there’s no way to bring that sum up to 0 using the operations.

Otherwise, say the sum is x, where x \geq 0. You can do the operation on the first element and decrease a_1 by 1, x times. Thus, it’s always possible if x \geq 0.

# TIME COMPLEXITY:

## Main solution

O(n) for reading in the input and computing the sum.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int sum = 0;
int tmp;
for (int i = 0; i<n; i++)
{
cin>>tmp; sum+=tmp;
}
if (sum>=0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t;
cin>>t;
while (t--) solve();
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int s =0;
for(int i=0;i<n;++i){
int x;
cin >> x;
s += x;
}
cout << (s < 0 ? "NO" : "YES") << '\n';
}
return 0;
}
```

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
void solve(int tc = 0) {
ll n;
cin >> n;
ll s = 0, x;
for (ll i = 0; i < n; i++) {
cin >> x;
s += x;
}
cout << (s >= 0 ? "YES\n" : "NO\n");
}
int main() {
send help
int tc = 1;
cin >> tc;
for (int t = 0; t < tc; t++) solve(t);
}
```

# Video Editorial(s)

My video: https://youtu.be/TB_krkk_U9A?t=85

Official video: https://www.youtube.com/watch?v=k6G07av1AjQ