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):
from collections import defaultdict

def dfs(i,j,dx,dy,kum):
    visited[i][j] = 1
    if grid[i][j]!="
        num[i][j]=max(num[i][j],dfs(i+dx,j+dy,dx,dy,kum+1))
    num[i][j] = max(num[i][j],kum)
    return kum
def main():
    h,w = map(int, input().split())
    grid = []
    for i in range(h):
        s = list(input().rstrip())
        grid.append(s)
    l = [[0]*w for _ in range(h)]
    r = [[0]*w for _ in range(h)]
    d = [[0]*w for _ in range(h)]
    u = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j]!="
                if j==0:
                    l[i][j]=1
                else:
                    l[i][j]=l[i][j-1]+1
            if grid[i][j]=="
                l[i][j]=0
            if grid[i][j]!="
                if i==0:
                    d[i][j]=1
                else:
                    d[i][j]=d[i-1][j]+1
            if grid[i][j]=="
                d[i][j]=0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if grid[i][j]!="
                if j==w-1:
                    r[i][j]=1
                else:
                    r[i][j]=r[i][j+1]+1
            if grid[i][j]=="
                r[i][j]=0

    for i in range(h-1,-1,-1):
        for j in range(w):
            if grid[i][j]!="
                if i==h-1:
                    u[i][j]=1
                else:
                    u[i][j]=u[i+1][j]+1
            if grid[i][j]=="
                u[i][j]=0
    tmp = 0

    for i in range(h):
        for j in range(w):
            tmp = max(tmp, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)



    print(tmp)

if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
s = []
for i in range(h):
  t = input()
  s.append(t)
yokol = [[0 for i in range(w)] for j in range(h)]
yokor = [[0 for i in range(w)] for j in range(h)]
tateu = [[0 for i in range(w)] for j in range(h)]
tated = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
  cnt = 0
  for j in range(w):
    if s[i][j] == '
      cnt =0
    else:
      cnt += 1
      yokol[i][j] = cnt
  cnt = 0
  for j in reversed(range(w)):
    if s[i][j] == '
      cnt=0
    else:
      cnt += 1
      yokor[i][j] = cnt

for j in range(w):
  cnt = 0
  for i in range(h):
    if s[i][j] == '
      cnt =0
    else:
      cnt += 1
      tateu[i][j] = cnt
  cnt = 0
  for i in reversed(range(h)):
    if s[i][j] == '
      cnt =0
    else:
      cnt += 1
      tated[i][j] = cnt

ans = 0
for i in range(h):
  for j in range(w):
    x = yokol[i][j] + yokor[i][j] + tateu[i][j] + tated[i][j] - 3
    ans = max(ans,x)
print (ans)

Solution (Python):
h,w=map(int,input().split())
M=[list(input()) for i in range(h)]
D=[[0]*w for i in range(h)]
U=[[0]*w for i in range(h)]
R=[[0]*w for i in range(h)]
L=[[0]*w for i in range(h)]

for i in range(h):
    c=0
    for j in range(w):
        if M[i][j]=='.':
            c+=1
            R[i][j]=c
        else:
            c=0
for i in range(h):
    c=0
    for j in range(w):
        if M[i][w-1-j]=='.':
            c+=1
            L[i][w-1-j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[i][j]=='.':
            c+=1
            D[i][j]=c
        else:
            c=0
for j in range(w):
    c=0
    for i in range(h):
        if M[h-1-i][j]=='.':
            c+=1
            U[h-1-i][j]=c
        else:
            c=0
r=0
for i in range(h):
    for j in range(w):
        r=max(r,R[i][j]+L[i][j]+D[i][j]+U[i][j]-3)
print(r)

Solution (Python):


import numpy as np
import sys
buf = sys.stdin.buffer
 
H,W = map(int,buf.readline().split())

grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'.').reshape((H,W+1))
 

def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) 
  L = len(x)
  
  left_zero = np.where(x,0,-np.arange(L)) 
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.where(x[::-1],0,np.arange(L)) 
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

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

l = [[0]*w for i in range(h)]
r = [[0]*w for i in range(h)]
u = [[0]*w for i in range(h)]
d = [[0]*w for i in range(h)]

for i in range(h):
    c = 0
    for j in range(w):
        if x[i][j] == '.':
            l[i][j] = c
            c += 1
        else: c=0


for i in range(h):
    c = 0
    for j in range(w):
        if x[i][w-1-j] == '.':
            r[i][w-1-j] = c
            c += 1
        else: c=0

for i in range(w):
    c = 0
    for j in range(h):
        if x[j][i] == '.':
            u[j][i] = c
            c += 1
        else: c=0

for i in range(w):
    c = 0
    for j in range(h):
        if x[h-1-j][i] == '.':
            d[h-1-j][i] = c
            c += 1
        else: c=0

ans = 0
for i in range(h):
    for j in range(w):
        c = l[i][j]+r[i][j]+u[i][j]+d[i][j]
        if x[i][j]=='.':c+=1
        ans = max(ans,c)

print(ans)

Solution (Python):
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
up = [[0 for i in range(w)] for j in range(h)]
down = [[0 for i in range(w)] for j in range(h)]
right = [[0 for i in range(w)] for j in range(h)]
left = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
    
    if grid[0][i] == ".":
        up[0][i] = 1
    else:
        up[0][i] = 0
    
    if grid[-1][i] == ".":
        down[-1][i] = 1
    else:
        down[-1][i] = 0
for i in range(h):
    
    if grid[i][-1] == ".":
        right[i][-1] = 1
    else:
        right[i][-1] = 0
    
    
    if grid[i][0] == ".":
        left[i][0] = 1
    else:
        left[i][0] = 0
for i in range(h):
    for j in range(1,w):
        if grid[i][j] == ".":
            left[i][j] = left[i][j-1] + 1
        else:
            left[i][j] = 0
for i in range(h):
    for j in range(w-2,-1,-1):
        if grid[i][j] == ".":
            right[i][j] = right[i][j+1] + 1
        else:
            right[i][j] = 0

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

Solution (Python):
def resolve():
    (H, W) = list(map(int, input().split(" ")))
    S = [list(input()) for i in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    U = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "
                continue
            L[i][j] = L[i][j-1]+1 if j > 0 else 1
    for i in range(H-1, -1, -1):
        for j in range(W-1, -1 ,-1):
            if S[i][j] == "
                continue
            R[i][j] = R[i][j+1]+1 if j < W-1 else 1
    for i in range(H-1, -1, -1):
        for j in range(W):
            if S[i][j] == "
                continue
            D[i][j] = D[i+1][j]+1 if i < H-1 else 1
    for i in range(H):
        for j in range(W-1, -1 ,-1):
            if S[i][j] == "
                continue
            U[i][j] = U[i-1][j]+1 if i > 0 else 1
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

    print(ans)

if '__main__' == __name__:
    resolve()

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w = map(int,ipt().split())
    s = [""]*h+["
    for i in range(h):
        s[i] = input()+"
    l = [[0]*(w+1) for _ in [0]*(h+1)]
    r = [[0]*(w+1) for _ in [0]*(h+1)]
    u = [[0]*(w+1) for _ in [0]*(h+1)]
    d = [[0]*(w+1) for _ in [0]*(h+1)]
    sm = [[-3]*(w+1) for _ in [0]*(h+1)]
    for i in range(h):
        si = sm[i]
        li = l[i]
        ui = u[i]
        for j in range(w):
            if s[i][j] == "
                continue
            else:
                li[j] = l[i-1][j]+1
                ui[j] = ui[j-1]+1
                si[j] += li[j]+ui[j]
    ma = 0
    for i in range(h):
        ri = r[h-i-1]
        si = sm[h-i-1]
        di = d[h-i-1]
        for j in range(w):
            if s[h-i-1][w-j-1] == "
                continue
            else:
                ri[w-j-1] = r[h-i][w-j-1]+1
                di[w-j-1] = di[w-j]+1
                si[w-j-1] += ri[w-j-1]+di[w-j-1]
                if ma < si[w-j-1]:
                    ma = si[w-j-1]
    print(ma)


    return

if __name__ == '__main__':
    main()

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


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

for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			if j == 0:
				L[i][j] = 1
			else:
				L[i][j] = L[i][j - 1] + 1

for i in range(H):
	for j in range(W - 1, -1, -1):
		if S[i][j] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

for j in range(W):
	for i in range(H - 1, -1, -1):
		if S[i][j] == ".":
			if i == H - 1:
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1


ans = 0
X = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
	ans = max(ans, max(X[i]))

print(ans)

Solution (Python):
import sys

def solve(H: int, W: int, S: "List[int]"):
    

    hcnts = [[0]*W for _ in range(H)]
    for h in range(H):
        hcnts[h][0] = S[h][0]
        for t in range(1,W):
            hcnts[h][t] = (S[h][t]+hcnts[h][t-1])*S[h][t]
    for h in range(H):
        for t in range(W-2,-1,-1):
            hcnts[h][t] = max(hcnts[h][t],hcnts[h][t+1])*bool(hcnts[h][t])

    wcnts = [[0]*W for _ in range(H)]
    for h in range(W):
        wcnts[0][h] = S[0][h]
        for t in range(1,H):
            wcnts[t][h] = (S[t][h]+wcnts[t-1][h])*S[t][h]
    for h in range(W):
        for t in range(H-2,-1,-1):
            wcnts[t][h] = max(wcnts[t][h],wcnts[t+1][h])*bool(wcnts[t][h])
    
    
    a = [hcnts[h][w]+wcnts[h][w]-1 for h in range(H) for w in range(W)]
    print(max(a))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    S = [[ int(_.replace(".", "1").replace("
    solve(H, W, S)

if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
grid=[]
for _ in range(h):
    s=input()
    g=[0 if i=='
    grid.append(g)
toL=[]
toR=[]
toU=[]
toD=[]
for i in range(h):
    tmpL=[]
    tmpR=[]
    tmpU=[]
    tmpD=[]
    for j in range(w):
        if grid[i][j]==0:
            tmpU.append(0)
        elif i==0:
            tmpU.append(1)
        else:
            tmpU.append(toU[i-1][j]+1)
        if grid[-i-1][j]==0:
            tmpD.append(0)
        elif i==0:
            tmpD.append(1)
        else:
            tmpD.append(toD[i-1][j]+1)
        if grid[i][j]==0:
            tmpL.append(0)
        elif j==0:
            tmpL.append(1)
        else:
            tmpL.append(tmpL[-1]+1)
        if grid[i][-j-1]==0:
            tmpR.append(0)
        elif j==0:
            tmpR.append(1)
        else:
            tmpR.append(tmpR[-1]+1)
    toL.append(tmpL)
    toR.append(tmpR[::-1])
    toU.append(tmpU)
    toD.append(tmpD)
toD=toD[::-1]
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, toU[i][j]+toD[i][j]+toR[i][j]+toL[i][j]-3)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[[d for d in input()] for i in range(H)]
ans=[[0 for j in range(W)] for i in range(H)]
t=0
for i in range(H):
 p=0
 for j in range(W):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for i in range(H):
 p=0
 for j in range(W)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H):
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
for j in range(W):
 p=0
 for i in range(H)[::-1]:
  if S[i][j]==".":
   p+=1
  else:
   p=0
  ans[i][j]+=p
  t=max(t,ans[i][j])
print(t-3)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





H,W = IL()
S = SLs(H)

YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  
YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  

TATE = []
for i in range(W):
  prev = None
  yoko = []
  count = 0
  for j in range(H):
    item = S[j][i]
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  TATE.append(yoko)


print(max(max(TATE[j][i]+YOKO[i][j] for j in range(W)) for i in range(H))-1)

Solution (Python):
h, w = map(int, input().split())
s = [input() for _ in range(h)]
hrz = [[0] * w for _ in range(h)]
vrt = [[0] * w for _ in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w + 1):
        if j < w and s[i][j] == '.':
            if cnt == 0:
                start = j
            cnt += 1
        elif cnt > 0:
            for k in range(start, j):
                hrz[i][k] = cnt
            cnt = 0
for j in range(w):
    cnt = 0
    for i in range(h + 1):
        if i < h and s[i][j] == '.':
            if cnt == 0:
                start = i
            cnt += 1
        elif cnt > 0:
            for k in range(start, i):
                vrt[k][j] = cnt
            cnt = 0
ans = max(hrz[i][j] + vrt[i][j] - 1 for i in range(h) for j in range(w))
print(ans)

Solution (Python):

import numpy as np

H,W = (int(x) for x in input().split())
map1 =[ list(input()) for i in range(H)]
map_np =(np.array(map1)==".")*1

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)

L[:,0] =map_np[:,0]
for i in range(1,W): 
    L[:,i] = (L[:,i-1] +1) *map_np[:,i]

R[:,W-1] =map_np[:,W-1]
for i in range(W-1-1,-1,-1):
    R[:,i] = (R[:,i+1] +1) *map_np[:,i]

U[0,:] =map_np[0,:]
for i in range(1,H):
    U[i,:] = (U[i-1,:] +1) *map_np[i,:]

D[H-1,:] =map_np[H-1,:]
for i in range(H-1-1,-1,-1):
    D[i,:] = (D[i+1,:] +1) *map_np[i,:]
    
ans =L +R +U +D -3
print(np.max(ans))

Solution (Python):
import numpy as np

H,W=map(int,input().split())
S=np.array([list(input()) for _ in range(H)]) == "."

ups=np.zeros((H,W),dtype=int)
downs=np.zeros((H,W),dtype=int)
rights=np.zeros((H,W),dtype=int)
lefts=np.zeros((H,W),dtype=int)

for i in range(1,H):
    ups[i,:]=(ups[i-1,:]+1)*S[i-1,:]

for i in range(H-2,-1,-1):
    downs[i,:]=(downs[i+1,:]+1)*S[i+1,:]

for i in range(1,W):
    rights[:,i]=(rights[:,i-1]+1)*S[:,i-1]

for i in range(W-2,-1,-1):
    lefts[:,i]=(lefts[:,i+1]+1)*S[:,i+1]

ans=((ups+downs+lefts+rights)*S).max()+1
print(ans)

Solution (Python):

import numpy as np

h, w = list(map(int, input().split()))

s = np.array([list(input()) for _ in range(h)]) == "."

ups = np.zeros((h, w), dtype=int)
downs = np.zeros((h, w), dtype=int)
rights = np.zeros((h, w), dtype=int)
lefts = np.zeros((h, w), dtype=int)

for i in range(1, h):
    ups[i, :] = (ups[i-1]+1)*s[i-1]

for i in reversed(range(h-1)):
    downs[i, :] = (downs[i+1]+1)*s[i+1]

for i in range(1, w):
    rights[:, i] = (rights[:, i-1]+1)*s[:, i-1]

for i in reversed(range(w-1)):
    lefts[:, i] = (lefts[:, i+1]+1)*s[:, i+1]

ans = (((ups+downs+lefts+rights)*s).max()+1)
print(ans)

Solution (Python):
from itertools import product
import numpy as np

h, w = map(int, input().split())
notwall = []
for _ in range(h):
    s = input()
    notwall.append([int(c == '.') for c in s])

notwall = np.array(notwall)


def getll():
    ls = np.zeros((h, w + 1), dtype=int)

    for i in range(w):
        ls[:, i + 1] = (ls[:, i] + 1) * notwall[:, i]

    ls = ls[:, 1:]
    return ls


def getlr():
    ls = np.zeros((h, w + 1), dtype=int)

    for i in range(w - 1, -1, -1):
        ls[:, i] = (ls[:, i + 1] + 1) * notwall[:, i]

    ls = ls[:, :-1]
    return ls


def getlu():
    ls = np.zeros((h + 1, w), dtype=int)

    for i in range(h):
        ls[i + 1, :] = (ls[i, :] + 1) * notwall[i, :]

    ls = ls[1:, :]
    return ls


def getld():
    ls = np.zeros((h + 1, w), dtype=int)

    for i in range(h - 1, -1, -1):
        ls[i, :] = (ls[i + 1, :] + 1) * notwall[i, :]

    ls = ls[:-1, :]
    return ls


ll = getll()
lr = getlr()
lu = getlu()
ld = getld()

m = max([0, np.max(ll + lr + lu + ld) - 3])

print(m)

Solution (Python):
from sys import stdin
import numpy as np
def main():
    
    readline=stdin.readline
    h,w=map(int,readline().split())
    grid=[readline().strip() for _ in range(h)]
    grid2=np.zeros((h,w),dtype="int64")
    for i in range(h):
        for j in range(w):
            if grid[i][j]==".":
                grid2[i][j]=1
            else:
                grid2[i][j]=0

    up=np.zeros((h,w),dtype="int64")
    up[0]=grid2[0]
    for i in range(1,h):
        up[i]=(up[i-1]+1)*grid2[i]
    
    down=np.zeros((h,w),dtype="int64")
    down[-1]=grid2[-1]
    for i in range(h-2,-1,-1):
        down[i]=(down[i+1]+1)*grid2[i]
    
    left=np.zeros((h,w),dtype="int64")
    left[:,0]=grid2[:,0]
    for i in range(1,w):
        left[:,i]=(left[:,i-1]+1)*grid2[:,i]
    
    right=np.zeros((h,w),dtype="int64")
    right[:,-1]=grid2[:,-1]
    for i in range(w-2,-1,-1):
        right[:,i]=(right[:,i+1]+1)*grid2[:,i]

    ans=(up+down+left+right-3).max()
    print(ans)
    
if __name__=="__main__":
    main()

Solution (Python):
import numpy as np
import sys
 
def main():
    sin = sys.stdin.buffer
    H, W = map(int, sin.readline().split())
    grid = np.frombuffer(sin.read(H * (W + 1)), dtype="B") == ord(".")
    grid = grid.reshape((H, W + 1))[:, :-1]
 
    L = np.empty((H, W), dtype="i4")
    R = np.empty((H, W), dtype="i4")
    T = np.empty((H, W), dtype="i4")
    B = np.empty((H, W), dtype="i4")
 
    T[0] = grid[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * grid[i]
 
    B[-1] = grid[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * grid[i]
 
    L[:, 0] = grid[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * grid[:, i]
 
    R[:, -1] = grid[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * grid[:, i]
 
    ans = (T + B + L + R - 3).max()
    print(ans)
 
main()

Solution (Python):
h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)

Solution (Python):
H,W = map(int,input().split())
s = [input() for _ in range(H)]
ans = [[-1 for w in range(W)] for h in range(H)]
ans0 = ans[:]
for h in range(H):
    sh = s[h]
    st = -1
    gl = -1
    cnt = 0
    for w in range(W):
        if sh[w] == '.':
            cnt += 1
            if st == -1:
                st,gl = w,w
            gl +=1
            if w == W-1:
                for i in range(st,w+1):
                    ans[h][i] += cnt
        else:
            for i in range(st,gl):
                ans[h][i] += cnt
            cnt = 0
            st,gl = -1,-1



for w in range(W):
    st = -1
    gl = -1
    cnt = 0
    for h in range(H):
        if s[h][w] == '.':
            cnt += 1
            if st == -1:
                st,gl = h,h
            gl +=1
            if h == H-1:
                for i in range(st,h+1):
                    ans[i][w] += cnt
        else:
            for i in range(st,gl):
                ans[i][w] += cnt
            cnt = 0
            st,gl = -1,-1

mx = 0
for x in ans:
    mx = max(max(x),mx)
print(mx)

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


left = [[-1 for _ in range(W)] for _ in range(H)]
right = [[-1 for _ in range(W)] for _ in range(H)]
top = [[-1 for _ in range(W)] for _ in range(H)]
bottom = [[-1 for _ in range(W)] for _ in range(H)]



for i in range(H):
    count = 0
    for j in range(W):
        if Ss[i][j] == "
            count = 0
        else:
            left[i][j] = count
            count += 1


for i in range(H):
    count = 0
    for j in range(W):
        k = W-j-1
        if Ss[i][k] == "
            count = 0
        else:
            right[i][k] = count
            count += 1


for j in range(W):
    count = 0
    for i in range(H):
        if Ss[i][j] == "
            count = 0
        else:
            top[i][j] = count
            count += 1


for j in range(W):
    count = 0
    for i in range(H):
        k = H - i - 1
        if Ss[k][j] == "
            count = 0
        else:
            bottom[k][j] = count
            count += 1

















max_score = 0
for i in range(H):
    for j in range(W):
        if Ss[i][j] != "
            score = left[i][j] + right[i][j] + top[i][j] + bottom[i][j] + 1
            max_score = max(max_score, score)

print(max_score)

Solution (Python):
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
r = [[0]*w for _ in range(h)]
for i in range(h):
    flg = False
    for j in range(w):
        if s[i][j]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[i][j]=='
            for k in range(begin, j):
                r[i][k] = tmp
            flg = False
    if flg:
        for k in range(begin, w):
            r[i][k] = tmp
c = [[0]*w for _ in range(h)]
for i in range(w):
    flg = False
    for j in range(h):
        if s[j][i]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[j][i]=='
            for k in range(begin, j):
                c[k][i] = tmp
            flg = False
    if flg:
        for k in range(begin, h):
            c[k][i] = tmp
ans = 0
for row1, row2 in zip(r, c):
    for e1, e2 in zip(row1, row2):
        if ans<e1+e2-1:
            ans = e1+e2-1
print(ans)

Solution (Python):
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
r = [[0]*w for _ in range(h)]
for i in range(h):
    flg = False
    row = s[i]
    row2 = r[i]
    for j in range(w):
        if row[j]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and row[j]=='
            for k in range(begin, j):
                row2[k] = tmp
            flg = False
    if flg:
        for k in range(begin, w):
            row2[k] = tmp
c = [[0]*w for _ in range(h)]
for i in range(w):
    flg = False
    for j in range(h):
        if s[j][i]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[j][i]=='
            for k in range(begin, j):
                c[k][i] = tmp
            flg = False
    if flg:
        for k in range(begin, h):
            c[k][i] = tmp
ans = 0
for row1, row2 in zip(r, c):
    for e1, e2 in zip(row1, row2):
        if ans<e1+e2-1:
            ans = e1+e2-1
print(ans)

Solution (Python):
h , w = map(int,input().split())
giri = [list(input()) for i in range(h)]
ans = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    sta = -1
    cou = 0
    for j in range(w):
        if sta == -1 and giri[i][j] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[i][j] == ".":
            cou += 1
        elif sta != -1 and giri[i][j] == "
            for k in range(sta,j):
                ans[i][k] += cou
            cou = 0
            sta = -1
        if j == w-1 and sta != -1:
            for k in range(sta,w):
                ans[i][k] += cou

for i in range(w):
    sta = -1
    cou = 0
    for j in range(h):
        if sta == -1 and giri[j][i] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[j][i] == ".":
            cou += 1
        elif sta != -1 and giri[j][i] == "
            for k in range(sta,j):
                ans[k][i] += cou
            cou = 0
            sta = -1
        if j == h-1 and sta != -1:
            for k in range(sta,h):
                ans[k][i] += cou

kotae = 0

for i in range(h):
    for j in range(w):
        kotae = max(kotae,ans[i][j]-1)

print(kotae)

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

    cnt = [[0]*w for _ in range(h)]
    for i in range(h):
        prev = [0]*w
        for j in range(w):
            if s[i][j] == '
                continue
            if prev[j] == 1:
                continue
            ln = 0
            while j+ln < w:
                if s[i][j+ln] == '
                    break
                ln += 1
            for k in range(ln):
                cnt[i][j+k] += ln
                prev[j+k] = 1
    for j in range(w):
        prev = [0]*h
        for i in range(h):
            if s[i][j] == '
                continue
            if prev[i] == 1:
                continue
            ln = 0
            while i+ln < h:
                if s[i+ln][j] == '
                    break
                ln += 1
            for k in range(ln):
                cnt[i+k][j] += ln
                prev[i+k] = 1
    res = 0
    for i in range(h):
        for j in range(w):
            res = max(res, cnt[i][j]-1)
    print(res)

if __name__ == '__main__':
    main()