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



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    H, W = mi()
    S = [input() for i in range(H)]

    left = [[0]*W for _ in range(H)]
    right = [[0]*W for _ in range(H)]
    top = [[0]*W for _ in range(H)]
    bottom = [[0]*W for _ in range(H)]

    # left
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                left[i][j] = 0
                continue

            if j == 0 or S[i][j-1] == '#':
                left[i][j] = 1
            else:
                left[i][j] = left[i][j-1] + 1

    # right
    for i in range(H):
        for j in range(W-1, -1, -1):
            if S[i][j] == '#':
                right[i][j] = 0
                continue

            if j == W-1 or S[i][j+1] == '#':
                right[i][j] = 1
            else:
                right[i][j] = right[i][j+1] + 1

    # top
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                top[i][j] = 0
                continue

            if i == 0 or S[i-1][j] == '#':
                top[i][j] = 1
            else:
                top[i][j] = top[i-1][j] + 1

    # bottom
    for i in range(H-1, -1, -1):
        for j in range(W):
            if S[i][j] == '#':
                bottom[i][j] = 0
                continue

            if i == H-1 or S[i+1][j] == '#':
                bottom[i][j] = 1
            else:
                bottom[i][j] = bottom[i+1][j] + 1


    m = -math.inf

    for i in range(H):
        for j in range(W):
            m = max(left[i][j]+right[i][j]+top[i][j]+bottom[i][j]-3, m)

    print(m)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    H, W = MI()
    room = [["" for j in range(W)] for i in range(H)]
    roomT = [["" for i in range(H)] for j in range(W)]
    num_yoko = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        row = input()

        splited = list(map(len, row.split('#')))
        tmp = 0
        for j in range(W):
            roomT[j][i] = row[j]
            room[i][j] = row[j]
            if row[j] == "#":
                num_yoko[i][j] = 0
                tmp += 1
            else:
                num_yoko[i][j] = splited[tmp]

    ans = 0

    for j in range(W):
        target = roomT[j]
        splited = list(map(len, "".join(target).split('#')))
        tmp = 0
        for i in range(H):
            num_tate = 0 if target[i] == "#" else splited[tmp]
            ans = max(ans,  num_tate + num_yoko[i][j] - 1)
            if target[i] == "#":
                tmp += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    H, W = MI()
    room = [["" for j in range(W)] for i in range(H)]
    roomT = [["" for i in range(H)] for j in range(W)]
    num_yoko = [[0 for j in range(W)] for i in range(H)]
    num_tate = [[0 for j in range(W)] for i in range(H)]
    num_sum = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        row = input()

        splited = list(map(len, row.split('#')))
        tmp = 0
        for j in range(W):
            roomT[j][i] = row[j]
            room[i][j] = row[j]
            if row[j] == "#":
                num_yoko[i][j] = 0
                tmp += 1
            else:
                num_yoko[i][j] = splited[tmp]

    ans = 0

    for j in range(W):
        target = roomT[j]
        splited = list(map(len, "".join(target).split('#')))
        tmp = 0
        for i in range(H):
            if target[i] == "#":
                num_tate[i][j] == 0
                tmp += 1
            else:
                num_tate[i][j] = splited[tmp]

            num_sum[i][j] = num_tate[i][j] + num_yoko[i][j] - 1
            ans = max(ans, num_sum[i][j])
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
h,w = map(int,input().split())
s = (np.array([list(input().strip()) for _ in range(h)])==".").astype(np.int)
l,r,u,d = s.copy(),s.copy(),s.copy(),s.copy()
for i in range(1,w):
  l[:,i] *= l[:,i-1] + 1
  r[:,w-i-1] *= r[:,w-i] + 1

for i in range(1,h):
  u[i] *= u[i-1] + 1
  d[h-i-1] *= d[h-i] + 1
print(max([max(i) for i in l+r+u+d-3]))

Submission status: Accepted

Solution code:
from itertools import chain
H, W = map(int, input().split())
S = [input()+"#" for _ in range(H)]
S.append("#"*(W+1))
A = [[0]*(W) for _ in range(H)]

for i in range(H):
    tmp = 0
    stack = []
    for j in range(W+1):
        if S[i][j] == ".":
            tmp += 1
            stack.append(j)
        # elif j == W-1:
        #     if S[i][j] == ".":
        #         tmp += 1
        #         stack.append(j)
            
        #     while stack:
        #         tmp_j = stack.pop()
        #         A[i][tmp_j] += tmp
        #     tmp = 0
        else:
            while stack:
                tmp_j = stack.pop()
                A[i][tmp_j] += tmp
            tmp = 0
for j in range(W):
    tmp = 0
    stack = []
    for i in range(H+1):
        if S[i][j] == ".":
            tmp += 1
            stack.append(i)
        # elif i == H-1:
        #     if S[i][j] == ".":
        #         tmp += 1
        #         stack.append(i)
        #     while stack:
        #         tmp_i = stack.pop()
        #         A[tmp_i][j] += tmp
        #     tmp = 0
        else:
            while stack:
                tmp_i = stack.pop()
                A[tmp_i][j] += tmp
            tmp = 0
ans = max(chain.from_iterable(A))-1
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain
H, W = map(int, input().split())
S = [input() for _ in range(H)]
A = [[0]*(W) for _ in range(H)]

for i in range(H):
    tmp = 0
    stack = []
    for j in range(W):
        if S[i][j] == "." and j < W-1:
            tmp += 1
            stack.append(j)
        elif j == W-1:
            if S[i][j] == ".":
                tmp += 1
                stack.append(j)
            
            while stack:
                tmp_j = stack.pop()
                A[i][tmp_j] += tmp
            tmp = 0
        else:
            while stack:
                tmp_j = stack.pop()
                A[i][tmp_j] += tmp
            tmp = 0
for j in range(W):
    tmp = 0
    stack = []
    for i in range(H):
        if S[i][j] == "." and i < H-1:
            tmp += 1
            stack.append(i)
        elif i == H-1:
            if S[i][j] == ".":
                tmp += 1
                stack.append(i)
            while stack:
                tmp_i = stack.pop()
                A[tmp_i][j] += tmp
            tmp = 0
        else:
            while stack:
                tmp_i = stack.pop()
                A[tmp_i][j] += tmp
            tmp = 0
ans = max(chain.from_iterable(A))-1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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=["#"*(w+2)]
for i in range(h):
    s.append("#"+input()+"#")
s.append("#"*(w+2))
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)

Submission status: Accepted

Solution code:
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=["#"*(w+2)]
for i in range(h):
    s.append("#"+input()+"#")
s.append("#"*(w+2))
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)

Submission status: Accepted

Solution code:
h,w=list(map(int,input().split()))
m=[]
for i in range(h):
  mm=[]
  for j in input():
    mm.append(1 if j=="#" else 0)
  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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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(["#"]*(W+2))
    for i in range(H):
        s=["#"]+list(input())+["#"]
        S.append(s)
    S.append(["#"]*(W+2))
    
    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)
                
    # for i in range(H+2):
    #     print(L[i])
    # for i in range(H+2):
    #     print(R[i])
    # for i in range(H+2):
    #     print(U[i])
    # for i in range(H+2):
    #     print(D[i])
                
    print(ans)

main()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import chain

H,W = map(int,input().split())
grid = tuple(tuple(map(lambda c: c != '#', input())) for _ in range(H))

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


#left
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
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
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
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)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
s.append(["#"] * (w + 2))
for i in range(h):
    s.append(["#"] + list(input()) + ["#"])
s.append(["#"] * (w + 2))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
S = [["#"] * (w + 2)]
for i in range(h):
    S.append(["#"] + list(input()) + ["#"])
S.append(["#"] * (w + 2))
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)]
#print(S)

for row in range(h + 2):
    counter = 0
    for col1 in range(w + 1):
        col2 = col1 + 1
        if S[row][col1] == "#" and S[row][col2] == ".":
            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
#print(*Lamp_row, sep="\n")
#print()

for col in range(w + 2):
    counter = 0
    for row1 in range(h + 1):
        row2 = row1 + 1
        if S[row1][col] == "#" and S[row2][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
#print(*Lamp_col, sep="\n")

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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

X = []
for i in range(H):
  C = [0 for _ in range(W)]
  count = 0
  for j in range(W-1, -1, -1):
    if M[i][j] == ".":
      count += 1
      C[j] = count
    else:
      count = 0

  r = [0 for _ in range(W)]
  current = C[0]
  for j in range(W):
    if M[i][j] == ".":
      r[j] = current
    else:
      r[j] = 0
      if j + 1 < W:
        current = C[j+1]
  X.append(r)
Y = []
for i in range(W):
  C = [0 for _ in range(H)]
  count = 0
  for j in range(H-1, -1, -1):
    if M[j][i] == ".":
      count += 1
      C[j] = count
    else:
      count = 0

  r = [0 for _ in range(H)]
  current = C[0]
  for j in range(H):
    if M[j][i] == ".":
      r[j] = current
    else:
      r[j] = 0
      if j + 1 < H:
        current = C[j+1]
  Y.append(r)

ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans, X[i][j]+Y[j][i]-1)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s =["#"*(w+2)] + ["#"+input()+"#" for i in range(h)] + ["#"*(w+2)]
# print(s)
ans = 1
opt = [(0,1),(0,-1),(1,0),(-1,0)]
s2 = [[0]*(w+2) for i in range(h+2)]
s3 = [[0]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == "." and s2[i][j] == 0:
            cnt = 0
            for k in opt[0:2]:
                tempy = i
                tempx = j
                while s[tempy+k[0]][tempx+k[1]] == ".":
                    cnt += 1
                    tempy += k[0]
                    tempx += k[1]
            for k in opt[0:2]:
                tempy = i
                tempx = j
                while s[tempy+k[0]][tempx+k[1]] == ".":
                    s2[tempy+k[0]][tempx+k[1]] += cnt
                    tempy += k[0]
                    tempx += k[1]
            s2[i][j] += cnt
        if s[i][j] == "." and s3[i][j] == 0:
            cnt = 0
            for k in opt[2:4]:
                tempy = i
                tempx = j
                while s[tempy+k[0]][tempx+k[1]] == ".":
                    cnt += 1
                    tempy += k[0]
                    tempx += k[1]
            for k in opt[2:4]:
                tempy = i
                tempx = j
                while s[tempy+k[0]][tempx+k[1]] == ".":
                    s3[tempy+k[0]][tempx+k[1]] += cnt
                    tempy += k[0]
                    tempx += k[1]
            s3[i][j] += cnt
        ans = max(ans,1+s2[i][j]+s3[i][j])
# print(s2)
print(ans)