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 d_lamp(H, W, Grid):
    field_horizontal = [[0] * W for _ in range(H)]
    field_vertical = [[0] * W for _ in range(H)]
    field = [[0] * W for _ in range(H)]

    for row in range(H):
        tmp = 0
        for col in range(W):
            if Grid[row][col] == '.':
                tmp += 1
                field_horizontal[row][col] = tmp
            else:
                tmp = 0
        max_val = 0
        for col in range(W - 1, -1, -1):
            if Grid[row][col] == '.':
                max_val = max(max_val, field_horizontal[row][col])
                field_horizontal[row][col] = max_val
            else:
                max_val = 0

    for col in range(W):
        tmp = 0
        for row in range(H):
            if Grid[row][col] == '.':
                tmp += 1
                field_vertical[row][col] = tmp
            else:
                tmp = 0
        max_val = 0
        for row in range(H - 1, -1, -1):
            if Grid[row][col] == '.':
                max_val = max(max_val, field_vertical[row][col])
                field_vertical[row][col] = max_val
            else:
                max_val = 0

    for row in range(H):
        for col in range(W):
            field[row][col] = field_horizontal[row][col] + field_vertical[row][col]

    ans = 0
    for row in range(H):
        for col in range(W):
            ans = max(ans, field[row][col])

    return max(ans - 1, 0)

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(d_lamp(H, W, Grid))

Solution (Python):





H,W = map(int, input().split())
Sn = [[None for _ in range(W)] for _ in range(H)]
for h in range(H):
  s = str(input())
  for w in range(W):
    if s[w] == ".":
      Sn[h][w] = True
    else:
      Sn[h][w] = False

H_cnt = [[1 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(W):
    if Sn[h][w] and w>0:
      H_cnt[h][w] = H_cnt[h][w-1]+1
    elif not Sn[h][w]:
      H_cnt[h][w] = 0
  for w in range(W-2,-1,-1):
    if H_cnt[h][w+1] > 0 and H_cnt[h][w] > 0:
      H_cnt[h][w] = H_cnt[h][w+1]

W_cnt = [[1 for _ in range(W)] for _ in range(H)]
for w in range(W):
  for h in range(H):
    if Sn[h][w] and h>0:
      W_cnt[h][w] = W_cnt[h-1][w]+1
    elif not Sn[h][w]:
      W_cnt[h][w] = 0
  for h in range(H-2,-1,-1):
    if W_cnt[h+1][w] > 0 and W_cnt[h][w] > 0:
      W_cnt[h][w] = W_cnt[h+1][w]


ans = 0
for h in range(H):
  for w in range(W):
    if H_cnt[h][w]*W_cnt[h][w] > 0:
      ans = max(ans, H_cnt[h][w]+W_cnt[h][w]-1)
print(ans)

Solution (Python):
def sol(inp=input):
    res=0
    h,w=map(int,inp().split())
    vers=[None for _ in range(w)]
    atlas=[list(inp()+'
    for i in range(h):
        hol=None
        for j in range(w):
            if atlas[i][j]=='.':
                if hol is None:
                    for j_ in range(j,w+1):
                        if atlas[i][j_]=='
                            hol=j_-j
                            break
                if vers[j] is None:
                    for i_ in range(i,h+1):
                        if atlas[i_][j]=='
                            vers[j]=i_-i
                            break
                res=max(res,hol+vers[j]-1)
            else:
                hol=None
                vers[j]=None
    return '{}'.format(res) 
print(sol())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

H,W=LI()
MP=[input() for _ in range(H)]

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

for i in range(H):
    cnt = 0
    for j in range(W):
        if MP[i][j] == '.':
            cnt += 1
        else:
            for k in range(cnt):
                mp_wid[i][j-k-1] = cnt
            cnt=0
    for k in range(cnt):
        mp_wid[i][-k-1] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if MP[i][j] == '.':
            cnt+=1
        else:
            for k in range(cnt):
                mp_hei[i-k-1][j] = cnt
            cnt=0
    for k in range(cnt):
        mp_hei[-k-1][j] = cnt






res = 0
for i in range(H):
    for j in range(W):
        res = max(res, mp_hei[i][j]+mp_wid[i][j]-1)
print(res)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    h, w = get_li()
    S = get_data(h, [str])
    horizontal = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        indices = [j for j, x in enumerate(S[i]) if x == '
        for a, b in zip([-1] + indices, indices):
            count = b - a - 1
            for j in range(a + 1, b):
                horizontal[i][j] = count
    vertical = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(w):
        indices = [i for i, x in enumerate([S[k][j] for k in range(h)]) if x == '
        for a, b in zip([-1] + indices, indices):
            count = b - a - 1
            for i in range(a + 1, b):
                vertical[i][j] = count
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, horizontal[i][j] + vertical[i][j] - 1)
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

    return ans - 1


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

    
    
    
    


if __name__ == '__main__':
    main()

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

for n in range(H):
  G = G + [input()]
  
L = [[0 for w in range(W)] for h in range(H)]
R = [[0 for w in range(W)] for h in range(H)]
U = [[0 for w in range(W)] for h in range(H)]
D = [[0 for w in range(W)] for h in range(H)]

for i in range(H):
  for j in range(1,W):
    if G[i][j]=='
      L[i][j] = 0
    else:
      L[i][j] = L[i][j-1]+1
        
    if G[i][W-1-j]=='
      R[i][W-1-j] = 0
    else:
      R[i][W-1-j] = R[i][W-j]+1
  
for i in range(1,H):
  for j in range(W):
    if G[i][j]=='
      U[i][j] = 0
    else:
      U[i][j] = U[i-1][j]+1
        
    if G[H-1-i][j]=='
      D[H-1-i][j] = 0
    else:
      D[H-1-i][j] = D[H-i][j]+1

v = [0]*H
for i in range(H):
  v_ = [0]*W
  for j in range(W):
    if G[i][j]=='.':
      v_[j] = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
  v[i] = max(v_)
print(max(v))

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


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

for i in range(H):
    memo = [0] * W
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[j] = tmp
    tmp = 0
    for j in range(W):
        if tmp == 0 and memo[W - 1 - j] > 0:
            tmp = memo[W - 1 - j]
        elif memo[W - 1 - j] == 0:
            tmp = 0
        tab_h[i][W - 1 - j] = tmp

for j in range(W):
    memo = [0] * H
    tmp = 0
    for i in range(H):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[i] = tmp
    tmp = 0
    for i in range(H):
        if tmp == 0 and memo[H - 1 - i] > 0:
            tmp = memo[H - 1 - i]
        elif memo[H - 1 - i] == 0:
            tmp = 0
        tab_v[H - 1 - i][j] = tmp




ans = 1
for i in range(H):
    for j in range(W):
        ans_tmp = tab_h[i][j] + tab_v[i][j] - 1
        if ans < ans_tmp:
            ans = ans_tmp

print(ans)

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
yoko_map=[[0 for i in range(w)] for j in range(h)]
tate_map=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    p=0
    s_=s[i]
    s_=s_.split('
    for x in s_:
        num=len(x)
        for j in range(num):
            yoko_map[i][p]=num
            p+=1
        p+=1
for i in range(w):
    p=0
    s_=''.join([s__[i] for s__ in s])
    s_=s_.split('
    for x in s_:
        num=len(x)
        for j in range(num):
            tate_map[p][i]=num
            p+=1
        p+=1
m=0
for i in range(h):
    yoko_=yoko_map[i]
    tate_=tate_map[i]
    for j in range(w):
        m=max(m,tate_[j]+yoko_[j])
print(max(0,m-1))

Solution (Python):
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

h,w = m()

k = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
	l = list(input())
	for j in range(w):
		if l[j] != "
			k[i][j] = 1

kk = copy.deepcopy(k)
ma = 0
for i in range(h):
	for j in range(1,w):
		if k[i][j] != 0:
			k[i][j] += k[i][j-1]
	for j in range(w-2,-1,-1):
		if k[i][j] != 0 and k[i][j+1]  != 0:
			k[i][j] = k[i][j+1]

for i in range(w):
	for j in range(1,h):
		if kk[j][i] != 0:
			kk[j][i] += kk[j-1][i]
	for j in range(h-2,-1,-1):
		if kk[j][i] != 0 and kk[j+1][i] != 0:
			kk[j][i] = kk[j+1][i]

for i in range(h):
	for j in range(w):
		if ma <= kk[i][j] + k[i][j] - 1:
			ma = kk[i][j] + k[i][j] - 1
print(ma)

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

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

countL2R = [[0 for i in range(w)] for j in range(h)]
countR2L = [[0 for i in range(w)] for j in range(h)]
countU2D = [[0 for i in range(w)] for j in range(h)]
countD2U = [[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] == "
            countL2R[i][j] = -1
            countR2L[i][j] = -1
            countU2D[i][j] = -1
            countD2U[i][j] = -1

for i in range(h):
    for j in range(w):
        if j > 0 and countL2R[i][j] != -1:
                countL2R[i][j] = countL2R[i][j - 1] + 1

        j = w - j - 1
        if j < w - 1 and countR2L[i][j] != -1:
            countR2L[i][j] = countR2L[i][j + 1] + 1

        if i > 0 and countU2D[i][j] != -1:
            countU2D[i][j] = countU2D[i - 1][j] + 1

        I = i
        i = h - i - 1
        if i < h - 1 and countD2U[i][j] != -1:
            countD2U[i][j] = countD2U[i + 1][j] + 1
        i = I

ans = 0
for i in range(h):
    for j in range(w):
        if countD2U[i][j] != -1:
            ans = max(ans, countD2U[i][j] + countU2D[i][j] + countR2L[i][j] + countL2R[i][j])

print(ans + 1)

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

s1=[[0]*w for i in range(h)]
s2=[[0]*w for i in range(h)]

for i in range(h):
    count=0
    now=set()
    for j in range(w):
        if s[i][j]=='
            s1[i][j]==0
            for j in now:
                s1[i][j]=count
            count=0
            now=set()
        else:
            count+=1
            now.add(j)
    for j in now:
        s1[i][j]=count
        
for i in range(w):
    count=0
    now=set()
    for j in range(h):
        if s[j][i]=='
            s2[j][i]==0
            for j in now:
                s2[j][i]=count
            count=0
            now=set()
        else:
            count+=1
            now.add(j)
    for j in now:
        s2[j][i]=count
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, s1[i][j]+s2[i][j]-1)
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
grid=[]
for i in range(H):
    grid.append(list(input()))

L=list2d(H, W, 0)
R=list2d(H, W, 0)
D=list2d(H, W, 0)
U=list2d(H, W, 0)

for i in range(H):
    cnt=0
    for j in range(W):
        if grid[i][j]=='
            cnt=0
        else:
            cnt+=1
        L[i][j]=cnt
for i in range(H):
    cnt=0
    for j in range(W-1, -1, -1):
        if grid[i][j]=='
            cnt=0
        else:
            cnt+=1
        R[i][j]=cnt
for i in range(W):
    cnt=0
    for j in range(H):
        if grid[j][i]=='
            cnt=0
        else:
            cnt+=1
        D[j][i]=cnt
for i in range(W):
    cnt=0
    for j in range(H-1, -1, -1):
        if grid[j][i]=='
            cnt=0
        else:
            cnt+=1
        U[j][i]=cnt

ans=0
for i in range(H):
    for j in range(W):
        if grid[i][j]!='
            ans=max(ans, L[i][j]+R[i][j]+D[i][j]+U[i][j]-3)
print(ans)

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

Solution (Python):
import sys

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

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

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

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)

Solution (Python):
def inpl(): return list(map(int, input().split()))
H, W = inpl()
S = [[0]*(W+2) for _ in range(H+2)]
for h in range(H):
    s = input()
    for w in range(W):
        S[h+1][w+1] = int(s[w] == ".")

WG1 = [[0]*(W+2) for _ in range(H+2)]
HG1 = [[0]*(W+2) for _ in range(H+2)]
WG2 = [[0]*(W+2) for _ in range(H+2)]
HG2 = [[0]*(W+2) for _ in range(H+2)]


for h in range(1, H+1):
    for w in range(1, W+1):
        WG1[h][w] = (WG1[h][w-1] + 1)*S[h][w]
for w in range(1, W+1):
    for h in range(1, H+1):
        HG1[h][w] = (HG1[h-1][w] + 1)*S[h][w]

for h in range(H, 0, -1):
    for w in range(W, 0, -1):
        WG2[h][w] = max(WG2[h][w+1], WG1[h][w])*S[h][w]

for w in range(W, 0, -1):
    for h in range(H, 0, -1):
        HG2[h][w] = max(HG2[h+1][w], HG1[h][w])*S[h][w]

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

Solution (Python):
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
rc = [[0] * W for _ in range(H)]
for i in range(H):
    j = 0
    for k in range(W):
        if S[i][k] == '
            j = k + 1
        else:
            rc[i][j] += 1
    j = 0
    while j < W:
        rc0 = rc[i][j]
        if rc0 < 2:
            j += 1
            continue
        for k in range(j, j + rc0):
            rc[i][k] = rc0
        j += rc0
cc = [[0] * W for _ in range(H)]
for j in range(W):
    i = 0
    for k in range(H):
        if S[k][j] == '
            i = k + 1
        else:
            cc[i][j] += 1
    i = 0
    while i < H:
        cc0 = cc[i][j]
        if cc0 < 2:
            i += 1
            continue
        for k in range(i, i + cc0):
            cc[k][j] = cc0
        i += cc0
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, rc[i][j] + cc[i][j] - 1)
print(ans)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    R, C = read_int_array()
    grid = [read() for _ in range(R)]
    vdp, ldp, ddp, rdp = [[0]*C for _ in range(R)], [[0]*C for _ in range(R)], [[0]*C for _ in range(R)], [[0]*C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if grid[r][c] != b'
                vdp[r][c] = (vdp[r-1][c] if r else 0) + 1
                ldp[r][c] = (ldp[r][c-1] if c else 0) + 1
    for r in range(R-1, -1, -1):
        for c in range(C-1, -1, -1):
            if grid[r][c] != b'
                ddp[r][c] = (ddp[r+1][c] if r + 1 < R else 0) + 1
                rdp[r][c] = (rdp[r][c+1] if c + 1 < C else 0) + 1

    print(max(vdp[r][c] + ldp[r][c] + ddp[r][c] + rdp[r][c] - 3 for r in range(R) for c in range(C) if grid[r][c] != b'





BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]

if __name__ == "__main__":
    main()

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

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

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


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

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

print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [input()+ "

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


for i in range(h+1):
    cnt = 0
    start = 0
    for j in range(w+1):
        if s[i][j] == ".":
            cnt += 1
        else:
            for k in range(start, j):
                yoko[i][k] += cnt
            cnt = 0
            start = j + 1
for i in range(w+1):
    cnt = 0
    start = 0
    for j in range(h+1):
        if s[j][i] == ".":
            cnt += 1
        else:
            for k in range(start, j):
                yoko[k][i] += cnt
            cnt = 0
            start = j + 1
ans = 0
for i in range(h):
    ans = max(max(yoko[i]), ans)
print(ans - 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):
H,W = map(int,input().split())
S = [input() for i in range(H)]

rs = [[0]*W for i in range(H)]
ls = [[0]*W for i in range(H)]
ds = [[0]*W for i in range(H)]
us = [[0]*W for i in range(H)]

for i in range(H):
    tmp = 0
    for j in range(W):
        if S[i][j] == '
            tmp = 0
        else:
            tmp += 1
            rs[i][j] = tmp
    tmp = 0
    for j in reversed(range(W)):
        if S[i][j] == '
            tmp = 0
        else:
            tmp += 1
            ls[i][j] = tmp

for j in range(W):
    tmp = 0
    for i in range(H):
        if S[i][j] == '
            tmp = 0
        else:
            tmp += 1
            ds[i][j] = tmp
    tmp = 0
    for i in reversed(range(H)):
        if S[i][j] == '
            tmp = 0
        else:
            tmp += 1
            us[i][j] = tmp

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
        tmp = rs[i][j] + ls[i][j] + ds[i][j] + us[i][j] - 3
        ans = max(ans, tmp)
print(ans)

Solution (Python):
h, w = map(int, raw_input().strip().split())
grid = [[0 for i in xrange(w)] for j in xrange(h)]

for i in xrange(h):
    grid[i] = list(raw_input().strip())

idxl = [[-1 for i in xrange(h * w)] for j in xrange(4)]


for i in xrange(h):
    left = -1
    for j in xrange(w):
        if grid[i][j] == '
        idxl[0][i * w + j] = left


for i in xrange(h):
    right = w
    for j in xrange(w - 1, -1, -1):
        if grid[i][j] == '
        idxl[1][i * w + j] = right


for j in xrange(w):
    up = -1
    for i in xrange(h):
        if grid[i][j] == '
        idxl[2][i * w + j] = up


for j in xrange(w):
    down = h
    for i in xrange(h - 1, -1, -1):
        if grid[i][j] == '
        idxl[3][i * w + j] = down

ans = 0
for i in xrange(h):
    for j in xrange(w):
        if grid[i][j] == '
        k = i * w + j
        left = j - idxl[0][k]
        right = idxl[1][k] - j
        up = i - idxl[2][k]
        down = idxl[3][k] - i
        cur = left + right + up + down - 3
        ans = max(ans, cur)

print ans

Solution (Python):
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

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

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

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

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

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

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


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

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


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

if __name__ == '__main__':
    main()