Maximum Submatrix 2 (Codeforces 375B)
Tags: Implement, data structures

You are given a matrix consisting of digits zero and one, its size is n × m. You are allowed to rearrange its rows. What is the maximum area of the submatrix that only consists of ones and can be obtained in the given problem by the described operations?Let's assume that the rows of matrix a are numbered from 1 to n from top to bottom and the columns are numbered from 1 to m from left to right. A matrix cell on the intersection of the i-th row and the j-th column can be represented as (i, j). Formally, a submatrix of matrix a is a group of four integers d, u, l, r (1 ≤ d ≤ u ≤ n; 1 ≤ l ≤ r ≤ m). We will assume that the submatrix contains cells (i, j) (d ≤ i ≤ u; l ≤ j ≤ r). The area of the submatrix is the number of cells it contains.

Input: The first line contains two integers n and m (1 ≤ n, m ≤ 5000). Next n lines contain m characters each — matrix a. Matrix a only contains characters: "0" and "1". Note that the elements of the matrix follow without any spaces in the lines.

Output: Print a single integer — the area of the maximum obtained submatrix. If we cannot obtain a matrix of numbers one, print 0.


Sample Inputs:
1 1
1

2 2
10
11

4 3
100
011
000
101

Sample Outputs:
1

2

2

Solution (Python):
from collections import defaultdict as dd, deque as dq, Counter as ctr
import sys
input = lambda : sys.stdin.buffer.readline().decode('utf-8').rstrip('\r\n')
inp = lambda : int(input())
mi = lambda x=int: map(x, input().split())
li = lambda x=int: list(mi(x))
lb = lambda x=int: list(map(x, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = ['No', 'Yes']
YN = ['NO', 'YES']
YY = 'YES'
NN = 'NO'
yy = 'Yes'
nn = 'No'
alp = 'abcdefghijklmnopqrstuvwxyz'
inf = sys.maxsize
mod = 1000000007
from math import ceil, sqrt, gcd

def main(kase):
    (n, m) = mi()
    grd = [input() for i in range(n)]
    dp = [[0] * m for i in range(n)]
    for i in range(n):
        for j in range(m):
            if grd[i][j] == '1':
                dp[i][j] = dp[i][j - 1] + 1
    ans = 0
    for j in range(m):
        cnt = [0] * (m + 1)
        for i in range(n):
            cnt[dp[i][j]] += 1
        ct = 0
        for i in range(m, 0, -1):
            if cnt[i]:
                ct += cnt[i]
                ans = max(ans, i * ct)
    print(ans)
    pass
if __name__ == '__main__':
    test_Cases = 1
    for i in range(test_Cases):
        main(i)

Solution (Python):
""""""
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def A(n):
    return [0] * n

def AI(n, x):
    return [x] * n

def A2(n, m):
    return [[0] * m for i in range(n)]

def G(n):
    return [[] for i in range(n)]

def GP(it):
    return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    fact(x, mod)
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa.reverse()

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def floorsum(a, b, c, n):
    if a == 0:
        return b // c * (n + 1)
    if a >= c or b >= c:
        return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
    m = (a * n + b) // c
    return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
    return n & -n

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class ST:

    def __init__(self, arr):
        n = len(arr)
        mx = n.bit_length()
        self.st = [[0] * mx for i in range(n)]
        for i in range(n):
            self.st[i][0] = arr[i]
        for j in range(1, mx):
            for i in range(n - (1 << j) + 1):
                self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

    def query(self, l, r):
        if l > r:
            return -inf
        s = (r + 1 - l).bit_length() - 1
        return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] > self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return flag

def dij(s, graph):
    d = {}
    d[s] = 0
    heap = [(0, s)]
    seen = set()
    while heap:
        (dis, u) = heappop(heap)
        if u in seen:
            continue
        seen.add(u)
        for (v, w) in graph[u]:
            if v not in d or d[v] > d[u] + w:
                d[v] = d[u] + w
                heappush(heap, (d[v], v))
    return d

def bell(s, g):
    dis = AI(n, inf)
    dis[s] = 0
    for i in range(n - 1):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
    change = A(n)
    for i in range(n):
        for (u, v, w) in edge:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                change[v] = 1
    return dis

def lcm(a, b):
    return a * b // gcd(a, b)

def lis(nums):
    res = []
    for k in nums:
        i = bisect.bisect_left(res, k)
        if i == len(res):
            res.append(k)
        else:
            res[i] = k
    return len(res)

def RP(nums):
    n = len(nums)
    s = set(nums)
    d = {}
    for (i, k) in enumerate(sorted(s), 1):
        d[k] = i
    bi = BIT([0] * (len(s) + 1))
    ans = 0
    for i in range(n - 1, -1, -1):
        ans += bi.query(d[nums[i]] - 1)
        bi.update(d[nums[i]], 1)
    return ans

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def nb(i, j, n, m):
    for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < n and 0 <= nj < m:
            yield (ni, nj)

def topo(n):
    q = deque()
    res = []
    for i in range(1, n + 1):
        if ind[i] == 0:
            q.append(i)
            res.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)
                res.append(v)
    return res

@bootstrap
def gdfs(r, p):
    for ch in g[r]:
        if ch != p:
            yield gdfs(ch, r)
    yield None
t = 1
for i in range(t):
    (n, m) = RL()
    res = []
    for i in range(n):
        res.append(input())
    dp = A2(n, m)
    for i in range(n):
        dp[i][0] = int(res[i][0] == '1')
        for j in range(1, m):
            if res[i][j] == '1':
                dp[i][j] = dp[i][j - 1] + 1
    ans = 0
    for j in range(m):
        cnt = A(m + 1)
        for i in range(n):
            cnt[dp[i][j]] += 1
        res = 0
        for i in range(m, 0, -1):
            res += cnt[i]
            ans = max(i * res, ans)
    print(ans)
''

Solution (Python):
(n, m) = map(int, input().split())
c = [input() for _ in range(n)]
cnt = [0] * (m + 1)
h = [0] * n
res = 0
for j in range(m):
    for i in range(n):
        if c[i][j] == '1':
            h[i] += 1
        else:
            h[i] = 0
    cnt = [0] * (m + 1)
    for i in range(n):
        cnt[h[i]] += 1
    ile = 0
    for i in range(m, 0, -1):
        ile += cnt[i]
        res = max(res, ile * i)
print(res)