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):

def store_lamp(g, j, v):
    while j >= 0:
        if g[j] is not None:
            break
        g[j] = v
        j -= 1


def store_lamp_h(g, i, j, v):
    while i >= 0:
        if g[i][j] is not None:
            break
        g[i][j] = v
        i -= 1

h, w = map(int, input().split())
s = []

hg = [[None] * w for _ in range(h)]
wg = [[None] * w for _ in range(h)]

for _ in range(h):
    s.append(input())

for i in range(h):
    pre = 0
    for j in range(w):
        if s[i][j] == '
            hg[i][j] = 0
            if pre != 0:
                store_lamp(hg[i], j-1, pre)
            pre = 0
        else:
            pre += 1

    if pre != 0:
        store_lamp(hg[i], w-1, pre)

for j in range(w):
    pre = 0
    for i in range(h):
        if s[i][j] == '
            wg[i][j] = 0
            if pre != 0:
                store_lamp_h(wg, i-1, j, pre)
            pre = 0
        else:
            pre += 1

    if pre != 0:
        store_lamp_h(wg, h-1, j, pre)

l = 0
for hh, wh in zip(hg, wg):
    for hw, ww in zip(hh, wh):
        l = max(l, hw+ww)

print(l-1)

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


S = [[0 for w in range(W)] for h in range(H)]
for h in range(H):
    l = input()
    for w in range(W):
        if l[w]=="
            S[h][w] = 0
        else:
            S[h][w] = 1

Sh = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    se = []
    cnt = 0
    for w,val in enumerate(S[h]):
        if val == 1:
            cnt += 1
            se.append(w)
        else:
            for ww in se:
                Sh[h][ww] = cnt
            cnt = 0
            se = []
    for ww in se:
        Sh[h][ww] = cnt

Sw = [[0 for w in range(W)] for h in range(H)]

for w in range(W):
    se = []
    cnt = 0
    for h in range(H):
        val = S[h][w]
        if val == 1:
            cnt += 1
            se.append(h)
        else:
            for hh in se:
                Sw[hh][w] = cnt
            cnt = 0
            se = []
    for hh in se:
        Sw[hh][w] = cnt


mx = 0
for h in range(H):
    for w in range(W):
        mx = max(Sh[h][w] + Sw[h][w], mx)

print(max((mx-1,0)))

Solution (Python):
from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron, log
from fractions import gcd as pg 
from bisect import insort as ins, bisect_left as bl, bisect_right as br
import sys


raw_input=sys.stdin.readline

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()
f5=lambda : raw_input().split()


def main():
    
    h,w=f1()
    a1=[[0]*w for i in xrange(h)]
    a2=[[0]*w for i in xrange(h)]
    a=[]

    inf=-10**1
    for i in xrange(h):
        a.append(f4())

    for i in xrange(h):
        oc=1
        m=inf
        for j in xrange(w):
            if a[i][j]=='
                k=j-1
                while k>-1 and a[i][k]!='
                    a1[i][k]=oc-1
                    k=k-1
                oc=1
                a1[i][j]=inf
            else:
                a1[i][j]=oc
                oc=oc+1
        if a[i][j]!='
            k=j-1
            while k>-1 and a[i][k]!='
                a1[i][k]=oc-1
                k=k-1

    for i in xrange(w):
        oc=1
        for j in xrange(h):
            if a[j][i]=='
                k=j-1
                while k>-1 and a[k][i]!='
                    a2[k][i]=oc-1
                    k=k-1
                oc=1
                a2[j][i]=inf
            else:
                a2[j][i]=oc
                oc=oc+1
        
        if a[j][i]!='
            k=j-1
            while k>-1 and a[k][i]!='
                a2[k][i]=oc-1
                k=k-1
        
    ans=inf
    for i in xrange(h):
        for j in xrange(w):
            
            
            if a[i][j]!='
                oc=a1[i][j]+a2[i][j]-1
                
                if oc>ans:
                    ans=oc

    
    
    print ans


if __name__ == '__main__':
	main()

Solution (Python):


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

S = [None] * H

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

for i in range(H):
    s_tmp = [-1] * W
    s = input()
    for j, c in enumerate(s):
        if c == "
            s_tmp[j] = 1
        else:
            s_tmp[j] = 0
    S[i] = s_tmp

max_tmp = 0
coord = (-1, -1)
for i in range(H):
    
    tmp = 0
    for j in range(W):
        if S[i][j] == 1:
            tmp = 0
        else:
            tmp += 1
        
        ans[i][j] += tmp
    
    tmp = 0
    for j in reversed(range(W)):
        if S[i][j] == 1:
            tmp = 0
        else:
            tmp += 1
        
        ans[i][j] += tmp


for i in range(W):
    
    tmp = 0
    for j in range(H):
        if S[j][i] == 1:
            tmp = 0
        else:
            tmp += 1
        
        ans[j][i] += tmp
    
    tmp = 0
    for j in reversed(range(H)):
        if S[j][i] == 1:
            tmp = 0
        else:
            tmp += 1
        
        ans[j][i] += tmp
        
        if ans[j][i] > max_tmp:
            
            max_tmp = ans[j][i]
            coord = (j, i)

score = 1

tmp_x = coord[1]
while True:
    tmp_x -= 1
    if tmp_x < 0:
        break
    if S[coord[0]][tmp_x] == 0:
        score += 1
    else:
        break
tmp_x = coord[1]
while True:
    tmp_x += 1
    if tmp_x >= W:
        break
    if S[coord[0]][tmp_x] == 0:
        score += 1
    else:
        break
tmp_y = coord[0]
while True:
    tmp_y -= 1
    if tmp_y < 0:
        break
    if S[tmp_y][coord[1]] == 0:
        score += 1
    else:
        break
tmp_y = coord[0]
while True:
    tmp_y += 1
    if tmp_y >= H:
        break
    if S[tmp_y][coord[1]] == 0:
        score += 1
    else:
        break

print(score)

Solution (Python):
import numpy as np

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

map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1


def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) 
  x = x.cumsum(axis = 1)
  return x


def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) 
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)

answer += F()

map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]


answer += G()

map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)

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

m = list()
mv = list()
mh = list()

for i in range(h):
    mh.append([0] * w)
for i in range(h):
    mv.append([0] * w)

for i in range(h):
    m.append(input())

for i in range(h):
    c = 0
    for j in range(w):
        if m[i][j] == "
            mh[i][j] = 0
            for k in range(c):
                mh[i][j - k - 1] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mh[i][w - 1 - k] = c

for i in range(w):
    c = 0
    for j in range(h):
        if m[j][i] == "
            mv[j][i] = 0
            for k in range(c):
                mv[j - k - 1][i] = c
            c = 0
        else:
            c += 1
    for k in range(c):
        mv[h - 1 - k][i] = c

res = 0
for i in range (h):
    for j in range(w):
        res = max(res, mv[i][j] + mh[i][j])
print(res - 1)

Solution (Python):




H, W = map(int, input().split())
S = []
vertical = []
horizontal = []

for _ in range(H):
    s = input()
    S.append(s)
    vertical.append([-1]*W)
    horizontal.append([-1]*W)

def search_vertical(i, j, current):
    i2 = i

    while not (i2 == H-1 or S[i2+1][j] == '
        i2 += 1
        current += 1

    for i3 in range(i, i2+1):
        vertical[i3][j] = current

def search_horizontal(i, j, current):
    j2 = j

    while  not (j2 == W-1 or S[i][j2+1] == '
        j2 += 1
        current += 1

    for j3 in range(j, j2+1):
        horizontal[i][j3] = current


res = -2
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        if vertical[i][j] == -1:
            search_vertical(i, j, 1)
        if horizontal[i][j] == -1:
            search_horizontal(i, j, 1)
        res = max(res, vertical[i][j] + horizontal[i][j] -1)


print(res)

Solution (Python):


import numpy


def main():
  r, c = map(int, input().split())
  g = numpy.array([[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)])
  g = numpy.array([g, g])

  for x in range(1, c):
    g[0, :, x] += g[0, :, x] * g[0, :, x - 1]

  for x in range(c - 2, -1, -1):
    g[0, :, x] = (g[0, :, x] != 0) * numpy.maximum(g[0, :, x], g[0, :, x + 1])

  for y in range(1, r):
    g[1, y] += g[1, y] * g[1, y - 1]

  for y in range(r - 2, -1, -1):
    g[1, y] = (g[1, y] != 0) * numpy.maximum(g[1, y], g[1, y + 1])

  g = g[0] + g[1]

  print(numpy.max(g) - 1)


if __name__ == '__main__':
  main()

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


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


H,W=rl()
S=[]
for i in range(H):
    S.append(input())

wM = [[0 for w in range(W)] for h in range(H)]
hM = [[0 for w in range(W)] for h in range(H)]

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

for h in range(H):
    cnt = 0
    for w in range(W-1,-1,-1):
        if wM[h][w] > 0:
            cnt = wM[h][w]
        elif wM[h][w] == -1:
            wM[h][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H):
        if S[h][w] == "
        
            hM[h-1][w] = cnt 
            cnt = 0
        else:
            hM[h][w] = -1
            cnt += 1
    if cnt != 0:
        hM[H-1][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H-1,-1,-1):
        if hM[h][w] > 0:
            cnt = hM[h][w]
        elif hM[h][w] == -1:
            hM[h][w] = cnt

ans = 0
for h in range(H):
    for w in range(W):
        ret1 = wM[h][w]
        ret2 = hM[h][w]
        ret = ret1 + ret2
        if ret1 != 0 and ret2 != 0:
            ret -= 1
        ans = max(ans,ret)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
rows,cols = list(map(int,raw_input().split()))
grid=[]
up=[]



for i in range(rows):
	grid.append(raw_input())
	up.append([0 for j in range(cols)])
	
	
	

for c in range(cols):
	count = 1
	for r in range(rows-1,-1,-1):
		if(grid[r][c]=='
			count=1
		else:
			up[r][c]+=count
			count+=1



for c in range(cols):
	count = 1
	for r in range(rows):
		if(grid[r][c]=='
			count=1
		else:
			up[r][c]+=count
			count+=1



for c in range(rows):
	count = 1
	for r in range(cols-1,-1,-1):
		if(grid[c][r]=='
			count=1
		else:
			up[c][r]+=count
			count+=1



for c in range(rows):
	count = 1
	for r in range(cols):
		if(grid[c][r]=='
			count=1
		else:
			up[c][r]+=count
			count+=1
ans = 1
for x in range(rows):
	for y in range(cols):
		if(grid[x][y]=='.'):
			ans=max(ans,(up[x][y]-3))
print(ans)

Solution (Python):

class UnionFind:

    
    def __init__(self, n):
        self.n = n
        self.parent = [-1] * (n + 1)
        self.rnk = [0]*(n+1)

    
    def find_root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find_root(self.parent[x])
            return self.parent[x]

    
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)

        if x == y:
            return

        elif self.rnk[x] > self.rnk[y]:
            self.parent[x] += self.parent[y]  
            self.parent[y] = x

        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y

            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    
    def is_same_tree(self, x, y):
        return self.find_root(x) == self.find_root(y)

    
    def count_nodes(self, x):
        return -self.parent[self.find_root(x)]


def read_input():
    h, w = map(int, input().split())

    board = []
    for i in range(h):
        board.append([0 if c == '.' else 1 for c in input()])

    return h, w, board


def union(vec):
    u = UnionFind(len(vec))

    for i, (v1, v2) in enumerate(zip(vec, vec[1:])):
        if v1 == v2 == 0:
            u.unite(i, i + 1)

    return u

def submit():
    h, w, board = read_input()

    hunions = []
    for i in range(h):
        hunions.append(union(board[i]))

    wunions = []
    for j in range(w):
        v = [board[i][j] for i in range(h)]
        wunions.append(union(v))


    max_lit = 0
    for i in range(h):
        for j in range(w):
            if board[i][j] == 0:
                hv = hunions[i].count_nodes(j)
                wv = wunions[j].count_nodes(i)

                if max_lit < hv + wv - 1:
                    max_lit = hv + wv - 1


    print(max_lit)



if __name__ == '__main__':
    submit()

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

for i in range(h):
    f = 0
    j = 0
    m = 0
    while j < w:
        if s[i][j] == ".":
            if m == 0:
                j += 1
            else:
                f = j
                m = 0
                j += 1
        else:
            if m == 0:
                for p in range(f, j):
                    yoko[i][p] = j - f
            m = 1
            j += 1
    if m == 0:
        for p in range(f, j):
            yoko[i][p] = j - f

for i in range(w):
    f = 0
    j = 0
    m = 0
    while j < h:
        if s[j][i] == ".":
            if m == 0:
                j += 1
            else:
                f = j
                m = 0
                j += 1
        else:
            if m == 0:
                for p in range(f, j):
                    tate[p][i] = j - f
            m = 1
            j += 1
    if m == 0:
        for p in range(f, j):
            tate[p][i] = j - f
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            q = yoko[i][j] + tate[i][j] - 1
            if q > ans:
                ans = q
print(ans)

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

S=[input() for i in range(H)]
color1 = -1
color_list1 = [[-1 for j in range(W)] for i in range(H)]
color_num1 = [0 for i in range(H*W)]
flag=True
for i in range(H):
    for j in range(W):
        if S[i][j]=="
            flag=True
        else:
            if j==0:
                flag=True
            if flag:
                color1+=1
                color_list1[i][j]=color1
                color_num1[color1]+=1
                flag=False
            else:
                color_list1[i][j]=color1
                color_num1[color1]+=1

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

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
g=[["
gg=[[0]*w for _ in range(h)]
for i in range(1,h+1):
  k=1
  for j in range(1,w+1):
    if g[i][j]==".":
      gg[i-1][j-1]=k;k+=1
    else:k=1
  d=gg[i-1][-1]
  for j in range(1,w+1):
    if gg[i-1][-j]!=0:gg[i-1][-j]=d
    elif j!=w:d=gg[i-1][-j-1]
ggg=[[0]*w for _ in range(h)]
for j in range(1,w+1):
  k=1
  for i in range(1,h+1):
    if g[i][j]==".":
      ggg[i-1][j-1]=k;k+=1
    else:k=1
  d=ggg[-1][j-1]
  for i in range(1,h+1):
    if ggg[-i][j-1]!=0:ggg[-i][j-1]=d
    elif i!=h:d=ggg[-i-1][j-1]
ans=0
for i in range(h):
  for j in range(w):ans=max(ans,gg[i][j]+ggg[i][j])
print(ans-1)

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H, W = MI()
    S = [["
    up = [[0] * (W+2) for _ in range(H+2)]
    left = [[0]*(W+2) for _ in range(H+2)]
    right = [[0]*(W+2) for _ in range(H+2)]
    down = [[0] * (W + 2) for _ in range(H + 2)]
    
    for h in range(1, H+1):
        for w in range(1, W + 1):
            if S[h][w] == "
                continue
            else:
                up[h][w] = up[h-1][w] + 1
                left[h][w] = left[h][w-1] + 1
    for h in range(1, H+1)[::-1]:
        for w in range(1, W+1)[::-1]:
            if S[h][w] == "
                continue
            else:
                down[h][w] = down[h+1][w] + 1
                right[h][w] = right[h][w + 1] + 1
                
    ans = 0
    for h in range(1, H+1):
        for w in range(1, W + 1):
            if S[h][w] == ".":
                ans = max(ans, (left[h][w-1] + right[h][w+1]) + (up[h-1][w] + down[h+1][w])+1)
                
                
    print(ans)

    """
    cumsum1 = [[] for _ in range(H)]
    cumsum2 = [[] for _ in range(W)]
    
    for h in range(H):
        for w in range(W):
            if w == 0:
                cumsum1[h].append(int(S[h][w] == "
            else:
                cumsum1[h].append(cumsum1[h][-1] + (S[h][w] == "
            if h == 0:
                cumsum2[w].append(int(S[h][w] == "
            else:
                cumsum2[w].append(cumsum2[w][-1] + (S[h][w] == "
    
    left_right = [[0] * W for _ in range(H)]
    up_down = [[0] * H for _ in range(W)]
    sharp = False:
    for h in range(H):
        for w in range(W):
            if S[h][w] == "
                sharp = True

            else:

    ans=0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "
                continue
            else:
                c1 = cumsum1[h][w]
                c2 = cumsum2[w][h]
                
                b1,b2,b3,b4 = bisect_right(cumsum1[h], c1) ,bisect_left(cumsum1[h], c1) , bisect_right(cumsum2[w], c2) , bisect_left(cumsum2[w], c2)
                num = b1 - b2 + b3 - b4 -3 +(b2==0) + (b4 == 0) 
                
                
                ans=max(ans,num)
    print(ans)"""
if __name__ == '__main__':
    main()

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

h,w = get_nums_l()

lines = sys.stdin.readlines()

xtable = [ [-1]*w for _ in range(h) ]
ytable = [ [-1]*w for _ in range(h) ]
yoko = [0] * (h*w)
tate = [0] * (h*w)

cur = 0
for y in range(h):
    for x in range(w):

        c = lines[y][x]

        if c == ".":
            yoko[cur] += 1
            xtable[y][x] = cur

            if x == (w-1):
                cur += 1
        else:
            cur += 1

cur = 0
for x in range(w):
    for y in range(h):

        c = lines[y][x]

        if c == ".":
            tate[cur] += 1
            ytable[y][x] = cur

            if y == (h-1):
                cur += 1
        else:
            cur += 1
        
ans = 0
for y in range(h):
    for x in range(w):
        if xtable[y][x] != -1:
            v = yoko[xtable[y][x]] + tate[ytable[y][x]] - 1
            
            if ans < v:
                ans = v

print(ans)

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


for h in range(H):
    t = 0
    s = 0
    for w in range(W):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,w):
                    yoko[h][k] = t
            s = w+1
            t = 0
    if t > 0:
        for k in range(s,W):
            yoko[h][k] = t


for w in range(W):
    t = 0
    s = 0
    for h in range(H):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,h):
                    tate[k][w] = t
            s = h+1
            t = 0
    if t > 0:
        for k in range(s,H):
            tate[k][w] = t

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

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

Solution (Python):
sizeI, sizeJ = map(int, input().split())
a = [input().strip() for _ in range(sizeI)]

rowVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for i in range(sizeI):
    for j in range(sizeJ):
        if j == 0:
            rowVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                rowVal[i][j] = rowVal[i][j - 1] + 1
            else:
                rowVal[i][j] = 0
    for j in range(sizeJ - 2, -1, -1):
        if rowVal[i][j] and rowVal[i][j + 1]:
            rowVal[i][j] = rowVal[i][j + 1]

colVal = [[0 for _ in range(sizeJ)] for _ in range(sizeI)]
for j in range(sizeJ):
    for i in range(sizeI):
        if i == 0:
            colVal[i][j] = 1 if a[i][j] == '.' else 0
        else:
            if a[i][j] == '.':
                colVal[i][j] = colVal[i - 1][j] + 1
            else:
                colVal[i][j] = 0
    for i in range(sizeI - 2, -1, -1):
        if colVal[i][j] and colVal[i + 1][j]:
            colVal[i][j] = colVal[i + 1][j]

ret = 0
for i in range(sizeI):
    for j in range(sizeJ):
        ret = max(ret, rowVal[i][j] + colVal[i][j] - 1)
print(ret)

Solution (Python):
n,m = map(int,input().split())
ls = [[x for x in input() + '
yokodp = [[0 for x in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    yoko = 0
    for j in range(m+1):
        if ls[i][j] == '
            yokodp[i][j] = yoko
            yoko = 0
        else:
            yoko += 1
for i in range(n,-1,-1):
    check = 0
    for j in range(m,-1,-1):
        if yokodp[i][j] != 0:
            check = yokodp[i][j]
        if ls[i][j] == '.':
            yokodp[i][j] = check
tatedp = [[0 for x in range(m+1)] for i in range(n+1)]            
for j in range(m+1):
    tate = 0
    for i in range(n+1):
        if ls[i][j] == '
            tatedp[i][j] = tate
            tate = 0
        else:
            tate += 1
for j in range(m,-1,-1):
    for i in range(n,-1,-1):
        if tatedp[i][j] != 0:
            check = tatedp[i][j]
        if ls[i][j] == '.':
            tatedp[i][j] = check
ans = 0
for i in range(n):
    for j in range(m):
        if ls[i][j] == '.':
            ans = max(ans,tatedp[i][j] + yokodp[i][j] - 1)
print(ans)

Solution (Python):

import sys

def solve(H: int, W: int, S: "List[str]"):
    tab = [0 for i in range(H*W)]
    for i in range(W):
        acc0, acc1 = 0, 0
        for j in range(H):
            j2 = H-1-j
            tab[W*j+i] += acc0
            tab[W*j2+i] += acc1
            acc0 = 0 if S[j][i] == "
            acc1 = 0 if S[j2][i] == "
    for j in range(H):
        acc2, acc3 = 0, 0
        for i in range(W):
            i2 = W-1-i
            tab[W*j+i] += acc2
            tab[W*j+i2] += acc3
            if S[j][i] == "
                tab[W*j+i] = -10**10
            else:
                tab[W*j+i] += 1
            acc2 = 0 if S[j][i] == "
            acc3 = 0 if S[j][i2] == "
    
    print(max(max(tab), 0))

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 = [ next(tokens) for _ in range(H) ]  
    solve(H, W, S)

if __name__ == '__main__':
    main()

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

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

for i in range(H):
    t = 0
    for j in range(W):
        t = max(t,k[-i-1][-j-1])
        if S[-i-1][-j-1] == "
            t = 0
            continue
        k[-i-1][-j-1] = t


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

for j in range(W):
    t = 0
    for i in range(H):
        t = max(t,kk[-i-1][-j-1])
        if S[-i-1][-j-1] == "
            t = 0
            continue
        kk[-i-1][-j-1] = t
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue

        ans = max(ans , k[i][j] + kk[i][j] - 1)
print(ans)

Solution (Python):



H, W = list(map(int, input().split()))
data = [''] * H

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

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

for h in range(H):
    w = 0
    while w < W:
        if data[h][w] == '
            w += 1
            continue
        try:
            floor_count = data[h][w:].index('
        except ValueError:
            floor_count = W - w
        for k in range(floor_count):
            lights[h][w+k] += floor_count
        w += floor_count + 1

for w in range(W):
    h = 0
    while h < H:
        if data[h][w] == '
            h += 1
            continue
        floor_count = 1
        for i in range(1, H-h):
            if data[h+i][w] == '
                break
            floor_count += 1
        for k in range(floor_count):
            lights[h+k][w] += floor_count
        h += floor_count + 1

ans = -1
for h in range(H):
    m = max(lights[h])
    if ans < max(lights[h]):
        ans = m
print(ans)

Solution (Python):
import sys
H,W=map(int, raw_input().split())
S=[ sys.stdin.readline().strip() for i in range(H)] 

LSUM=[  [ 0 for w in range(W) ] for h in range(H) ]
RSUM=[  [ 0 for w in range(W) ] for h in range(H) ]
USUM=[ [ 0 for h in range(H) ] for w in range(W) ]
DSUM=[ [ 0 for h in range(H) ] for w in range(W) ]

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


for h in range(H):
	for w in range(W-1,-1,-1):
		if S[h][w]==".":
			if w==W-1:
				RSUM[h][w]=1
			else:
				RSUM[h][w]=RSUM[h][w+1]+1
		elif S[h][w]=="
				RSUM[h][w]=0


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


for w in range(W):
	for h in range(H-1,-1,-1):
		if S[h][w]==".":
			if h==H-1:
				DSUM[w][h]=1
			else:
				DSUM[w][h]=DSUM[w][h+1]+1
		elif S[h][w]=="
				DSUM[w][h]=0



ans=0
for h in range(H):
	for w in range(W):
		ans=max(ans , LSUM[h][w]+RSUM[h][w]+USUM[w][h]+DSUM[w][h]-3 )


print ans

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    field = [[0] * w for _ in range(h)]

    for i, row in enumerate(grid):
        row = row + "
        cnt = row.count("
        idx = -1
        for j in range(cnt + 1):
            idx_next = row.find("
            for k in range(idx + 1, idx_next):
                field[i][k] = idx_next - idx - 1
            idx = idx_next

    m = 0
    for i, row in enumerate(zip(*grid)):
        row = "".join(row) + "
        cnt = row.count("
        idx = -1
        for j in range(cnt + 1):
            idx_next = row.find("
            for k in range(idx + 1, idx_next):
                field[k][i] += idx_next - idx - 1
                if field[k][i] > m:
                    m = field[k][i]
            idx = idx_next
    print(m - 1)


if __name__ == "__main__":
    main()