1771E - Hossam and a Letter - CodeForces Solution

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

#define all(x) (x).begin(), (x).end()

void yn(bool b)

{ cout << (b ? "YES" : "NO") << '\n';}

using ll = long long;

using ld = long double;

using VI = vector<int>;

using VVI = vector<VI>;

using PII = pair<int,int>;

using VPII = vector<PII>;

using VVPII = vector<VPII>;

using Graph = vector<vector<int>>;

#define pb push_back

#define eb emplace_back

#define ff first

#define ss second

const int Inf = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int N = 405 + 10;

bool testcases = 0;



char c;

int a[N][N];

int ri[N][N];

int n, m;



void solve_testcase() {

  cin >> n >> m;



  for (int i = 0; i <= n + 2; ++i)

    for (int j = 0; j <= m + 2; ++j)

      ri[i][j] = 0;



  for (int i = 1; i <= n; ++i) {

    for (int j = 1; j <= m; ++j) {

      cin >> c;

      if (c == '.')

        a[i][j] = 0;

      if (c == 'm')

        a[i][j] = 1;

      if (c == '#')

        a[i][j] = 2;

    }

  }

  for (int i = 1; i <= n; ++i) {

    for (int j = m; j > 0; --j) {

      ri[i][j] = ri[i][j+1] + a[i][j];

    }

  }

  int ans = 0;

  for (int col1 = 1; col1 <= m; ++col1) {

    for (int col2 = col1 + 2; col2 <= m; ++col2) {



      int l = 1, s = 0;



      int last0 = -1, last1 = -1;



      for (int r = 1; r <= n; ++r) {

        if (a[r][col1] + a[r][col2] > 1) {

          l = r + 1;

          last0 = last1 = -1;

          s = 0;

          continue;

        }

        s += a[r][col1] + a[r][col2];



        while (s > 1) {

          s -= a[l][col1] + a[l][col2]; ++l;

        }



        if (r - l >= 2) {

          if (s <= 1 && last0 > l)

            ans = max(ans, (r - l + 1) * 2 + col2 - col1 - 1);//, cout << (r - l + 1) * 2 + col2 - col1 << " : " << l << ' ' << r << ' ' << col1 << ' ' << col2 << '\n';

          if (s == 0 && last1 > l)

            ans = max(ans, (r - l + 1) * 2 + col2 - col1 - 1);//, cout << (r - l + 1) * 2 + col2 - col1 << " : " << l << ' ' << r << ' ' << col1 << ' ' << col2 << '\n';

        }



        if (ri[r][col1 + 1] - ri[r][col2] == 0)

          last0 = r;

        if (ri[r][col1 + 1] - ri[r][col2] == 1)

          last1 = r;

      }

    }

  }

  cout << ans << '\n';

}



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);

  int t;

  if (testcases)

    cin >> t;

  else t = 1;

  while (t--)

    solve_testcase();

}