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

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

yStarts = [-1] * w
yStrks = [0] * w

for y in range(h):
    xStart = -1
    xStrk = 0

    for x in range(w):
        if grid[y][x] == ".":
            if xStart == -1:
                xStart = x
            xStrk += 1

            if yStarts[x] == -1:
                yStarts[x] = y
            yStrks[x] += 1

        if grid[y][x] == "#" or x == w-1:
            if xStart != -1:
                xEnd = x if grid[y][x] == "." else x-1

                for x2 in range(xStart, xEnd+1):
                    cnt[y][x2] += (xEnd-xStart)+1

            xStart = -1
            xStrk = 0

        if grid[y][x] == "#" or y == h-1:
            if yStarts[x] != -1:
                yEnd = y if grid[y][x] == "." else y-1

                for y2 in range(yStarts[x], yEnd+1):
                    cnt[y2][x] += (yEnd-yStarts[x])+1

            yStarts[x] = -1
            yStrks[x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, cnt[y][x]-1)

print(ans)

Submission status: Accepted

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

r = [[0] * w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if map[i][j] == ".":
      if j == 0:
        r[i][j] = 1
      else:
        r[i][j] = r[i][j-1] + 1

l = [[0] * w for _ in range(h)]
for i in range(h):
  for j in range(w-1, -1, -1):
    if map[i][j] == ".":
      if j == w - 1:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j+1] + 1
        
d = [[0] * w for _ in range(h)]
for i in range(w):
  for j in range(h):
    if map[j][i] == ".":
      if j == 0:
        d[j][i] = 1
      else:
        d[j][i] = d[j-1][i] + 1

u = [[0] * w for _ in range(h)]
for i in range(w):
  for j in range(h-1, -1, -1):
    if map[j][i] == ".":
      if j == h-1:
        u[j][i] = 1
      else:
        u[j][i] = u[j+1][i] + 1
ans = 0
for i in range(h):
  for j in range(w):
    num = l[i][j] + r[i][j] + d[i][j] + u[i][j] - 3
    if num > ans:
      ans = num
print(ans)

Submission status: Accepted

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    h,w=INTM()
    ban=np.zeros((h,w),dtype=np.int16)
    for i in range(h):
        s=STR()
        for i1 in range(len(s)):
            if s[i1]==".":
                ban[i][i1]=1

    left =np.zeros((h,w),dtype=np.int16)
    right=np.zeros((h,w),dtype=np.int16)
    up   =np.zeros((h,w),dtype=np.int16)
    down =np.zeros((h,w),dtype=np.int16)
    #print(up)
    for i in range(w):
        i2=w-1-i
        if i==0:
            left[:,i]=ban[:,i]
            right[:,i2]=ban[:,i2]
        else:
            left[:,i]=ban[:,i]*(left[:,i-1]+1)
            right[:,i2]=ban[:,i2]*(right[:,i2+1]+1)
    
    for i in range(h):
        i2=h-1-i
        if i==0:
            up[i,:]=ban[i,:]
            down[i2,:]=ban[i2,:]
        else:
            up[i,:]=ban[i,:]*(up[i-1,:]+1)
            down[i2,:]=ban[i2,:]*(down[i2+1,:]+1)
    

    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
maps = [['']*(W+2) for _ in range(H+2)]
maps[0] = ['#']*(W+2)
for i in range(H):
    maps[i+1] = ['#']+list(input())+['#']
maps[H+1] = ['#']*(W+2)

ans = 0
L = [[[0, 0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if maps[i+1][j+1] == '#':
            continue
        if j >= 1 and L[i][j-1][1] > 0:
            L[i][j][1] = L[i][j-1][1]
        else:
            u = j+1
            while maps[i+1][u] == '.':
                u += 1
            L[i][j][1] = u-j-1
        if i >= 1 and L[i-1][j][0] > 0:
            L[i][j][0] = L[i-1][j][0]
        else:
            u = i+1
            while maps[u][j+1] == '.':
                u += 1
            L[i][j][0] = u-i-1
        ans = max(ans, L[i][j][0]+L[i][j][1]-1)
print(ans)

Submission status: Accepted

Solution code:
# ABC129 D

H,W=map(int,input().split())
S=[input() for _ in [0]*H]
Lx=[[0]*W for _ in [0]*H]
Ly=[[0]*W for _ in [0]*H]

def search_x(x,y):
    i=x
    while 1:
        i+=1
        if i<W:
            if S[y][i]=='#':
                break
        else:
            break
    return i-x

def search_y(x,y):
    j=y
    while 1:
        j+=1
        if j<H:
            if S[j][x]=='#':
                break
        else:
            break
    return j-y

def set_x(x,y,p):
    i=x
    Lx[y][i]=p
    while 1:
        i+=1
        if i<W:
            if S[y][i]=='#':
                break
            else:
                Lx[y][i]=p
        else:
            break

def set_y(x,y,p):
    j=y
    Ly[j][x]=p
    while 1:
        j+=1
        if j<H:
            if S[j][x]=='#':
                break
            else:
                Ly[j][x]=p
        else:
            break

res=0
for y in range(H):
    for x in range(W):
        if S[y][x]=='.':
            if Lx[y][x]==0:
                w=search_x(x,y)
                set_x(x,y,w)
            if Ly[y][x]==0:
                Ly[y][x]==0
                h=search_y(x,y)
                set_y(x,y,h)
            res=max(Lx[y][x]+Ly[y][x]-1,res)
print(res)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]


up = [[0] * W for i in range(H)]  # あるマスから上に連続していくつ障害物のないマスが続くか
right = [[0] * W for i in range(H)]  # あるマスから右に連続していくつ障害物のないマスが続くか
down = [[0] * W for i in range(H)]  # あるマスから下に連続していくつ障害物のないマスが続くか
left = [[0] * W for i in range(H)]  # あるマスから左に連続していくつ障害物のないマスが続くか


# up
for w in range(W):
    for h in range(1, H):
        if G[h - 1][w] == '#':
            continue
        up[h][w] = up[h - 1][w] + 1

# right
for h in range(H):
    for w in reversed(range(W - 1)):
        if G[h][w + 1] == '#':
            continue
        right[h][w] = right[h][w + 1] + 1

# down
for w in range(W):
    for h in reversed(range(H - 1)):
        if G[h + 1][w] == '#':
            continue
        down[h][w] = down[h + 1][w] + 1

# left
for h in range(H):
    for w in range(1, W):
        if G[h][w - 1] == '#':
            continue
        left[h][w] = left[h][w - 1] + 1


ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == '#':
            continue
        ans = max(ans, up[h][w] + right[h][w] + down[h][w] + left[h][w] + 1)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import numpy as np


# In[2]:


H, W = map(int, input().split())
S = np.ones((H, W), dtype=np.bool)
for i in range(H):
    S[i] = [s == "." for s in input()]


# In[3]:


up = np.zeros((H, W), dtype=np.int16)
down = np.zeros((H, W), dtype=np.int16)
left = np.zeros((H, W), dtype=np.int16)
right = np.zeros((H, W), dtype=np.int16)

# up
up[0, :] = S[0, :]
for h in range(1, H):
    up[h, :] = up[h - 1, :] + 1
    up[h, :] *= S[h, :]

# down
down[H - 1, :] = S[H - 1, :]
for h in reversed(range(0, H - 1)):
    down[h, :] = down[h + 1, :] + 1
    down[h, :] *= S[h, :]

# left
left[:, 0] = S[:, 0]
for w in range(1, W):
    left[:, w] = left[:, w - 1] + 1
    left[:, w] *= S[:, w]

# right
right[:, W - 1] = S[:, W - 1]
for w in reversed(range(0, W - 1)):
    right[:, w] = right[:, w + 1] + 1
    right[:, w] *= S[:, w]

ans = np.max(up + down + left + right - 3)
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

H,W=mint()
S=[input() for _ in range(H)]
C=[[0]*W for _ in range(H)]
for i in range(H):
    l=0
    for r in range(W):
        if S[i][r]=='.':
            continue
        tmp=r-l
        while l<r:
            C[i][l]+=tmp
            l+=1
        l=r+1
    tmp=W-l
    while l<W:
        C[i][l]+=tmp
        l+=1
for j in range(W):
    l=0
    for r in range(H):
        if S[r][j]=='.':
            continue
        tmp=r-l
        while l<r:
            C[l][j]+=tmp
            l+=1
        l=r+1
    tmp=H-l
    while l<H:
        C[l][j]+=tmp
        l+=1
print(max([max(c) for c in C])-1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
l1 = []
for i in range(H):
  s = str(input())
  S.append(s)
  tmp = []
  cnt = 0
  flag = False
  for j in s:
    if flag:
      if j == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if j == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l1.append(tmp)

l2 = []
for i in range(W):
  tmp = []
  cnt = 0
  flag = False
  for j in range(H):
    x = S[j][i]
    if flag:
      if x == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if x == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l2.append(tmp)

ans = [[0]*W for i in range(H)]
m = 0
for i in range(H):
  for j in range(W):
    if (l1[i][j]>0) and (l2[j][i]>0):
      ans[i][j] = l1[i][j] + l2[j][i] - 1
    else:
      ans[i][j] = l1[i][j] + l2[j][i]
    m = max(m, ans[i][j])
print(m)

Submission status: Accepted

Solution code:
import numpy as np

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

t = np.zeros((h, w), dtype=np.int32)
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            t[i][j] = 1

l = np.zeros((h, w), dtype=np.int32)
r = np.zeros((h, w), dtype=np.int32)
u = np.zeros((h, w), dtype=np.int32)
d = np.zeros((h, w), dtype=np.int32)

for i in range(w):
    if i == 0:
        l[:, i] = t[:, i]
    else:
        l[:, i] = (l[:, i-1] + 1) * t[:, i]

for i in range(w-1, -1, -1):
    if i == w-1:
        r[:, i] = t[:, i]
    else:
        r[:, i] = (r[:, i+1] + 1) * t[:, i]

for i in range(h):
    if i == 0:
        u[i] = t[i]
    else:
        u[i] = (u[i-1] + 1) * t[i]

for i in range(h-1, -1, -1):
    if i == h-1:
        d[i] = t[i]
    else:
        d[i] = (d[i+1] + 1) * t[i]

lrud = l+r+u+d-3
print(np.max(lrud))

Submission status: Accepted

Solution code:
import numpy as np
H,W = map(int,input().split())
L = np.zeros((H,W),int)
R = np.zeros((H,W),int)
D = np.zeros((H,W),int)
U = np.zeros((H,W),int)
S = np.array([list(input()) for h in range(H)])=="."

for h in range(H):
  U[h] = S[h]*(U[h-1]+1)
  D[-h-1] = S[-h-1]*(D[-h]+1)

for w in range(W):
  L[:,w] = S[:,w]*(L[:,w-1]+1)
  R[:,-w-1] = S[:,-w-1]*(R[:,-w]+1)

print(np.max(U+D+L+R)-3)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


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


def main():
    h, w = input_int_list()
    grid = []
    for i in range(h):
        grid.append(list(input()))

    ver_cnt = [[None for _ in range(w)] for _ in range(h)]
    hor_cnt = [[None for _ in range(w)] for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                # 横方向の数を埋める
                if not hor_cnt[i][j]:
                    j_end = j
                    cnt = 0
                    while j_end < w:
                        if grid[i][j_end] == "#":
                            break
                        else:
                            j_end += 1
                            cnt += 1
                    for _j in range(j, j_end):
                        hor_cnt[i][_j] = cnt
                # 縦方向の数を埋める
                if not ver_cnt[i][j]:
                    i_end = i
                    cnt = 0
                    while i_end < h:
                        if grid[i_end][j] == "#":
                            break
                        else:
                            i_end += 1
                            cnt += 1
                    for _i in range(i, i_end):
                        ver_cnt[_i][j] = cnt
    ans = 0

    for i in range(h):
        for j in range(w):
            if grid[i][j] != "#":
                ans = max(ans, ver_cnt[i][j] + hor_cnt[i][j] - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

lefts = [[0]*W for i in range(H)]
rights = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if fs[i][j] == "#":
            lefts[i][j] = 0
        if fs[i][j] == ".":
            if j == 0:
                lefts[i][j] = 1
            else:
                lefts[i][j] = lefts[i][j-1] + 1
        jr = W - j - 1
        if fs[i][jr] == "#":
            rights[i][jr] = 0
        else:
            if jr == W-1:
                rights[i][jr] = 1
            else:
                rights[i][jr] = rights[i][jr+1] + 1
ups = [[0]*W for i in range(H)]
downs = [[0]*W for i in range(H)]
for j in range(W):
    for i in range(H):
        if fs[i][j] == "#":
            ups[i][j] = 0
        else:
            if i == 0:
                ups[i][j] = 1
            else:
                ups[i][j] = ups[i-1][j] + 1
        ir = H - i - 1
        if fs[ir][j] == "#":
            downs[ir][j] = 0
        else:
            if ir == H-1:
                downs[ir][j] = 1
            else:
                downs[ir][j] = downs[ir+1][j] + 1


# for l in lefts:
#     print(*l)
# print("-----------")
# for r in rights:
#     print(*r)
# print("updown")
# for l in ups:
#     print(*l)
# print("-----------")
# for r in downs:
#     print(*r)

ans = 0
for i in range(H):
    for j in range(W):
        x = lefts[i][j] + rights[i][j] + ups[i][j] + downs[i][j]
        # print(i,j,lefts[i][j] ,rights[i][j] ,ups[i][j] ,downs[i][j])
        ans = max(x,ans)
print(ans-3)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]

for h in range(H):
  for w in range(W):
    if Gd[h][w]=='#':
      R[h][w]=0
    else:
      if w==0:
        R[h][w]=1
      else:
        R[h][w]=R[h][w-1]+1
    wr=W-w-1
    if Gd[h][wr]=='#':
      L[h][wr]=0
    else:
      if w==0:
        L[h][wr]=1
      else:
        L[h][wr]=L[h][wr+1]+1

for w in range(W):
  for h in range(H):
    if Gd[h][w]=='#':
      D[h][w]=0
    else:
      if h==0:
        D[h][w]=1
      else:
        D[h][w]=D[h-1][w]+1
    hr=H-h-1
    if Gd[hr][w]=='#':
      U[hr][w]=0
    else:
      if h==0:
        U[hr][w]=1
      else:
        U[hr][w]=U[hr+1][w]+1
ret = 0
for w in range(W):
  for h in range(H):
    ret = max(ret, D[h][w]+U[h][w]+R[h][w]+L[h][w]-3)
print(ret)

Submission status: Accepted

Solution code:
import sys
import copy

input = sys.stdin.readline

def mymax(a, b, c=None):
    """
        最大値を返すメソッド.
        値が2, 3つの場合のみ対応している.
    """
    if c == None:
        if a > b:
            return a
        else:
            return b

    if a > b:
        if c > a:
            return c
        else:
            return a
    else:
        if c > b:
            return c
        else:
            return b

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()[:-1]))
    
    L = [[0] * W for _ in range(H)]
    R = copy.deepcopy(L)
    U = copy.deepcopy(L)
    D = copy.deepcopy(L)
    
    for h in range(H):
        cntL, cntR = 0, 0
        for w in range(W):
            wreverse = W - w - 1
            if grid[h][w] == '.':
                cntL += 1
            else:
                cntL = 0
            if grid[h][wreverse] == '.':
                cntR += 1
            else:
                cntR = 0
            L[h][w] = cntL
            R[h][wreverse] = cntR

    for w in range(W):
        cntU, cntD = 0, 0
        for h in range(H):
            hreverse = H - h - 1
            if grid[h][w] == '.':
                cntU += 1
            else:
                cntU = 0
            if grid[hreverse][w] == '.':
                cntD += 1
            else:
                cntD = 0
            U[h][w] = cntU
            D[hreverse][w] = cntD
    
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = mymax(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] - 3)

    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(H, W, Si):
    R = [[0] * W for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]

    # for R
    for h in range(H):
        for w in range(W):
            if Si[h][w] == '#':
                R[h][w] = 0
                continue
            if w == 0:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w - 1] + 1
    # for L
    for h in range(H):
        for w in range(W):
            if Si[h][W - w - 1] == '#':
                L[h][W - w - 1] = 0
                continue
            if w == 0:
                L[h][W - w - 1] = 1
            else:
                L[h][W - w - 1] = L[h][W - w] + 1
    # for D
    for w in range(W):
        for h in range(H):
            if Si[h][w] == '#':
                D[h][w] = 0
                continue
            if h == 0:
                D[h][w] = 1
            else:
                D[h][w] = D[h - 1][w] + 1
    # for U
    for w in range(W):
        for h in range(H):
            if Si[H - h - 1][w] == '#':
                U[H - h - 1][w] = 0
                continue
            if h == 0:
                U[H - h - 1][w] = 1
            else:
                U[H - h - 1][w] = U[H - h][w] + 1

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


if __name__ == '__main__':
    H, W = map(int, input().split())
    Si = [input() for _ in range(H)]

    # # test
    # import func
    # H, W = 2000, 2000
    # Si = [''.join([func.random_str(W, '.')]) for _ in range(H)]
    # for s in Si:
    #     print(s)
    solve(H, W, Si)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(H, W, Si):
    Si = ['#' * (W + 2)] + ['#' + S + '#' for S in Si] + ['#' * (W + 2)]
    lamp_map = [[[-1, -1] for _ in range(W + 2)] for _ in range(H + 2)]
    ans = 0
    for h in range(1, H + 2):
        for w in range(1, W + 2):
            # block
            if Si[h][w] == '#':
                lamp_map[h][w][0] = 0
                lamp_map[h][w][1] = 0
                continue
            # vertical
            if lamp_map[h - 1][w][0] > 0:
                lamp_map[h][w][0] = lamp_map[h - 1][w][0]
            else:
                tmp = 0
                while Si[h + tmp][w] == '.':
                    tmp += 1
                lamp_map[h][w][0] = tmp
            # horizon
            if lamp_map[h][w - 1][1] > 0:
                lamp_map[h][w][1] = lamp_map[h][w - 1][1]
            else:
                tmp = 0
                while Si[h][w + tmp] == '.':
                    tmp += 1
                lamp_map[h][w][1] = tmp
            ans = max(ans, sum(lamp_map[h][w]) - 1)
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Si = [input() for _ in range(H)]

    # # test
    # import func
    # H, W = 2000, 2000
    # Si = [''.join([func.random_str(W, '.')]) for _ in range(H)]
    # for s in Si:
    #     print(s)
    solve(H, W, Si)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
s = [list(input().strip()) for _ in range(h)]
# print(s)

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

for i in range(h):
    cur = 0
    for j in range(w-1,-1,-1):
        if s[i][j] == '#':
            cur = 0
        else:
            cur += 1
        R[i][j] = cur

for i in range(h):
    cur = 0
    for j in range(w):
        if s[i][j] == '#':
            cur = 0
        else:
            cur += 1
        L[i][j] = cur

for j in range(w):
    cur = 0
    for i in range(h):
        if s[i][j] == '#':
            cur = 0
        else:
            cur += 1
        D[i][j] = cur

for j in range(w):
    cur = 0
    for i in range(h-1,-1,-1):
        if s[i][j] == '#':
            cur = 0
        else:
            cur += 1
        U[i][j] = cur

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

Submission status: Accepted

Solution code:
import numpy as np
H, W = map(int,input().split())
l = np.zeros((H,W), dtype=int)
r = np.zeros((H,W), dtype=int)
d = np.zeros((H,W), dtype=int)
u = np.zeros((H,W), dtype=int)
s = np.array([list(input()) for _ in range(H)]) == "."
for i in range(H):
    u[i] = (u[i-1]+1)*s[i]
    d[-i-1] = (d[-i]+1)*s[-i-1]
for i in range(W):
    l[:, i] = (l[:, i-1]+1)*s[:, i]
    r[:, -i-1] = (r[:, -i]+1)*s[:, -i-1]
print(np.max(u+d+l+r)-3)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())

S = [[] for _ in range(n)]

for i in range(n):
    S[i] = list(input())

rows = [[] for _ in range(n)]
cols = [[] for _ in range(m)]

start = [[] for _ in range(n)]
end = [[] for _ in range(n)]

for i in range(n):
    rows[i].append(-1)
    for j in range(m):
        if(S[i][j] == '#'):
            rows[i].append(j)
    rows[i].append(m)

    l = 0
    r = 1
    cnt = 0

    for j in range(m):
        if(S[i][j] != '#'):
            start[i].append(rows[i][r] - rows[i][l])
        else:
            start[i].append(0)
        if(j == rows[i][r]):
            l = r
            r = r + 1
ans = 0
for i in range(m):
    cols[i].append(-1)

    for j in range(n):
        if(S[j][i] == '#'):
            cols[i].append(j)
    cols[i].append(n)

    l = 0
    r = 1
    cnt = 0

    for j in range(n):
        if(S[j][i] != '#'):
            end[j].append(cols[i][r] - cols[i][l])
            # ans = max(ans, start[j][i], end[j][i])
        else:
            end[j].append(0)
        if(j == cols[i][r]):
            l = r
            r = r + 1
        



for i in range(n):
    for j in range(m):
        # if(S[i][j] != '#'):
            ans = max(ans, start[i][j] + end[i][j])

print(ans - 3)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
grid = [input() for i in range(H)]

tate = [[0] * W for i in range(H)]
yoko = [[0] * W for i in range(H)]

for i in range(H):
	for j in range(W):
		if grid[i][j] == ".":
			if tate[i][j] == 0:
				back = 0
				while(1):
					if 0 > i - back or grid[i - back][j] == "#":
						break
					else:
						back += 1
				forth = 0
				while(1):
					if i + forth >= H or grid[i + forth][j] == "#":
						break
					else:
						forth += 1
				for k in range(-back + 1, forth):
					tate[i + k][j] = forth + back - 1
			if yoko[i][j] == 0:
				back = 0
				while(1):
					if 0 > j - back or grid[i][j - back] == "#":
						break
					else:
						back += 1
				forth = 0
				while(1):
					if j + forth >= W or grid[i][j + forth] == "#":
						break
					else:
						forth += 1
				for k in range(-back + 1, forth):
					yoko[i][j + k] = forth + back - 1

maxl = 0
for i in range(H):
	for j in range(W):
		maxl = max(maxl, tate[i][j] + yoko[i][j] - 1)
print(maxl)

Submission status: Accepted

Solution code:
from collections import deque

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

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

yo = [[0] * w for _ in range(h)]
q = deque([])
c = 0

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



m = 0

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

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

Submission status: Accepted

Solution code:
H,W=list(map(int,input().split()))
import numpy as np
m=np.array([[0 if i=="#" else 1 for i in input()] for i in range(H)])
l,r,u,d=np.zeros((4,H,W))
for i in range(H):
   u[i]=(u[i-1]+1)*m[i]
   d[-i-1]=(d[-i]+1)*m[-i-1]
for i in range(W):
   r[:,i]=(r[:,i-1]+1)*m[:,i]
   l[:,-i-1]=(l[:,-i]+1)*m[:,-i-1]
print(int(np.max(u+r+l+d))-3)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

SS = []

for i in range(H):
    S = input() + "#"
    j = 0
    while j < W:
        if S[j] == "#":
            a[i][j] = 0
            j += 1
        else:
            count = 0
            k = j
            while S[k] == ".":
                count += 1
                k += 1
            for l in range(count):
                a[i][j+l] = count
            j = j + count
    SS.append(S)

SS.append("#"*(W+1))

for j in range(W):
    i = 0
    while i < H:
        if SS[i][j] == "#":
            b[i][j] = 0
            i += 1
        else:
            count = 0
            k = i
            while SS[k][j] == ".":
                count += 1
                k += 1
            for l in range(count):
                b[i+l][j] = count
            i = i + count

ans = 0
for i in range(H):
    for j in range(W):
        if ans < a[i][j] + b[i][j]:
            ans = a[i][j] + b[i][j]
print(ans-1)