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):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "
            U[i][j] = 0
            L[i][j] = 0
        else:
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1


for i in reversed(range(h)):
    for j in reversed(range(w)):
        if s[i][j] == "
            D[i][j] = 0
            R[i][j] = 0
        else:
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(ans)

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

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

S=[[0]*(W+2) for _ in range(H+2)]
for i in range(H):
    S[i+1]=[0]+list(map(lambda x:int(x=="."),input()))+[0]


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


for y in range(H+2):
    for x in range(W+2):
        if S[y][x]:
            R[y][x]=R[y][x-1]+1

for y in range(H+2):
    for x in range(W+1,-1,-1):
        if S[y][x]:
            L[y][x]=L[y][x+1]+1

for x in range(W+2):
    for y in range(H+2):
        if S[y][x]:
            D[y][x]=D[y-1][x]+1

for x in range(W+2):
    for y in range(H+1,-1,-1):
        if S[y][x]:
            U[y][x]=U[y+1][x]+1

A=[[0]*(W+2) for _ in range(H+2)]
for y in range(H+2):
    for x in range(W+2):
        A[y][x]=U[y][x]+D[y][x]+R[y][x]+L[y][x]-3

M=0
for y in range(H+2):
    M=max(M,max(A[y]))

print(M)

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

h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    si=input()
    s[i]=si
"""
h,w=4,6
s=[['
"""
ww=[[0]*w for i in range(h)]

www=[0]*w
for i in range(h):
    jsum=0
    jcnt=1
    jj=[0]*(w+1)
    for j in range(w):
        if s[i][j]==".":

            www[j]=jcnt
            if j<w-1 and s[i][j+1]=="
                jcnt+=1
            jsum+=1
        else:

            if jsum!=0:
                jj[jcnt-1]=jsum
            jsum=0
    jcnt+=1
    jj[jcnt-1]=jsum
            
    for j in range(w):
        if s[i][j]==".":

            ww[i][j]=jj[www[j]]

                
hh=[[0]*w for i in range(h)]
hhh=[0]*h
for j in range(w):
    isum=0
    icnt=1
    ii=[0]*(h+1)
    for i in range(h):
        if s[i][j]==".":

            hhh[i]=icnt
            if i<h-1 and s[i+1][j]=="
                icnt+=1
            isum+=1
        else:

            if isum!=0:
                ii[icnt-1]=isum
            isum=0
    icnt+=1
    ii[icnt-1]=isum
            
    for i in range(h):
        if s[i][j]==".":

            hh[i][j]=ii[hhh[i]]

            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Solution (Python):
h,w=map(int,input().split())
s=[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):
    temp=1
    for j in range(w):
        if s[i][j]==".":
            left[i][j]+=temp
            temp+=1
        else:
            temp=1
for i in range(h):
    temp=1
    for j in range(w)[::-1]:
        if s[i][j]==".":
            right[i][j]+=temp
            temp+=1
        else:
            temp=1
for i in range(w):
    temp=1
    for j in range(h):
        if s[j][i]==".":
            down[j][i]+=temp
            temp+=1
        else:
            temp=1
for i in range(w):
    temp=1
    for j in range(h)[::-1]:
        if s[j][i]==".":
            up[j][i]+=temp
            temp+=1
        else:
            temp=1
ans=1
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):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w=mp()
s=["
for i in range(h):
    s.append("
s.append("
ans=[[0]*(w+2) for i in range(h+2)]

for i in range(h+2):
    ran=[]
    c=1
    for j in range(1,w+2):
        if s[i][j]==s[i][j-1]:
            c+=1
        else:
            ran.append(c)
            c=1
    ran.append(c)
    p=0
    for j in range(len(ran)):
        for k in range(ran[j]):
            if j%2==1:
                ans[i][p]+=ran[j]
            p+=1

for i in range(w+2):
    ran=[]
    c=1
    for j in range(1,h+2):
        if s[j][i]==s[j-1][i]:
            c+=1
        else:
            ran.append(c)
            c=1
    ran.append(c)
    p=0
    for j in range(len(ran)):
        for k in range(ran[j]):
            if j%2==1:
                ans[p][i]+=ran[j]
            p+=1
x=0
for i in range(h+2):
    for j in range(w+2):
        x=max(x,ans[i][j]-1)
print(x)

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w=mp()
s=["
for i in range(h):
    s.append("
s.append("
ans=[[0]*(w+2) for i in range(h+2)]

for i in range(h+2):
    ran=[]
    c=1
    for j in range(1,w+2):
        if s[i][j]==s[i][j-1]:
            c+=1
        else:
            ran.append(c)
            c=1
    ran.append(c)
    p=0
    for j in range(len(ran)):
        for k in range(ran[j]):
            if j%2==1:
                ans[i][p]+=ran[j]
            p+=1

for i in range(w+2):
    ran=[]
    c=1
    for j in range(1,h+2):
        if s[j][i]==s[j-1][i]:
            c+=1
        else:
            ran.append(c)
            c=1
    ran.append(c)
    p=0
    for j in range(len(ran)):
        for k in range(ran[j]):
            if j%2==1:
                ans[p][i]+=ran[j]
            p+=1
print(max(list(itertools.chain.from_iterable(ans)))-1)

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

for h in range(H):
    d = []
    for w in range(W):
        if S[h][w] == ".":
            d.append([h, w])
            if W != w+1: continue
        for h, w in d:
            yoko[h][w] = len(d)
        d = []

for w in range(W):
    d = []
    for h in range(H):
        if S[h][w] == ".":
            d.append([h, w])
            if H != h+1: continue
        for h, w in d:
            tate[h][w] = len(d)
        d = []
        
ans = 0
for h in range(H):
    for w in range(W):
        if ans < yoko[h][w]+tate[h][w]-1:
            ans = yoko[h][w]+tate[h][w]-1
print(ans)

Solution (Python):
h,w=list(map(int,input().split()))
m=[]
for i in range(h):
  mm=[]
  for j in input():
    mm.append(1 if j=="
  m.append(mm)

wl=[[0 for i in range(w)]for j in range(h)]
for i in range(h):
  s=0
  t=0
  while t<w:
    while t<w and m[i][t]==0:
      t+=1
    for j in range(s,t):
      wl[i][j]=t-s
    s=t+1
    t=t+1
mx=0
for i in range(w):
  s=0
  t=0
  while t<h:
    while t<h and m[t][i]==0:
      t+=1
    for j in range(s,t):
      k=wl[j][i]
      if mx<k+t-s:
        mx=k+t-s
    s=t+1
    t=t+1


print(mx-1)

Solution (Python):
h,w=list(map(int,input().split()))
m=[]
for i in range(h):
  mm=[]
  for j in input():
    mm.append(1 if j=="
  m.append(mm)

wl=[[0 for i in range(w)]for j in range(h)]
for i in range(h):
  s=0
  t=0
  while t<w:
    while t<w and m[i][t]==0:
      t+=1
    for j in range(s,t):
      wl[i][j]=t-s
    s=t+1
    t=t+1
mx=0
for i in range(w):
  s=0
  t=0
  while t<h:
    while t<h and m[t][i]==0:
      t+=1
    for j in range(s,t):
      k=wl[j][i]
      if mx<k+t-s:
        mx=k+t-s
    s=t+1
    t=t+1


print(mx-1)

Solution (Python):
h , w = map(int,input().split())
s = [input() for i in range(h)]
coulef = [[0 for i in range(w)] for j in range(h)]
courig = [[0 for i in range(w)] for j in range(h)]
coudow = [[0 for i in range(w)] for j in range(h)]
couup = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    cou = 0
    for j in range(w):
        if s[i][j] == ".":
            cou += 1
            courig[i][j] = cou
        elif s[i][j] == "
            cou = 0
for i in range(h):
    cou = 0
    for j in reversed(range(w)):
        if s[i][j] == ".":
            cou += 1
            coulef[i][j] = cou
        elif s[i][j] == "
            cou = 0
for i in range(w):
    cou = 0
    for j in range(h):
        if s[j][i] == ".":
            cou += 1
            coudow[j][i] = cou
        elif s[j][i] == "
            cou = 0
for i in range(w):
    cou = 0
    for j in reversed(range(h)):
        if s[j][i] == ".":
            cou += 1
            couup[j][i] = cou
        elif s[j][i] == "
            cou = 0

ans = 0
for i in range(h):
    for j in range(w):
        now = couup[i][j]+coudow[i][j]+coulef[i][j]+courig[i][j]
        ans = max(ans,now-3)
print(ans)

Solution (Python):
H,W = map(int,input().split())
grid = [0] * H
for i in range(H):
    grid[i] = 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):
    now = 0
    for x in range(W):
        if grid[i][x] == '.':
            left[i][x] = now
            now += 1
        else:
            now = 0
    now = 0
    for x in range(W-1,-1,-1):
        if grid[i][x] == '.':
            right[i][x] = now
            now += 1
        else:
            now = 0
for x in range(W):
    now = 0
    for y in range(H):
        if grid[y][x] == '.':
            up[y][x] = now
            now += 1
        else:
            now = 0
    now = 0
    for y in range(H-1,-1,-1):
        if grid[y][x] == '.':
            down[y][x] = now
            now += 1
        else:
            now = 0
ans = 0
for y in range(H):
    for x in range(W):
        if grid[y][x] == '.':
            can = 1 + right[y][x] + left[y][x] + up[y][x] + down[y][x]
            ans = max(ans,can)
print(ans)

Solution (Python):
from collections import deque

H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
    D = list(input())
    for w in range(W):
        if D[w] =='
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h = [ [0] * W  for h in range(H) ]

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        for o in range(o_st+1,o_ed):
            Lamp_h[d_h][o] = o_ed-1 - o_st
    
Lamp_w =  [ [0] * H  for w in range(W) ]
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        for o in range(o_st+1,o_ed):
            Lamp_w[d_w][o] = o_ed-1 - o_st
    
ans = 0
for h in range(H):
    for w in range(W):
        ans_ = Lamp_h[h][w] + Lamp_w[w][h] 
        if ans < ans_:
            ans =ans_
        
print(ans-1)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W=MI()
    S=[]
    S.append(["
    for i in range(H):
        s=["
        S.append(s)
    S.append(["
    
    L=[[-1]*(W+2) for _ in range(H+2)]
    R=[[-1]*(W+2) for _ in range(H+2)]
    U=[[-1]*(W+2) for _ in range(H+2)]
    D=[[-1]*(W+2) for _ in range(H+2)]
    
    for i in range(1,H+1):
        for j in range(1,W+1):
            if S[i][j]!="
                L[i][j]=L[i][j-1]+1
                U[i][j]=U[i-1][j]+1
                
    for i in range(H,0,-1):
        for j in range(W,0,-1):
            if S[i][j]!="
                R[i][j]=R[i][j+1]+1
                D[i][j]=D[i+1][j]+1
                
    ans=0
    
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j]!="
                temp=L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
                ans=max(ans,temp)
                
    
    
    
    
    
    
    
    
                
    print(ans)

main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,b1[:,:])", cache=True)
def solve(H, W, S):
    U = np.full(shape=(H + 2, W + 2), fill_value=-1, dtype=np.int64)
    D = np.full(shape=(H + 2, W + 2), fill_value=-1, dtype=np.int64)
    L = np.full(shape=(H + 2, W + 2), fill_value=-1, dtype=np.int64)
    R = np.full(shape=(H + 2, W + 2), fill_value=-1, dtype=np.int64)
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            if not S[h][w]:
                continue
            if U[h][w] == -1:
                U[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if not S[h + d][w]:
                        break
                    U[h + d][w] = d
            if L[h][w] == -1:
                L[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if not S[h][w + d]:
                        break
                    L[h][w + d] = d

    for h in range(H + 1, 0, -1):
        for w in range(W + 1, 0, -1):
            if not S[h][w]:
                continue
            if D[h][w] == -1:
                D[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if not S[h - d][w]:
                        break
                    D[h - d][w] = d
            if R[h][w] == -1:
                R[h][w] = 0
                d = 0
                while True:
                    d += 1
                    if not S[h][w - d]:
                        break
                    R[h][w - d] = d

    dist = U + D + L + R + 1
    ans = np.max(dist)
    return ans


def main():
    H, W = map(int, input().split())
    S = np.zeros(shape=(H + 2, W + 2), dtype=np.bool)
    for i in range(1, H + 1):
        S[i][1:-1] = [s == "." for s in input().rstrip()]

    ans = solve(H, W, S)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
H,W=map(int,input().split())
import heapq
w=[[0 for i in range(W)]for j in range(H)]
for i in range(H):
  S=input()
  for j in range(W):
    w[i][j]=S[j]
    
L=[[0 for i in range(W)] for j in range(H)]
R=[[0 for i in range(W)] for j in range(H)]
U=[[0 for i in range(W)] for j in range(H)]
D=[[0 for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if w[i][j]=='
      L[i][j]=0
    elif 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 w[i][j]=='
      R[i][j]=0
    elif j==W-1:
      R[i][j]=1
    else:
      R[i][j]=R[i][j+1]+1
for i in range(H):
  for j in range(W):
    if w[i][j]=='
      D[i][j]=0
    elif i==0:
      D[i][j]=1
    else:
      D[i][j]=D[i-1][j]+1  
for i in range(H-1,-1,-1):
  for j in range(W):
    if w[i][j]=='
      U[i][j]=0
    elif i==H-1:
      U[i][j]=1
    else:
      U[i][j]=U[i+1][j]+1
m=0

for i in range(H):
  for j in range(W):
    x=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    m=max(x,m)
print(m)

Solution (Python):
h, w = list(map(int, input().split()))
s = []
up, down, right, left = [
    [[0 for _ in range(w)] for _ in range(h)] for _ in range(4)]
for _ in range(h):
    s.append(list(input()))

for j in range(w):
    for i in range(h - 1, -1, -1):
        if s[i][j] == ".":
            if i == h - 1:
                down[i][j] = 1
            else:
                down[i][j] = down[i + 1][j] + 1

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

for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == ".":
            if j == w - 1:
                right[i][j] = 1
            else:
                right[i][j] = right[i][j + 1] + 1

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

res = 0
for i in range(h):
    for j in range(w):
        lit = up[i][j] + down[i][j] + right[i][j] + left[i][j] - 3
        res = max(res, lit)
print(res)

Solution (Python):
from collections import deque

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

s = [list(input()) for _ in range(h)]

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


q = deque([])
c = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1
        
        if s[i][j] == "
            while len(q) > 0:
                x, y = q.pop()
                yoko[x][y] = c
            c = 0



m = 0



c = 0
for j in range(w):
    for i in range(h):
        if s[i][j] == ".":
            q.append((i, j))
            c += 1

        if s[i][j] == "
            while len(q) > 0:
                x, y = q.pop()
                m = max(m, yoko[x][y] + c - 1)
            c = 0


print(m)

Solution (Python):
import sys
from itertools import groupby, chain
def input(): return sys.stdin.readline().rstrip()


def trans(l_2d):
    return [list(x) for x in zip(*l_2d)]


def lamp(arr):
    count = [[] for i in range(len(arr))]
    for i in range(len(arr)):
        lamps = []
        for key, value in groupby(arr[i]):
            n = int(len(list(value)))
            if key == '.':
                lamps += [n]*n
            else:
                lamps += [0]*n
        count[i] = lamps
    return count


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    tate = lamp(s)
    yoko = lamp(trans(s))
    ans=0
    for hh in range(h):
        for ww in range(w):
            ans=max(ans,tate[hh][ww]+yoko[ww][hh]-1)
    print(ans)
        


if __name__ == '__main__':
    main()

Solution (Python):
def make_mat(grid, H, W):
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if grid[h][w] == 1:
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if grid[h][w] == 0:
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())


grid = []
grid_t = [[] for _ in range(W)]
for h in range(H):
    temp = []
    for w, s in enumerate(input().rstrip()):
        if s=="
            temp.append(1)
            grid_t[w].append(1)
        else:
            temp.append(0)
            grid_t[w].append(0)
    grid.append(temp)

A = make_mat(grid, H, W)
B = make_mat(grid_t, W, H)

res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[w][h], res)

print(res-1)

Solution (Python):
from itertools import chain

H,W = map(int,input().split())
grid = tuple(tuple(map(lambda c: c != '

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

for i in range(H):
    s = 0
    for j in range(W):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0

for i in range(H):
    s = 0
    for j in reversed(range(W)):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0

for j in range(W):
    s = 0
    for i in range(H):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0

for j in range(W):
    s = 0
    for i in reversed(range(H)):
        if grid[i][j]:
            scores[i][j] += s
            s += 1
        else:
            s = 0


print(1 + max(chain.from_iterable(scores)))

Solution (Python):
def make_mat(grid, H, W):
    res = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if (grid[h]>>w)&1 == 1:
                for i in range(cnt):
                    res[h][w - 1 - i] = cnt
                cnt = 0
            else:
                cnt += 1
        if (grid[h]>>w)&1 == 0:
            for i in range(cnt):
                res[h][w - i] = cnt
    return res

def max2(x,y):
    return x if x > y else y


import sys
input = sys.stdin.readline

H, W = map(int, input().split())


grid = []
grid_t = [0]*W
for h in range(H):
    temp = 0
    for w, s in enumerate(input().rstrip()):
        if s=="
            temp += 1<<w
            grid_t[w] += 1<<h
    grid.append(temp)

A = make_mat(grid, H, W)
B = make_mat(grid_t, W, H)

res = 0
for h in range(H):
    for w in range(W):
        res = max2(A[h][w] + B[w][h], res)

print(res-1)

Solution (Python):
import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

print(ans)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

H,W = list(map(int,input().split()))
s = [input().rstrip() for _ in range(H)]
maperW = [[0]*W for _ in range(H)]
maperH = [[0]*W for _ in range(H)]



for ih in range(H):
    for iw in range(W):
        if s[ih][iw]=='
            maperW[ih][iw]=0
        elif s[ih][iw]=='.' and iw == 0:
            maperW[ih][iw]=1
        else:
            maperW[ih][iw]=1+maperW[ih][iw-1]
    for iw in range(W-2,-1,-1):
        if maperW[ih][iw+1] == 0 or maperW[ih][iw]==0:
            continue
        else:
            maperW[ih][iw] = maperW[ih][iw+1]

for iw in range(W):
    for ih in range(H):
        if s[ih][iw]=='
            maperH[ih][iw]=0
        elif s[ih][iw]=='.' and ih == 0:
            maperH[ih][iw]=1
        else:
            maperH[ih][iw]=1+maperH[ih-1][iw]
    for ih in range(H-2,-1,-1):
        if maperH[ih+1][iw] == 0 or maperH[ih][iw]==0:
            continue
        else:
            maperH[ih][iw] = maperH[ih+1][iw]
ans = 0
for iw in range(W):
    for ih in range(H):
        ans = max(ans,maperW[ih][iw]+maperH[ih][iw]-1)
print(ans)

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



left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0


right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0

top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0

down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    if g[i][j] =="
      continue
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)

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

num = [[-1 for i in range(w + 2)] for i in range(h + 2)]
for i in range(1, h + 1):
    l = 0
    m = 0
    while l < w + 2:
        if s[i][l] == "
            l += 1
            continue
        else:
            m = l
            while s[i][m] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[i][j] += m - l
                l = m
for i in range(1, w + 1):
    l = 0
    m = 0
    while l < h + 2:
        if s[l][i] == "
            l += 1
            continue
        else:
            m = l
            while s[m][i] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[j][i] += m - l
                l = m
print(max([max([num[i][j] for j in range(w + 2)]) for i in range(h + 2)]))

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
a = [[0]*w for i in range(h)]
b = [[0]*w for i in range(h)]

for i in range(h):
    tmp = 0
    for j in range(w):
        if s[i][j] == '.':
            tmp += 1
            a[i][j] = tmp
        else:
            tmp = 0
    tmp = 0
    for j in range(w-1, -1, -1):
        if s[i][j] == '.':
            tmp = max(tmp, a[i][j])
            a[i][j] = tmp
        else:
            tmp = 0

ans = 0
for j in range(w):
    tmp = 0
    for i in range(h):
        if s[i][j] == '.':
            tmp += 1
            b[i][j] = tmp
        else:
            tmp = 0
    tmp = 0
    for i in range(h-1, -1, -1):
        if s[i][j] == '.':
            tmp = max(tmp, b[i][j])
            b[i][j] = tmp
        else:
            tmp = 0
        ans = max(ans, a[i][j]+b[i][j]-1)
print(ans)

Solution (Python):
h, w = map(int, input().split())
S = [["
for i in range(h):
    S.append(["
S.append(["
Lamp_row = [[0 for i in range(w+2)] for j in range(h+2)]
Lamp_col = [[0 for i in range(w+2)] for j in range(h+2)]


for row in range(h + 2):
    counter = 0
    for col1 in range(w + 1):
        col2 = col1 + 1
        if S[row][col1] == "
            start = col2
            counter += 1
        if S[row][col1] == "." and S[row][col2] == ".":
            counter += 1
        if S[row][col1] == "." and S[row][col2] == "
            end = col2
            for i in range(start, end):
                Lamp_row[row][i] = counter
            counter = 0



for col in range(w + 2):
    counter = 0
    for row1 in range(h + 1):
        row2 = row1 + 1
        if S[row1][col] == "
            start = row2
            counter += 1
        if S[row1][col] == "." and S[row2][col] == ".":
            counter += 1
        if S[row1][col] == "." and S[row2][col] == "
            end = row2
            for i in range(start, end):
                Lamp_col[i][col] = counter
            counter = 0


max_sum = 0
for row in range(h+2):
    for col in range(w+2):
        max_sum = max(max_sum, Lamp_row[row][col] + Lamp_col[row][col] - 1)
print(max_sum)

Solution (Python):
def main():
    import sys
    import numpy as np

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

    h, w = map(int, input().split())
    g = np.zeros((h, w), dtype=int)
    for i in range(h):
        g[i] = [int(s == '.') for s in input()]
    
    L = g.copy()
    R = g.copy()
    U = g.copy()
    D = g.copy()
    
    for i in range(1,h):
        U[i] = (U[i-1]+1)*g[i]
        D[~i] = (D[~i+1]+1)*g[~i]
    for j in range(1, w):
        L[:, j] = (L[:, j-1]+1)*g[:,j]
        R[:, ~j] = (R[:, ~j+1]+1)*g[:, ~j]
     
    ans = np.max(L+R+U+D-3)
    print(ans)
            
                
if __name__ == '__main__':
    main()