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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def main():
    H,W = map(int,input().split())
    graph = [[""]*W for _ in range(H)]

    for h in range(H):
        graph[h] = list(input())

    left = [[1]*W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if graph[h][w] == "
                left[h][w] = 0
            else:
                if w-1 >= 0:
                    left[h][w] = left[h][w-1] + 1

    right = [[1]*W for _ in range(H)]
    for h in range(H):
        for w in reversed(range(W)):
            if graph[h][w] == "
                right[h][w] = 0
            else:
                if w+1<W:
                    right[h][w] = right[h][w+1] + 1

    down = [[1]*W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if graph[h][w] == "
                down[h][w] = 0
            else:
                if h-1>=0:
                    down[h][w] = down[h-1][w] + 1

    up = [[1]*W for _ in range(H)]
    for h in reversed(range(H)):
        for w in range(W):
            if graph[h][w] == "
                up[h][w] = 0
            else:
                if h+1<H:
                    up[h][w] = up[h+1][w] + 1

    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,up[h][w] + down[h][w] + left[h][w] + right[h][w] - 3)


    print(ans)
    
    

if __name__ == "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)



result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)



result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)

Solution (Python):
import sys
input = sys.stdin.readline

H,W = (int(x) for x in input().split())
S = [list(input()) for _ in range(H)]
memh = [[0] * W for _ in range(H)]
memv = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            h = memh[i][j]
            if h == 0:
                stopped = False
                for k in range(W-j-1):
                    if S[i][j+k+1] == '
                        for l in range(k+1):
                            memh[i][j+l] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(W-j):
                        memh[i][j+l] = W-j
                h = memh[i][j]
            v = memv[i][j]
            if v == 0:
                stopped = False
                for k in range(H-i-1):
                    if S[i+k+1][j] == '
                        for l in range(k+1):
                            memv[i+l][j] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(H-i):
                        memv[i+l][j] = H-i
                v = memv[i][j]
            ans = max(ans,h+v-1)
print(ans)

Solution (Python):





h,w   = map(int,input().split())
mp    = list(list(input()) for i in range(h))
scx   = [[0 for _ in range(w)] for _ in range(h)]
scy   = [[0 for _ in range(w)] for _ in range(h)]
donex = [[0 for _ in range(w)] for _ in range(h)]
doney = [[0 for _ in range(w)] for _ in range(h)]
sc    = 0
ans   = 0

for y in range(h):
  for x in range(w):
    if mp[y][x]=='
      scx[y][x]==0
    elif donex[y][x]==1:
      continue
    else:
      l = 1
      while(x+l<w):
        if mp[y][x+l]=='
          break
        l += 1
      for i in range(l):
        scx[y][x+i] = l
        donex[y][x+i] = 1

for y in range(h):
  for x in range(w):
    if mp[y][x]=='
      scy[y][x]==0
    elif doney[y][x]==1:
      continue
    else:
      l = 1
      while(y+l<h):
        if mp[y+l][x]=='
          break
        l += 1
      for i in range(l):
        scy[y+i][x] = l
        doney[y+i][x] = 1

for y in range(h):
  for x in range(w):
    ans = max(ans, (scy[y][x] + scx[y][x] - 1))

print(ans)

Solution (Python):
import numpy as np
h,w=map(int,input().split())
s=[]
for _ in range(h):
    si=input()
    si=si.replace('.', '1')
    si=si.replace('
    s.append(list(map(int,si)))
s=np.array(s)

left=np.zeros((h,w))
right=np.zeros((h,w))
up=np.zeros((h,w))
down=np.zeros((h,w))

for i in range(w):
    if(i==0):
        left[:,i]=s[:,i]
        right[:,w-i-1]=s[:,w-i-1]
    else:
        left[:,i]=(left[:,i-1]+1)*s[:,i]
        right[:,w-i-1]=(right[:,w-i]+1)*s[:,w-i-1]

for i in range(h):
    if(i==0):
        down[i,:]=s[i,:]
        up[h-i-1,:]=s[h-i-1,:]
    else:
        down[i,:]=(down[i-1,:]+1)*s[i,:]
        up[h-i-1,:]=(up[h-i,:]+1)*s[h-i-1,:]

ans=left+right+up+down-3
print(int(np.max(ans)))

Solution (Python):
H,W=map(int, input().split()) 
S=[[0 for _ in range(W+2)] for _ in range(H+2)]
for i in range(H):
  S[i+1]= ["
for j in range(W+2):
  S[0][j]="
  S[-1][j]="
  
t=[[-1 for _ in range(W)] for _ in range(H)]
y=[[-1 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if S[i+1][j+1]==".":
      if t[i][j]==-1:
        k=1
        while True:
          if S[i+k+1][j+1]==".":
            k +=1
          else:
            break
        for l in range(k):
          t[i+l][j]=k       
      if y[i][j]==-1:
        m=1
        while True:
          if S[i+1][j+1+m]==".":
            m +=1
          else:
            break
        for n in range(m):
          y[i][j+n]=m       

maxi=0          
for i in range(H):
  for j in range(W):
    maxi=max(maxi, t[i][j]+y[i][j])
print(maxi-1)

Solution (Python):
import numpy as np


def main():
    H, W = list(map(int, input().split(' ')))
    field = np.array([list(input()) for _ in range(H)])
    field = np.where(field == '
    left, right, up, down = [np.zeros((H, W)) for _ in range(4)]
    for w in range(W):
        left[:, w] = (left[:, w-1] + 1) * field[:, w]
        right[:, -w-1] = (right[:, -w] + 1) * field[:, -w-1]
    for h in range(H):
        up[h, :] = (up[h-1, :] + 1) * field[h, :]
        down[-h-1, :] = (down[-h, :] + 1) * field[-h-1, :]
    s = left + right + up + down - 3
    print(int(np.max(s)))


if __name__ == '__main__':
    main()

Solution (Python):
h,w = map(int,input().split())
F = [input() for _ in range(h)]

MW = [[0]*w for _ in range(h)]
MH = [[0]*w for _ in range(h)]


for i in range(h):
  l = 0
  c = 0
  for r in range(w):    
    if F[i][r] == '
      for k in range(l,r):
        MW[i][k] = c
      l = r+1
      c = 0      
    else:
      c += 1
  for k in range(l,r+1):
    MW[i][k] = c  
    
for i in range(w):
  u = 0
  c = 0
  for b in range(h):    
    if F[b][i] == '
      for k in range(u,b):
        MH[k][i] = c
      u = b+1
      c = 0      
    else:
      c += 1
  for k in range(u,b+1):
    MH[k][i] = c      
    
ans = 0    
for i in range(h):
  for j in range(w):
    tmp = 0
    if F[i][j] != '
      tmp = MH[i][j]+MW[i][j] -1 
    ans = max(ans,tmp)
    
print(ans)

Solution (Python):
import numpy as np
h,w=map(int,input().split())
S=np.array([list(input()) for _ in range(h)])
S=np.where(S==".",1,0)

left,right,up,down=[np.zeros((h,w)) for _ in range(4)]
for i in range(w):
    left[:,i]=(left[:,i-1]+1)*S[:,i]
    right[:,-i-1]=(right[:,-i]+1)*S[:,-i-1]
for i in range(h):
    up[i]=(up[i-1]+1)*S[i]
    down[-i-1]=(down[-i]+1)*S[-i-1]

print(int(np.max(left+right+up+down)-3))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        
        left = np.arange(G.shape[1], dtype=np.int16)*np.ones(G.shape, dtype=np.int16)
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.arange(G.shape[1], dtype=np.int16)*np.ones(G.shape, dtype=np.int16)
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
import itertools as it
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	H,W = inputMap()
	S = []
	for i in range(H):
		tmp = inputStr()
		S.append(list(tmp))

	part_x = []
	x = 0
	for i in range(H):
		tmp = []
		for j in range(W):
			if S[i][j] == "
				tmp.append(x)
				x = 0
				continue
			x += 1
		tmp.append(x)
		x = 0
		part_x.append(tmp)

	part_y = []
	x = 0
	for j in range(W):
		tmp = []
		for i in range(H):
			if S[i][j] == "
				tmp.append(x)
				x = 0
				continue
			x += 1
		tmp.append(x)
		x = 0
		part_y.append(tmp)

	
	
	ans = 0
	mem = [0 for i in range(W)]
	index_xx = 0
	index_xy = 0
	index_yx = 0
	index_yy = 0
	for i in range(H):
		index_yx = 0
		for j in range(W):
			index_yx += 1
			if S[i][j] == "
				index_xx += 1
				mem[j] += 1
				continue
			tmp = part_x[index_xy][index_xx] + part_y[index_yx-1][mem[j]]
			
			if ans < tmp:
				
				ans = tmp
		index_xx = 0
		index_xy += 1

	print(ans-1)






def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Solution (Python):
H,W = map(int,input().split())
data = [list(input()) for i in range(H)]

A = [[0]*(W) for i in range(H)]
B = [[0]*(W) for i in range(H)]

for i in range(H):
    a = 0
    f = 0
    t = 0
    for j in range(W):
        if data[i][j] == '.' and j < W-1:
            a += 1
            t += 1
        elif data[i][j] == '
            for k in range(f,t):
                A[i][k] = a
            t = j+1
            f = j+1
            a = 0
        else:
            for k in range(f,t+1):
                A[i][k] = a+1
for j in range(W):
    b = 0
    f = 0
    t = 0
    for i in range(H):
        if data[i][j] == '.' and i < H-1:
            b += 1
            t += 1
        elif data[i][j] == '
            for k in range(f,t):
                B[k][j] = b
            t = i+1
            f = i+1
            b = 0
        else:
            for k in range(f,t+1):
                B[k][j] = b+1
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,A[i][j]+B[i][j])
print(ans-1)

Solution (Python):
import numpy as np
h,w = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
l = np.zeros((h,w),dtype=int)
r = np.zeros((h,w),dtype=int)
u = np.zeros((h,w),dtype=int)
d = np.zeros((h,w),dtype=int)
for i in range(h):
  u[i, :] = (u[i-1]+1)*ar[i]
  d[-i-1, :] = (d[-i]+1)*ar[-i-1]

for j in range(w):
  l[:,j] = (l[:,j-1]+1)*ar[:,j]
  r[:,-j-1] = (r[:,-j]+1)*ar[:,-j-1]
print(np.max(u+d+l+r)-3)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())
    grid = [[_ for _ in input()] for _ in range(H)]

    l = [[0] * W for _ in range(H)]
    r = [[0] * W for _ in range(H)]
    u = [[0] * W for _ in range(H)]
    d = [[0] * W for _ in range(H)]

    for h in range(H):
        cur = 0
        for w in range(W):
            if grid[h][w] == '
                cur = 0
            else:
                cur += 1
            l[h][w] = cur

    for h in range(H):
        cur = 0
        for w in reversed(range(W)):
            if grid[h][w] == '
                cur = 0
            else:
                cur += 1
            r[h][w] = cur

    for w in range(W):
        cur = 0
        for h in range(H):
            if grid[h][w] == '
                cur = 0
            else:
                cur += 1
            u[h][w] = cur

    for w in range(W):
        cur = 0
        for h in reversed(range(H)):
            if grid[h][w] == '
                cur = 0
            else:
                cur += 1
            d[h][w] = cur

    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, r[h][w] + l[h][w] + u[h][w] + d[h][w] - 3)
    print(ans)


resolve()

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
hdp=[[0]*w for _ in range(h)] 
wdp=[[0]*w for _ in range(h)] 
for i in range(h):
  for j in range(w):
    if s[i][j]=='
      continue
    if j>0 and wdp[i][j-1]>0:
      wdp[i][j]=wdp[i][j-1]
    else:
      for k in range(j,w):
        if s[i][k]=='
          break
        wdp[i][j]+=1
    if i>0 and hdp[i-1][j]>0:
      hdp[i][j]=hdp[i-1][j]
    else:
      for k in range(i,h):
        if s[k][j]=='
          break
        hdp[i][j]+=1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,hdp[i][j]+wdp[i][j]-1)
print(ans)

Solution (Python):
h,w=map(lambda x:range(int(x)),input().split())
g=[[c=='.'for c in input()]for _ in h]
a=[[-3]*len(w)for _ in h]
for i in h:
  l=r=0
  for j in w: l=-~l*g[i][j]; a[i][j]+=l; r=-~r*g[i][~j]; a[i][~j]+=r
for i in w:
  d=u=0
  for j in h: d=-~d*g[j][i]; a[j][i]+=d; u=-~u*g[~j][i]; a[~j][i]+=u
print(max(a[i][j] for i in h for j in w))

Solution (Python):
h,w=map(int,input().split())
f=range
g=[[c=='.'for c in input()]for _ in f(h)]
a=[[-3]*w for _ in f(h)]
for i in f(h):
  l=r=0
  for j in f(w): l=-~l*g[i][j]; a[i][j]+=l; r=-~r*g[i][~j]; a[i][~j]+=r
for i in f(w):
  d=u=0
  for j in f(h): d=-~d*g[j][i]; a[j][i]+=d; u=-~u*g[~j][i]; a[~j][i]+=u
print(max(a[i][j] for i in f(h) for j in f(w)))

Solution (Python):
h,w=map(int,input().split())
g=[[c=='.'for c in input()] for _ in range(h)]
a=[[-3]*w for _ in range(h)]
for i in range(h):
  l=r=0
  for j in range(w):
    l=-~l*g[i][j]; a[i][j]+=l
    r=-~r*g[i][-1-j]; a[i][-1-j]+=r
for i in range(w):
  d=u=0
  for j in range(h):
    d=-~d*g[j][i]; a[j][i]+=d
    u=-~u*g[-1-j][i]; a[-1-j][i]+=u
print(max(a[i][j] for i in range(h) for j in range(w)))

Solution (Python):
h,w=map(int,input().split())
f=lambda:[[0]*w for _ in range(h)]
g=[input() for _ in range(h)]
l,r=f(),f()
for i in range(h):
  lc=rc=0
  for j in range(w):
    if g[i][j]=='.': lc+=1; l[i][j]=lc
    else: lc=0
    if g[i][-1-j]=='.': rc+=1; r[i][-1-j]=rc
    else: rc=0
d,u=f(),f()
for i in range(w):
  dc=uc=0
  for j in range(h):
    if g[j][i]=='.': dc+=1; d[j][i]=dc
    else: dc=0
    if g[-1-j][i]=='.': uc+=1; u[-1-j][i]=uc
    else: uc=0
print(max(l[i][j]+r[i][j]+d[i][j]+u[i][j]-3 for i in range(h) for j in range(w)))

Solution (Python):
import numpy as np
 
H, W = map(int, input().split())
S_list = [list(input()) for _ in range(H)]
S_list=(np.array(S_list) ==".")*1
 
L = np.zeros((H, W), int) 
R = np.zeros((H, W), int)
U = np.zeros((H, W), int)
D = np.zeros((H, W), int)
 
for w in range(W):
    if w == 0: 
        L[:,w] = S_list[:,w] 
        R[:,W-w-1] = S_list[:,W-w-1] 
    else:
        L[:,w] = (L[:,w-1]+1) * S_list[:,w] 
        R[:,W-w-1] = (R[:,W-w]+1) * S_list[:,W-w-1] 
 
for h in range(H):
    if h == 0:
        U[h,:] = S_list[h,:]
        D[H-h-1,:] = S_list[H-h-1,:]
    else:
        U[h,:] = (U[h-1,:]+1) * S_list[h,:]
        D[H-h-1,:] = (D[H-h,:]+1) * S_list[H-h-1,:]
        
ans = max(np.max(L+R+U+D-3), 0) 
 
print(ans)

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

right = [[0]*w for _ in range(h)]
left = [[0]*w for _ in range(h)]
up = [[0]*w for _ in range(h)]
down = [[0]*w for _ in range(h)]

for i in range(h):
    if s[i][0] == ".":
        left[i][0] = 1
    if s[i][w-1] == ".":
        right[i][w-1] = 1

for j in range(w):
    if s[0][j] == ".":
        down[0][j] = 1
    if s[h-1][j] == ".":
        up[h-1][j] = 1
        
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j > 0:
                left[i][j] = left[i][j-1] + 1
            if i > 0:
                down[i][j] = down[i-1][j] + 1

for i in range(h)[::-1]:
    for j in range(w)[::-1]:
        if s[i][j] == ".":
            if i < h-1:
                up[i][j] = up[i+1][j] + 1
            if j < w-1:
                right[i][j] = right[i][j+1] + 1
ans = 0
for i in range(h):
    for j in range(w):
        count = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        if ans < count:
            ans = count
print(ans)

Solution (Python):
h,w = map(int,input().split())
s = [0] * h
for i in range(h):
    s[i] = [i for i in str(input())]
ans = [[0] * w for i in range(h)]

for i in range(h):
    box = []
    a = 0
    for j in range(w):
        if s[i][j] == '.':
            box.append(j)
            a += 1
            if j == w-1:
                for k in range(len(box)):
                    ans[i][box[k]] += a
                box = []
                a = 0
        else:
            if j != 0 and len(box) >= 1:
                for k in range(len(box)):
                    ans[i][box[k]] += a
                box = []
                a = 0

for i in range(w):
    box = []
    a = 0
    for j in range(h):
        if s[j][i] == '.':
            box.append(j)
            a += 1
            if j == h-1:
                for k in range(len(box)):
                    ans[box[k]][i] += a
                box = []
                a = 0
        else:
            if j != 0 and len(box) >= 1:
                for k in range(len(box)):
                    ans[box[k]][i] += a
                box = []
                a = 0
aans = 0
for i in range(h):
    aans = max(aans,max(ans[i]))
print(aans-1)

Solution (Python):
H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

    def wallen(g):
        L = len(g[0])
        ret = []
        ret.append('
        for row in g:
            t = '
            ret.append(t)
        ret.append('
        return ret

    g = wallen(s)
    

    left = [[-1] * (W + 2) for _ in range(H + 2)]  
    right = [[-1] * (W + 2) for _ in range(H + 2)]
    up = [[-1] * (W + 2) for _ in range(H + 2)]
    down = [[-1] * (W + 2) for _ in range(H + 2)]

    for r in range(H + 2):
        for c in range(W + 2):
            if g[r][c] == '
                left[r][c] = c
            else:
                left[r][c] = left[r][c - 1]

        for c in reversed(range(W + 2)):
            if g[r][c] == '
                right[r][c] = c
            else:
                right[r][c] = right[r][c + 1]

    for c in range(W + 2):
        for r in range(H + 2):
            if g[r][c] == '
                up[r][c] = r
            else:
                up[r][c] = up[r - 1][c]

        for r in reversed(range(H + 2)):
            if g[r][c] == '
                down[r][c] = r
            else:
                down[r][c] = down[r + 1][c]

    ans = 0
    for r in range(H + 2):
        for c in range(1, W + 1):
            t = right[r][c] - left[r][c] + down[r][c] - up[r][c] - 3
            ans = max(ans, t)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
H,W=map(int, input().split())
S=[]
for h in range(H):
    s=list(input())
    S.append(s)
S=np.array(S)
ruit=np.zeros((H,W))
ruit[0,:]=np.where(S[0,:]==".",1,0)
ruil=np.zeros((H,W))
ruil[:,0]=np.where(S[:,0]==".",1,0)
ruir=np.zeros((H,W))
ruir[:,-1]=np.where(S[:,-1]==".",1,0)
ruib=np.zeros((H,W))
ruib[-1,:]=np.where(S[-1,:]==".",1,0)

for h in range(1,H):
    nowt=np.where(S[h,:]==".",1,0)
    ruit[h,:]=(ruit[h-1,:]+nowt)*nowt

    nowb=np.where(S[-(h+1),:]==".",1,0)
    ruib[-(h+1),:]=(ruib[-h,:]+nowb)*nowb

for w in range(1,W):
    nowl=np.where(S[:,w]==".",1,0)
    ruil[:,w]=(ruil[:,w-1]+nowl)*nowl
    nowr=np.where(S[:,-(w+1)]==".",1,0)
    ruir[:,-(w+1)]=(ruir[:,-w]+nowr)*nowr



print(int((ruit+ruib+ruil+ruir-3).max()))

Solution (Python):
h, w = map(int, input().split())

grid = [list(input()) for _ in range(h)]
left = [[0] * w for _ in range(h)]
right = [[0] * w for _ in range(h)]
up = [[0] * w for _ in range(h)]
down = [[0] * w for _ in range(h)]

for i in range(h):
    current = 0
    for j in range(w):
        if grid[i][j] == '
            current = 0
        else:
            current += 1
        left[i][j] = current
    
for i in range(h):
    current = 0
    for j in range(w - 1, -1, -1):
        if grid[i][j] == '
            current = 0
        else:
            current += 1
        right[i][j] = current

for i in range(w):
    current = 0
    for j in range(h):
        if grid[j][i] == '
            current = 0
        else:
            current += 1
        up[j][i] = current

for i in range(w):
    current = 0
    for j in range(h - 1, -1, -1):
        if grid[j][i] == '
            current = 0
        else:
            current += 1
        down[j][i] = current

ans = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '
            continue
        ans = max(ans, left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3)

print(ans)

Solution (Python):
H, W = map(int, input().split())
A = [input() for _ in range(H)]

U = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if A[h][w] == '
            U[h][w] = 0
            L[h][w] = 0
        else:
            U[h][w] = 1 + (U[h - 1][w] if h > 0 else 0)
            L[h][w] = 1 + (L[h][w - 1] if w > 0 else 0)

        y = H - h - 1
        x = W - w - 1
        if A[y][x] == '
            D[y][x] = 0
            R[y][x] = 0
        else:
            D[y][x] = 1 + (D[y + 1][x] if y < H - 1 else 0)
            R[y][x] = 1 + (R[y][x + 1] if x < W - 1 else 0)

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == '.':
            ans = max(ans, U[h][w] + D[h][w] + L[h][w] + R[h][w] - 3)
print(ans)