[Codeforces] D - Table with Letters - 2

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D - Table with Letters - 2
Source            : Codeforces
Category          : Data Structure, Two Pointer
Algorithm         : Two Pointer
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 400 + 5;  
  
int row;  
int column;  
int maxa;  
char grid[maxn][maxn];  
int mat[maxn][maxn];  
  
int subRectangleSum(int x1, int y1, int x2, int y2)  
{  
      int sum = mat[x2][y2] - mat[x2][y1 - 1] - mat[x1 - 1][y2] + mat[x1 - 1][y1 - 1];  
      return sum;  
}  
  
void solve()  
{  
      long long ans = 0;  
      for (int col_1 = 1; col_1 <= column; col_1++)  
      {  
            for (int col_2 = col_1 + 1; col_2 <= column; col_2++)  
            {  
                  int preRow = 1;  
                  vector <int> same(27, 0);  
                  for (int nxtRow = 1; nxtRow <= row; nxtRow++)  
                  {  
                        if (grid[nxtRow][col_1] == grid[nxtRow][col_2])  
                        {  
                              int val = grid[nxtRow][col_1] - 'a' + 1;  
                              while (preRow < nxtRow)  
                              {  
                                    int total_a = subRectangleSum(preRow, col_1, nxtRow, col_2);  
                                    if (total_a <= maxa) break;  
                                    if (grid[preRow][col_1] == grid[preRow][col_2])  
                                    {  
                                          int bad = grid[preRow][col_1] - 'a' + 1;  
                                          same[bad]--;  
                                    }  
                                    preRow++;  
                              }  
                              if (preRow < nxtRow) ans += same[val];  
                              same[val]++;  
                        }  
                  }  
            }  
      }  
      cout << ans << '\n';  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      freopen("input.txt", "r", stdin);  
      freopen("output.txt", "w", stdout);  
  
      cin >> row >> column >> maxa;  
      for (int i = 1; i <= row; i++)  
      {  
            for (int j = 1; j <= column; j++)  
            {  
                  cin >> grid[i][j];  
                  mat[i][j] = mat[i][j - 1] + (grid[i][j] == 'a');  
            }  
            for (int j = 1; j <= column; j++)  
            {  
                  mat[i][j] += mat[i - 1][j];  
            }  
      }  
      solve();  
}