Forest density

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
  // ios::sync_with_stdio(false);
  // cin.tie(0);
  int q;
  cin >> n >> q;

  auto values = vector<string>(n, "");

  auto sumarr = vector<vector<int>>(n, vector<int>(n));

  for (int i = 0; i < n; i++) {
    cin >> values[i];
  }

  for (int i = 0; i < n; i++) {
    for (int y = 0; y < n; y++) {
      int c = 0;

      for (int x = 0; x <= i; x++) {
        for (int yy = 0; yy <= y; yy++) {
          if (values[x][yy] == '*') c++;
        }
      }
      sumarr[i][y] = c;
    }
  }

  for (int i = 0; i < q; i++) {
    int y1, x1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    y1--;
    x1--;
    y2--;
    x2--;
    int A = sumarr[y2][x2];
    if (x1 > 0) A -= sumarr[y2][x1 - 1];
    if (y1 > 0) A -= sumarr[y1 - 1][x2];
    if (y1 > 0 && x1 > 0) A += sumarr[y1 - 1][x1 - 1];

    cout << A << endl;
  }

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED