Problem:


Score : 700 points

Problem Statement

We have a board with an H \times W grid.
Each square in the grid is painted in black or white. The square at the i-th row from the top and j-th column from the left is black if the j-th character in S_i is #, and white if that character is ..

Snuke can perform the following operation on the grid any number of times:

Select a row or column in the grid, and invert the color of all the squares in that row or column (that is, black squares become white and vice versa).

Then, Snuke draws a rectangle along grid lines. Here, all the squares contained in the rectangle must be painted in black.

Find the maximum possible area of Snuke's rectangle when the operation is performed optimally.

Constraints

2 \leq H \leq 2000

2 \leq W \leq 2000

|S_i| = W

S_i consists of # and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

Print the maximum possible area of Snuke's rectangle.

Sample Input 1

3 3
..#
##.
.#.

Sample Output 1

6

If the first row from the top and the third column from the left are inverted, a 2 \times 3 rectangle can be drawn, as shown below:

Sample Input 2

4 4
....
....
....
....

Sample Output 2

16

Sample Input 3

10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###

Sample Output 3

27



Sample input:
3 3
..#
##.
.#.


Sample output:
6

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans=max(H, W)
S=[input() for i in range(H)]
T = [[0]*(W-1)]
for i in range(H-1):
    t,ts=[],[]
    for j in range(W-1):
      r=S[i][j:j+2]+S[i+1][j:j+2]
      t.append(r.count('.')%2)
      if t[j]==0:
        ts.append(T[-1][j]+1)
      else:
        ts.append(0)
    T.append(ts)
for L in T[1:]:
    stack=[]
    for i,l in enumerate(L+[0]):
      w=-1
      while stack and stack[-1][1]>=l:
        w,h=stack.pop()
        ans = max(ans, (h+1)*(i-w+1))
      if w!=-1:
        stack.append((w,l))
        continue
      stack.append((i,l))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
table=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        table[j][i]=(int(S[j][i]=='#')+int(S[j+1][i]=='#')+int(S[j][i+1]=='#')+int(S[j+1][i+1]=='#') +1 )%2

def get_rec(L):
    a = len(L)
    arr = L + [0]
    stack = deque()
    ans = -1
    for i in range(a + 1):
        #print(stack)
        if len(stack)==0:
            stack.append((arr[i], i))
        elif stack[-1][0] < arr[i]:
            stack.append((arr[i], i))
        elif stack[-1][0] > arr[i]:
            while len(stack) != 0 and stack[-1][0] >= arr[i]:
                x, y = stack.pop()
                ans = max((x+1) * (i - y+1), ans)
            # print(x,y,x*(i-y))
            stack.append((arr[i], y))
        #print(ans)
    return ans
dp=[[0]*(W-1) for i in range(H-1)]
for i in range(W-1):
    for j in range(H-1):
        if j==0:
            dp[0][i]=table[0][i]
            continue
        if table[j][i]==1:
            dp[j][i]=dp[j-1][i]+1
ans=max(H,W)
for j in range(H-1):
    ans=max(ans,get_rec(dp[j]))
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W = inpl()
ans = max(H, W)
S = [input() for _ in range(H)]
T = [[0]*(W-1)]
for i in range(H-1):
    t = []
    for j in range(W-1):
        r = S[i][j:j+2] + S[i+1][j:j+2]
        t.append(r.count('.')%2)
    ts = [T[-1][i] + 1 if not k else 0 for i, k in enumerate(t) ]
    T.append(ts)
for iT in T[1:]:
    stack = []
    for i, l in enumerate(iT+[0]):
        dw = -1
        while stack and stack[-1][1] >= l:
            dw, dh = stack.pop()
            ans = max(ans, (dh+1)*(i-dw+1))
        if dw != -1:
            stack.append((dw,l))
            continue
        stack.append((i, l))
print(ans)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<complex>
#include<bitset>
#include<numeric>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

const int MAX_H = 2000, MAX_W = 2000;
int H, W;
string S[MAX_H];
int bad[MAX_H - 1][MAX_W - 1];

signed main() {
    cin >> H >> W;
    rep(i, H) {
        cin >> S[i];
    }
    rep(h, H - 1) {
        rep(w, W - 1) {
            rep(i, 2) {
                rep(j, 2) {
                    bad[h][w] += (S[h + i][w + j] == '#');
                }
            }
            bad[h][w] %= 2;
        }
    }
    rep(w, W - 1)bad[0][w] = 2 - bad[0][w];
    rep(h, H - 2) {
        rep(w, W - 1) {
            if (bad[h + 1][w] == 1)bad[h + 1][w] = 1;
            else bad[h + 1][w] = bad[h][w] + 1;
        }
    }
    int ans = max(H, W);
    rep(h, H - 1) {
        stack<pii> st;
        rep(w, W - 1) {
            int tmp = w;
            while (!st.empty() && st.top().second > bad[h][w]) {
                pii p = st.top();
                st.pop();
                ans = max(ans, p.second * (w - p.first + 1));
                tmp = p.first;
            }
            st.push(pii(tmp, bad[h][w]));
        }
        while (!st.empty()) {
            pii p = st.top();
            st.pop();
            ans = max(ans, p.second * (W - p.first));
        }
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <cstdio>
#include <cstring>
#define maxn 2010
int n, m, ans;
char s[maxn];
int p[maxn][maxn];
inline int max(int a, int b) {return a > b ? a : b;}
struct node {
	int len, h;
	void add(int _a, int _b) {len = _a, h = _b;}
} S[maxn];
int top;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s + 1);
		for (int j = 1; j <= m; j++) p[i][j] = s[j] == '#';
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (p[i][j] ^ p[i + 1][j] ^ p[i][j + 1] ^ p[i + 1][j + 1]) p[i][j] = 0;
			else p[i][j] = p[i - 1][j] + 1;
		}
	}
	for (int i = 1; i < n; i++) {
		S[++top].add(1, p[i][1]);
		for (int j = 2, len; j < m; j++) {
			len = 1;
			while (top && S[top].h >= p[i][j]) {
				len += S[top].len;
				ans = max(ans, len * (S[top].h + 1));
				top--;
			}
			S[++top].add(len, p[i][j]);
		}
		int len = 1;
		while (top) {
			len += S[top].len;
			ans = max(ans, len * (S[top].h + 1));
			top--;
		}
	}
	printf("%d\n", ans);
	return 0;
}