Calculating sum after ranged-based subtractions The puzzle consists from something like this:

You will receive an array of integer with values, then you will receive X numbers. Each number (call it x) represents an index of a 1-indexed array. Look up the value in the array (call it y), then subtract 1 from all the values in the array in the range [x-y, x+y]. The minimum value is 0.

After the given number of operations, you must return the sum of all values in the array.

My code looks like this.

#include &lt;cstdio&gt;
int array[111111];

int main(){
  int m,n;
  unsigned long long int sum = 0;

  //here n is the size of the array, and m is the number of operations
  scanf("%d %d", &amp;n, &amp;m);

  for (int i = 0; i &lt; n; i++){
    scanf("%d", &amp;array[i]);
    sum+= array[i];
  }

  for (int i = 0; i &lt; m; i++) {
    int idx;
    scanf("%d", &amp;idx);
    int count= array[idx - 1];

    for (int j = (idx -1 -count &gt;=0 ? idx -1 -count : 0); j &lt; (idx + count &lt;=n ? idx + count : n); j++)
      if (array[j]){
        sum--;
        array[j]--;
      }
  }

  printf("%d\n", sum);
}


It solves the problem, but does not pass in the worst case, that would be a ton of cases decreasing from the entire array, basically an O(n*n) (I think).

The value restrictions are:


1 ≤ N,M ≤ 100000;
Value inside array index between 0 and 50000.




Test case:

Input:

10 4
1 2 0 8 4 2 9 8 1 3
9 5 10 6


Output:

23


Visualization of the test case:



For example, the first number that is read is 9. If we treat the number sequence as a 1-indexed array, we read value 1. This means that we need to subtract 1 from every value in the range [9-1, 9+1], which corresponds to the last three elements of the array.
Performance
From what I understand, your solution is as good as it would get. The &quot;n^2&quot; (it's more like O(n*m)) performance seems inevitable. It also seems that an array is the optimal data structure since you must index into it.
If you really want to remove the worst case (decreasing from the entire array), you could keep a count of the number of times you have subtracted from the whole array and let the array value be array[idx] - theCountIMentioned and the final sum be sum - n * theCountIMentioned. Despite this, the performance would still be nearly n^2, especially since decreasing all but one of the values would be an O(n) operation, so the worst case would be O(n * m).
Readability
On another note: to make the inner loop more readable consider the following two functions:
inline int min(int a, int b){
    return (a &lt; b)? a : b;
}

inline int max(int a, int b){
    return (a &gt; b)? a : b;
}

This would make the inner loop's header much more readable. (It would be for(int j = max(0, idx - 1 - count); j &lt; min(idx + count, n); j++)).
Also, you should make the variable names more readable.

n = arrayLength or even arrLen.
m = numberOfOps or even opCt.