[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();  
}  

[Devskill] DCP-98: How Lazy One can be Part 2

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DCP-98: How Lazy One can be Part 2
Source            : Devskill
Category          : Data Structure
Algorithm         : Two Pointer
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
      int tc;
      scanf("%d", &tc); 
      for (int tcase=1; tcase<=tc; tcase++)
      {
            int n, s;
            scanf("%d %d", &n, &s);
            vector <int> vec;
            for (int i=0; i<n; i++)
            {
                  int num;
                  scanf("%d", &num);
                  vec.push_back(num);
            }
            int minLen = n+1;
            int sum = 0;
            int low = 0;
            int high = 0;
            while (high <= n)
            {
                  if (sum >= s)
                  {
                        minLen = min(minLen, high-low);
                  }
                  if (sum >= s && low < high)
                  {
                        sum -= vec[low];
                        low++;
                  }
                  else
                  {
                        sum += vec[high];
                        high++;
                  }
             }
             if (minLen == n+1) minLen = -1;
             printf("Case %d: %d\n", tcase, minLen);
             vec.clear();
      }
      return 0;
}