Problem:


Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

S_i is a string of length W consisting of # and ..

. occurs at least once in one of the strings S_i (1 \leq i \leq H).

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the maximum possible number of squares lighted by the lamp.

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = []

for _ in range(H):
    ss = input()
    S.append(ss)

ans = 0

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        
        cnt = 1
        
        for ds in range(1,x+2):
            nx = x - ds
            if nx < 0:
                break
            elif S[y][nx] == '#':
                break
            cnt += 1
        for ds in range(1,W-x+1):
            nx = x + ds
            if nx >= W:
                break
            elif S[y][nx] == '#':
                break
            cnt += 1
        for ds in range(1,y+2):
            ny = y - ds
            if ny < 0:
                break
            elif S[ny][x] == '#':
                break
            cnt += 1
        for ds in range(1,H-y+1):
            ny = y + ds
            if ny >= H:
                break
            elif S[ny][x] == '#':
                break
            cnt += 1
        
        ans = max(ans,cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
S = [input() for i in range(h)]

A = [[[0,0] for i in range(w)] for j in range(h)]

a = -1
b = -1
for i in range(h):
    a = -1
    for j in range(w):
        if S[i][j] == "#":
            if a != -1:
                for k in range(a,j):
                    A[i][k][0] = j-a
                a = -1
        else:
            if a == -1:
                a = j
                #print(j)
    if a != -1:
        for k in range(a,j+1):
            A[i][k][0] = j+1-a

for i in range(w):
    a = -1
    for j in range(h):
        if S[j][i] == "#":
            if a != -1:
                for k in range(a,j):
                    A[k][i][1] = j-a
                a = -1
        else:
            if a == -1:
                a = j
    if a != -1:
        for k in range(a,j+1):
            A[k][i][1] = j+1-a
#print(A)

ans = 0
for i in range(h):
    for j in range(w):
        su = sum(A[i][j])
        ans = max(ans, su)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, S):
    ans = 0
    ph = [[0] * W for _ in range(H)]
    for i in range(H):
        tmp = []
        for j in range(W):
            if S[i][j] == '.':
                tmp.append(j)
            else:
                p = len(tmp)
                for t in tmp:
                    ph[i][t] = p
                tmp = []
        if tmp:
            p = len(tmp)
            for t in tmp:
                ph[i][t] = p
            tmp = []

    pv = [[0] * W for _ in range(H)]
    for i in range(W):
        tmp = []
        for j in range(H):
            if S[j][i] == '.':
                tmp.append(j)
            else:
                p = len(tmp)
                for t in tmp:
                    pv[t][i] = p
                tmp = []
        if tmp:
            p = len(tmp)
            for t in tmp:
                pv[t][i] = p
            tmp = []

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, ph[i][j] + pv[i][j])

    return ans - 1


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[input() for i in range(h)]
c=[[[0,0] for i in range(w)] for i in range(h)]
t=0
for H,i in enumerate(s):
    for W,j in enumerate(i):
        if(j=="#"):
            for l in range(1,t+1):
                c[H][W-l][0]=t
            t=0
        else:
            t+=1
    for l in range(1,t+1):
        c[H][-l][0]=t
    t=0    
for W in range(w):
    for H in range(h):
        if(s[H][W]=="#"):
            for l in range(1,t+1):
                c[H-l][W][1]=t
            t=0
        else:
            t+=1
    for l in range(1,t+1):
        c[-l][W][1]=t
    t=0
ans=0
for i in c:
    for j in i:
        ans=max(sum(j),ans)
print(max(ans-1,0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main(H, W, s_list):
    row_count = np.zeros((H, W))
    for i_row in range(H):
        j_col = -1    
        for i_col in range(W):
            if i_col <= j_col:
                continue
            char = s_list[i_row][i_col]
            if char == '.':
                j_col = i_col
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s_list[i_row][j_col]
                    if c == '#':
                        break

                row_count[i_row, i_col:j_col] = j_col - i_col


    col_count = np.zeros((H, W))
    for i_col in range(W):
        j_row = -1    
        for i_row in range(H):
            if i_row <= j_row:
                continue
            char = s_list[i_row][i_col]
            if char == '.':
                j_row = i_row
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_list[j_row][i_col]
                    if c == '#':
                        break
                
                col_count[i_row:j_row, i_col] = j_row - i_row
    print(int(np.max(row_count + col_count)) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


H, W = _li()
S = []
mapping = {'#': 0, '.': 1}
for _ in range(H):
    S.append(list(map(lambda x: mapping[x], list(_s()))))

S = np.array(S)
S0 = (S == 0)
v_cum_S = np.zeros((H, W), dtype=int)
h_cum_S = np.zeros((H, W), dtype=int)

h_arange = np.arange(H)
for i in range(W):
    start = 0
    target = h_arange[S0[:, i]]
    for t in target:
        v_cum_S[start: t, i] = t-start
        start = t+1
    v_cum_S[start:, i] = H-start

v_arange = np.arange(W)
for i in range(H):
    start = 0
    target = v_arange[S0[i, :]]
    for t in target:
        h_cum_S[i, start: t] = t-start
        start = t+1
    h_cum_S[i, start:] = W-start

print(((v_cum_S + h_cum_S - 1)[S != 0]).max())

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,raw_input().split())
grid = []
hgrid = []
wgrid = []
for i in xrange(h):
	row = raw_input()
	grid.append(row)
	cur = 0
	width_row = []
	for x in row:
		if x == '#':
			for c in xrange(cur):
				width_row.append(cur)
			width_row.append(0)
			cur = 0
		else:
			cur += 1
	for c in xrange(cur):
		width_row.append(cur)
	wgrid.append(width_row)
#for x in wgrid:
#	print x
for j in xrange(w):
	cur = 0
	height_row = []
	for i in xrange(h):
		if grid[i][j] == '#':
			for c in xrange(cur):
				height_row.append(cur)
			height_row.append(0)
			cur = 0
		else:
			cur += 1
	for c in xrange(cur):
		height_row.append(cur)
	hgrid.append(height_row)

best = 0
for i in xrange(h):
	for j in xrange(w):
		temp = wgrid[i][j] + hgrid[j][i]
		if temp > best:
			best = temp
print best-1

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
space = []
for _ in range(h):
    space.append(list(input()))

max_light = 0
for i in range(h):
    for j in range(w):
        if space[i][j] != "#":
            light = 1
            #right
            pos = j+1
            while( pos < len(space[i])):
                if space[i][pos] == ".":
                    light += 1
                    pos += 1
                else:
                    break
            pos = j-1
            while( 0 <= pos ):
                if space[i][pos] == ".":
                    light += 1
                    pos -= 1
                else:
                    break
            pos = i+1
            while(pos < len(space)):
                if space[pos][j] == ".":
                    light += 1
                    pos += 1
                else:
                    break

            pos = i-1
            while( 0 <= pos ):
                if space[pos][j] == ".":
                    light += 1
                    pos -= 1
                else:
                    break
        
            max_light = max(max_light,light)
print(max_light)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [0 for i in range(n)]
for i in range(n):
  a[i] = input()
num = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
  for j in range(m):
    if a[i][j] == ".":
      num[i][j] += 1
      # 下
      i_2 = i+1
      j_2 = j
      if i_2 < n:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 += 1
          if i_2 < n:
            1
          else:
            break
      # 上
      i_2 = i-1
      j_2 = j
      if 0 <= i_2:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 -= 1
          if 0 <= i_2:
            1
          else:
            break
      # 上
      i_2 = i
      j_2 = j-1
      if 0 <= j_2:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 -= 1
          if 0 <= j_2:
            1
          else:
            break
      # 下
      i_2 = i
      j_2 = j+1
      if j_2 < m:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 += 1
          if j_2 < m:
            1
          else:
            break
print(max([max(i) for i in num]))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
cl=[[0]*w for i in range(h)]
for i in range(h):
    s=0
    for j in range(w):
        if l[i][j]=="#":
            for x in range(s,j):
                cl[i][x]+=j-s
            s=j+1
        elif j==w-1:
            for x in range(s,j+1):
                cl[i][x]+=j-s+1
for i in range(w):
    s=0
    for j in range(h):
        if l[j][i]=="#":
            for x in range(s,j):
                cl[x][i]+=j-s
            s=j+1
        elif j==h-1:
            for x in range(s,j+1):
                cl[x][i]+=j-s+1
print(max([max(x) for x in cl])-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
S = [input() for _ in range(H)]

g = [".", "#"]
HL = [[0] * W for _ in range(H)]
HR = [[0] * W for _ in range(H)]

for i in range(H):
  l = 0
  r = 0
  for j in range(W):
    if S[i][j] == g[0]:
      l += 1
    else:
      l = 0
    HL[i][j] = l
    if S[i][W - 1 - j] == g[0]:
      r += 1
    else:
      r = 0
    HR[i][W - 1 - j] = r

WU = [[0] * W for _ in range(H)]
WD = [[0] * W for _ in range(H)]

for i in range(W):
  u = 0
  d = 0
  for j in range(H):
    if S[j][i] == g[0]:
      u += 1
    else:
      u = 0
    WU[j][i] = u
    if S[H - j - 1][i] == g[0]:
      d += 1
    else:
      d = 0
    WD[H - j - 1][i] = d

ans = 0

for i in range(H):
  for j in range(W):
    k = HL[i][j] + HR[i][j] + WU[i][j] + WD[i][j] - 3
    ans = max(ans, k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))

S=[input() for i in range(H)]
e_list1 = [[] for i in range(H*W)]
e_list2 = [[] for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if i!=H-1:
            if S[i][j]=="." and S[i+1][j]==".":
                e_list1[i*W+j].append((i+1)*W+j)
                e_list1[(i+1)*W+j].append(i*W+j)

for i in range(H):
    for j in range(W):
        if j!=W-1:
            if S[i][j]=="." and S[i][j+1]==".":
                e_list2[i*W+j].append(i*W+j+1)
                e_list2[i*W+j+1].append(i*W+j)

from collections import deque

def BFS(vi,color,color_list,color_num,checked_list,e_list):
    
    Q = deque([vi])
    checked_list[vi]=True
    color_list[vi]=color
    color_num[color]+=1
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                color_list[v1]=color
                color_num[color]+=1
    return checked_list,color_list,color_num

color1 = 0
color_list1 = [-1 for i in range(H*W)]
color_num1 = [0 for i in range(H*W)]
checked_list1 = [False for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if S[i][j]=="." and color_list1[i*W+j]==-1:
            checked_list1,color_list1,color_num1=BFS(i*W+j,color1,color_list1,color_num1,checked_list1,e_list1)
            color1+=1


color2 = 0
color_list2 = [-1 for i in range(H*W)]
color_num2 = [0 for i in range(H*W)]
checked_list2 = [False for i in range(H*W)]


for i in range(H):
    for j in range(W):
        if S[i][j]=="." and color_list2[i*W+j]==-1:
            checked_list2,color_list2,color_num2=BFS(i*W+j,color2,color_list2,color_num2,checked_list2,e_list2)
            color2+=1

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            ans=max(color_num1[color_list1[i*W+j]]+color_num2[color_list2[i*W+j]]-1,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
s = [input() for i in range(h)]
visited = [[0 for i in range(w)] for i in range(h)]

ans = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def dfs(x, y):
  cur = 1
  if s[y][x]=="#":
    return 0

  for dxt, dyt in zip(dx, dy):
    xx, yy = x, y
    while True:
      nx = xx+dxt
      ny = yy+dyt
      if 0<=ny<h and 0<=nx<w and s[ny][nx]==".":
        cur += 1
      else:
        break
      xx, yy = nx, ny

  return cur


for i in range(h):
  for j in range(w):
    ans = max(ans, dfs(j, i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

H,W=rl()
S=[]
for i in range(H):
    S.append(input())
M = [[0 for w in range(W)] for h in range(H)]
wM = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    cnt = 0
    for w in range(W):
        if S[h][w] == '#':
            M[h][w] = 1
            for c in range(1,cnt+1):
                wM[h][w-c] = cnt
            cnt = 0
        else:
            cnt += 1
    for c in range(1,cnt+1):
        wM[h][W-c] = cnt

for w in range(W):
    cnt = 0
    for h in range(H):
        if M[h][w] == 1:
            for c in range(1,cnt+1):
                wM[h-c][w] += cnt -1
            cnt = 0
        else:
            cnt += 1
    for c in range(1,cnt+1):
        wM[h-c][w] += cnt -1

ans = 0
for ret in wM:
    ans = max(ans,max(ret))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for ll, rr, uu, dd in zip(l, r, u, d):
    ans = max(ans, max(map(sum, zip(ll, rr, uu, dd))))
print(ans - 3)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
m = [[[0, 0] for _ in range(W)] for _ in range(H)]
for h in range(H):
    i = None
    for j in range(W + 1):
        if j < W and S[h][j] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[h][k][0] = j - i
                i = None
for w in range(W):
    i = None
    for j in range(H + 1):
        if j < H and S[j][w] == ".":
            if i is None:
                i = j
        else:
            if i is not None:
                for k in range(i, j):
                    m[k][w][1] = j - i
                i = None
ans = 0
for h in range(H):
    for w in range(W):
        if m[h][w][0] == 0 or m[h][w][1] == 0:
            continue
        ans = max(ans, m[h][w][0] + m[h][w][1] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


h, w = li()
grid = [lc() for _ in range(h)]

def left_right(grid, row, col, cnt, w):
    if col == w:
        return cnt

    elif grid[row][col] == "#":
        return cnt

    else:
        cnt = left_right(grid, row, col+1, cnt+1, w)

    lr[row][col] = cnt
    return cnt


def top_bottom(grid, row, col, cnt, h):
    if row == h:
        return cnt

    elif grid[row][col] == "#":
        return cnt

    else:
        cnt = top_bottom(grid, row+1, col, cnt+1, h)

    tb[row][col] = cnt
    return cnt

lr = [[0]*w for _ in range(h)]
tb = [[0]*w for _ in range(h)]

for row in range(h):
    for col in range(w):
        if grid[row][col] == "." and lr[row][col] == 0:
            left_right(grid, row, col, 0, w)

for col in range(w):
    for row in range(h):
        if grid[row][col] == "." and tb[row][col] == 0:
            top_bottom(grid, row, col, 0, h)

ans = 0
for row in range(h):
    for col in range(w):
        ans = max(ans, lr[row][col] + tb[row][col])

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys

input = sys.stdin.readline

H, W = map(int, input().split())
s = [input() for _ in range(H)]

row_blocks = []
for r in range(H):
    t = [-1]
    for c in range(W):
        if s[r][c] == '#':
            t.append(c)
    t.append(W)
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = [-1]
    for r in range(H):
        if s[r][c] == '#':
            t.append(r)
    t.append(H)
    col_blocks.append(t)
# print(col_blocks)

ans = 0
for r in range(H):
    for c in range(W):
        t = -1
        ri = bisect_left(row_blocks[r], c)
        t += (row_blocks[r][ri] - 1) - row_blocks[r][ri - 1]
        ci = bisect_left(col_blocks[c], r)
        # print(r, c, ri, ci, col_blocks[c])
        t += (col_blocks[c][ci] - 1) - col_blocks[c][ci - 1]
        ans = max(ans, t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

area = []
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        count = 1
        delta = 1
        while j - delta >= 0:
            if s[i][j - delta] == ".":
                count += 1
                delta += 1
            else:
                break
        delta = 1
        while j + delta <= w - 1:
            if s[i][j + delta] == ".":
                count += 1
                delta += 1
            else:
                break
        delta = 1
        while i - delta >= 0:
            if s[i - delta][j] == ".":
                count += 1
                delta += 1
            else:
                break
        delta = 1
        while i + delta <= h - 1:
            if s[i + delta][j] == ".":
                count += 1
                delta += 1
            else:
                break
        area.append(count)
print(max(area))

Submission status: Time Limit Exceeded

Solution code:
H,W = (int(x) for x in input().split())

S_arr_arr = [[1]*(W+2)]
for i in range(H):
    S_arr_arr.append([0 if s=="." else 1 for s in "#"+input()+"#"])
S_arr_arr.append([1]*(W+2))

W_arr_arr = [[0]*(W+2) for _ in range(H+2)]
for j in range(H+2):
    i_begin = 0
    for i in range(W+2):
        if S_arr_arr[j][i] == 1:
            for ix in range(i_begin+1, i):
                W_arr_arr[j][ix] += i-i_begin-1
            i_begin = i
for i in range(W+2):
    j_begin = 0
    for j in range(H+2):
        if S_arr_arr[j][i] == 1:
            for jx in range(j_begin+1, j):
                W_arr_arr[jx][i] += j-j_begin-1
            j_begin = j

max_ans = max([max(W_arr) for W_arr in W_arr_arr]) - 1

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [0 for i in range(n)]
for i in range(n):
  a[i] = input()
num = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
  for j in range(m):
    if a[i][j] == ".":
      num[i][j] += 1
      # 下
      i_2 = i+1
      j_2 = j
      if 0 <= i_2 and i_2 < n:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 += 1
          if 0 <= i_2 and i_2 < n:
            1
          else:
            break
      # 上
      i_2 = i-1
      j_2 = j
      if 0 <= i_2 and i_2 < n:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 -= 1
          if 0 <= i_2 and i_2 < n:
            1
          else:
            break
      # 上
      i_2 = i
      j_2 = j-1
      if 0 <= j_2 and j_2 < m:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 -= 1
          if 0 <= j_2 and j_2 < m:
            1
          else:
            break
      # 下
      i_2 = i
      j_2 = j+1
      if 0 <= j_2 and j_2 < m:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 += 1
          if 0 <= j_2 and j_2 < m:
            1
          else:
            break
print(max([max(i) for i in num]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2500)
H, W = map(int, input().split())
S = ['#'*(W+2)]+['#' + input() + '#' for _ in range(H)]+['#'*(W+2)]

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (W+2) for _ in range(H+2)]

def process(n, x, y, dx, dy):
  ret = 0
  if S[y][x] == '#':
    ret = n
  else:
    ret = process(n+1, x+dx, y+dy, dx, dy)
  if dx > 0:
    ansX[y][x] = ret
  else:
    ansY[y][x] = ret
  return ret

final = 0
for y in range(1, H+1):
  for x in range(1, W+1):
    if S[y][x] == '#':
      continue
    if ansX[y][x] is None:
      process(0, x, y, 1, 0)
    if ansY[y][x] is None:
      process(0, x, y, 0, 1)
    a = ansX[y][x] + ansY[y][x] - 1
    final = a if a > final else final
print(final)

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return map(int, input().split())

L = []

H, W = getlist()
for i in range(H):
	S = list(input())
	L.append(S)

ans1 = [[0 for i in range(W)] for j in range(H)]
ans2 = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
	val = 0
	l = []
	for j in range(W):
		if L[i][j] == "#":
			for k in l:
				ans1[i][k] = val
			val = 0
			l = []
		else:
			val += 1
			l.append(j)
	for k in l:
		ans1[i][k] = val

for i in range(W):
	val = 0
	l = []
	for j in range(H):
		if L[j][i] == "#":
			for k in l:
				ans2[k][i] = val
			val = 0
			l = []
		else:
			val += 1
			l.append(j)
	for k in l:
		ans2[k][i] = val


ans = -1
for i in range(H):
	for j in range(W):
		x = ans1[i][j] + ans2[i][j] - 1
		if x > ans:
			ans = x

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


H, W = _li()
S = []
mapping = {'#': 0, '.': 1}
for _ in range(H):
    S.append(list(map(lambda x: mapping[x], list(_s()))))

S = np.array(S)
v_cum_S = np.zeros((H, W), dtype=int)
h_cum_S = np.zeros((H, W), dtype=int)
for i in range(W):
    start = 0
    target = np.arange(H)[S[:, i] == 0]
    for t in target:
        v_cum_S[start: t, i] = t-start
        start = t+1
    v_cum_S[start:, i] = H-start

for i in range(H):
    start = 0
    target = np.arange(W)[S[i, :] == 0]
    for t in target:
        h_cum_S[i, start: t] = t-start
        start = t+1
    h_cum_S[i, start:] = W-start

ans = 0
for i in range(H):
    for j in range(W):
        if S[i, j] == 0:
            continue
        else:
            ans = max(ans, v_cum_S[i, j] + h_cum_S[i, j] - 1)

# print(S)
# print(v_cum_S)
# print(h_cum_S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
S = [(input()) for _ in range(H)]

Mh = [[-1 for _ in range(W)] for _ in range(H)]
Mw = [[-1 for _ in range(W)] for _ in range(H)]

for h in range(H):
    w = 0
    while w < W:
        if S[h][w] == "#":
            w += 1
            continue
        start = w
        count = 0
        while w + count < W and S[h][w + count] == ".":
            count += 1
        for x in range(start, w + count):
            Mh[h][x] = count
        w = w + count


for w in range(W):
    h = 0
    while h < H:
        if S[h][w] == "#":
            h += 1
            continue
        start = h
        count = 0
        while h + count < H and S[h+count][w] == ".":
            count += 1
        for x in range(start, h + count):
            Mw[x][w] = count
        h = h + count

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, Mh[h][w]+Mw[h][w] -1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class UnionFind:
    def __init__(self, n):
        self._parents = list(range(n))
        self._ranks = [0] * n
        self._size = [1] * n

    def root(self, x):
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        return self._size[self.root(x)]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

        if self._ranks[rx] < self._ranks[ry]:
            self._parents[rx] = ry
            self._size[ry] += self._size[rx]
        else:
            self._parents[ry] = rx
            self._size[rx] += self._size[ry]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[rx] += 1

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


def solve(H: int, W: int, S: "List[str]"):
    uf_h = UnionFind(H * W)
    uf_v = UnionFind(H * W)
    for y in range(H):
        for x in range(W):
            i = y * W + x
            phi =  y * W + (x - 1)
            pvi = (y-1) * W + x
            if 0 < x and S[y][x] == '.' and S[y][x-1] == '.':
                uf_h.unite(i, phi)
            if 0 < y and S[y][x] == '.' and S[y-1][x] == '.':
                uf_v.unite(i, pvi)

    ret = 0
    for i in range(H * W):
        ret = max(ret, uf_h.size(i) + uf_v.size(i) - 1)
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, S)
    print(result)

if __name__ == '__main__':
    main()