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: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    H,W=map(int,readline().split())
    grid=[]
    for i in range(H):
        S=readline().strip()
        grid.append(S)
    up=[[0]*W for _ in range(H)]
    down=[[0]*W for _ in range(H)]
    left=[[0]*W for _ in range(H)]
    right=[[0]*W for _ in range(H)]

    #up,left
    for i in range(H):
        for j in range(W):
            if grid[i][j]==".":
                if i==0:
                    up[i][j]=1
                else:
                    up[i][j]=up[i-1][j]+1
            
                if j==0:
                    left[i][j]=1
                else:
                    left[i][j]=left[i][j-1]+1

    #down,right
    for i in range(H-1,-1,-1):
        for j in range(W-1,-1,-1):
            if grid[i][j]==".":
                if i==H-1:
                    down[i][j]=1
                else:
                    down[i][j]=down[i+1][j]+1

                if j==W-1:
                    right[i][j]=1
                else:
                    right[i][j]=right[i][j+1]+1

    res=0
    for i in range(H):
        for j in range(W):
            if grid[i][j]==".":
                res=max(res,up[i][j]+down[i][j]+left[i][j]+right[i][j]-3)
    
    print(res)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    hs = [[0]*w for _ in range(h)]
    ws = [[0]*w for _ in range(h)]

    for i in range(h):
        cums = 0
        for j in range(w):
            if s[i][j] == "#":
                cums = 0
                ws[i][j] = 0
            else:
                cums += 1
                ws[i][j] = cums
        for j in reversed(range(w-1)):
            if ws[i][j+1] != 0 and ws[i][j] != 0:
                ws[i][j] = ws[i][j+1]

    for i in range(w):
        cums = 0
        for j in range(h):
            if s[j][i] == "#":
                cums = 0
                hs[j][i] = 0
            else:
                cums += 1
                hs[j][i] = cums
        for j in reversed(range(h-1)):
            if hs[j+1][i] != 0 and hs[j][i] != 0:
                hs[j][i] = hs[j+1][i]
    print(np.max(np.array(ws) + np.array(hs))-1)


resolve()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
M=[]
ans=[]
for i in range(h):
  M.append(input())
  ans.append([])
  for j in range(w):
    ans[i].append([-1,-1])
max=0
for i in range(h):
  for j in range(w):
    if M[i][j]=='#':
      continue
    else:
      temp=1
      if ans[i][j][0]==-1:
        for k in range(i+1,h):
          if M[k][j]=='.':
            temp+=1
          else:
            break
        for k in range(i,i+temp):
          ans[k][j][0]=temp
      if ans[i][j][1]==-1:
        temp=1
        for k in range(j+1,w):
          if M[i][k]=='.':
            temp+=1
          else:
            break
        for k in range(j,j+temp):
          ans[i][k][1]=temp
      if ans[i][j][0]+ans[i][j][1]-1>max:
        max=ans[i][j][0]+ans[i][j][1]-1
print(max)

Submission status: Time Limit Exceeded

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

L,R=[[0]*W for _ in range(H)], [[0]*W for _ in range(H)]
D,U=[[0]*W for _ in range(H)], [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j==0:
      L[i][j]=1
      R[i][-(j+1)]=1
    else:
      L[i][j]=L[i][j-1]+1
      R[i][-(j+1)]=R[i][-j]+1
    if i==0:
      D[i][j]=1
      U[-(i+1)][j]=1
    else:
      D[i][j]=D[i-1][j]+1
      U[-(i+1)][j]=U[-i][j]+1
    if S[i][j]=="#":
      L[i][j],D[i][j]=0,0
    if S[i][-(j+1)]=="#":
      R[i][-(j+1)]=0
    if S[-(i+1)][j]=="#":
      U[-(i+1)][j]=0

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

Submission status: Time Limit Exceeded

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

def solve(sh,sw):
  if S[sh][sw]=="#":
    return 0
  h,w=sh,sw
  cnt=1
  for i in range(H):
    if h==0:
      break
    h-=1
    if S[h][w]=="#":
      break
    cnt+=1
  h=sh
  for i in range(H):
    if h==H-1:
      break
    h+=1
    if S[h][w]=="#":
      break
    cnt+=1
  h=sh
  for i in range(W):
    if w==0:
      break
    w-=1
    if S[h][w]=="#":
      break
    cnt+=1
  w=sw
  for i in range(W):
    if w==W-1:
      break
    w+=1
    if S[h][w]=="#":
      break
    cnt+=1
  return cnt

ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,solve(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

grid = []

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

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

print(max(
  count_h[h][w] + count_w[h][w] - 1
  for w in range(W)
  for h in range(H)      
))

Submission status: Time Limit Exceeded

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

grid = []

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

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

print(max(
  count_h[h][w] + count_w[h][w] - 1
  for w in range(W)
  for h in range(H)      
))

Submission status: Time Limit Exceeded

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

grid = []

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

for _ in range(H):
  grid.append([x for x in input()])
  

for i in range(H):
  for j in range(W):
    if grid[i][j] == '#':
      count_w[i][j] = 0
      continue
    if j == 0 or grid[i][j - 1] == '#':  # カウントスタート
      count = 0
      k = j
      while k < W and grid[i][k] == '.':
        k += 1
        count += 1
      count_w[i][j] = count      
    else:
      count_w[i][j] = count_w[i][j - 1]  # 左隣と同じ
    
for h in range(H):
  for w in range(W):
    if grid[h][w] == '#':
      count_w[h][w] = 0
      continue
    if w == 0 or grid[h][w - 1] == '#':  # カウントスタート
      count = 0
      k = w
      while k < W and grid[h][k] == '.':
        k += 1
        count += 1
      count_w[h][w] = count      
    else:
      count_w[h][w] = count_w[h][w - 1]  # 左隣と同じ  

for w in range(W):
  for h in range(H):
    if grid[h][w] == '#':
      count_h[h][w] = 0
      continue
    if h == 0 or grid[h - 1][w] == '#':  # カウントスタート
      count = 0
      k = h
      while k < H and grid[k][w] == '.':
        k += 1
        count += 1
      count_h[h][w] = count      
    else:
      count_h[h][w] = count_h[h - 1][w]  # 上と同じ        

print(max(
  count_h[h][w] + count_w[h][w] - 1
  for w in range(W)
  for h in range(H)      
))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy
    h,w = map(int,input().split())
    mp = []
    for i in range(h):
        s = list(map(lambda x:1 if x=='.' else 0,input()))
        mp.append(s)
    mp_c = copy.deepcopy(mp)
    for i in range(h):
        for j in range(1,w):
            if mp[i][j]!=0:
                mp[i][j]+=mp[i][j-1]
    for i in range(h):
        for j in range(1,w):
            if mp[i][w-1-j]!=0:
                if mp[i][w-j]!=0:
                    mp[i][w-1-j]=mp[i][w-j]
    
    for i in range(1,h):
        for j in range(w):
            if mp_c[i][j]!=0:
                mp_c[i][j]+=mp_c[i-1][j]

    for i in range(1,h):
        for j in range(w):
            if mp_c[h-1-i][j]!=0:
                if mp_c[h-i][j]!=0:
                    mp_c[h-1-i][j]=mp_c[h-i][j]

    m = 0
    for i in range(h):
        for j in range(w):
            if mp[i][j]+mp_c[i][j]>m:
                m = mp[i][j]+mp_c[i][j]
    print(m-1)
    
                


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = ['#' * (h + 2)]
for _ in range(h):
    grid.append('#' + input() + '#')
grid.append('#' * (h + 2))
lgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
rgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
dgrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
ugrid = [[0 for _ in range(w+2)] for _ in range(h+2)]
for i in range(1, h+1):
    for j in range(1, w+1):
        if grid[i][j] == '#':
            lgrid[i][j] = 0
            ugrid[i][j] = 0
        else:
            lgrid[i][j] = lgrid[i][j-1] + 1
            ugrid[i][j] = ugrid[i-1][j] + 1
        if grid[i][w+1-j] == '#':
            rgrid[i][w+1-j] = 0
        else:
            rgrid[i][w+1-j] = rgrid[i][w+2-j] + 1
        if grid[h+1-i][j] == '#':
            dgrid[h+1-i][j] = 0
        else:
            dgrid[h+1-i][j] = dgrid[h+2-i][j] + 1        
cnt = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        tmp = lgrid[i][j]+rgrid[i][j]+ugrid[i][j]+dgrid[i][j] - 3
        cnt = max(cnt, tmp)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
t=[''.join([j[i] for j in s]) for i in range(w+2)]
ans,cnt=0,0
for i in range(1,h+1):
  for j in range(1,w+1):
    if s[i][j]=='.':
      ss,tt=s[i],t[j]
      for k in range(1,w+2):
        if ss[j-k]=='.':
          cnt+=1
        else:
          break
      for k in range(1,w+2):
        if ss[j+k]=='.':
          cnt+=1
        else:
          break
      for k in range(1,h+2):
        if tt[i+k]=='.':
          cnt+=1
        else:
          break
      for k in range(1,h+2):
        if tt[i-k]=='.':
          cnt+=1
        else:
          break
      ans=max(ans,cnt)
      cnt=0
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy
    h,w = map(int,input().split())
    mp = []
    for i in range(h):
        s = list(map(lambda x:1 if x=='.' else 0,input()))
        mp.append(s)
    mp_c = copy.deepcopy(mp)
    for i in range(h):
        for j in range(1,w):
            if mp[i][j]!=0:
                mp[i][j]+=mp[i][j-1]
    for i in range(h):
        for j in range(1,w):
            if mp[i][w-1-j]!=0 and mp[i][w-j]:
                mp[i][w-1-j]=mp[i][w-j]
    
    for i in range(1,h):
        for j in range(w):
            if mp_c[i][j]!=0:
                mp_c[i][j]+=mp_c[i-1][j]

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

    m = 0
    for i in range(h):
        for j in range(w):
            if mp[i][j]+mp_c[i][j]>m:
                m = mp[i][j]+mp_c[i][j]
    print(m-1)
    
                


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy
    h,w = map(int,input().split())
    import numpy as np
    mp = []
    for i in range(h):
        s = list(map(lambda x:1 if x=='.' else 0,input()))
        mp.append(s)
    mp_c = copy.deepcopy(mp)
    for i in range(h):
        for j in range(1,w):
            if mp[i][j]!=0:
                mp[i][j]+=mp[i][j-1]
    for i in range(h):
        for j in range(1,w):
            if mp[i][w-1-j]!=0 and mp[i][w-j]:
                mp[i][w-1-j]=mp[i][w-j]
    
    for i in range(1,h):
        for j in range(w):
            if mp_c[i][j]!=0:
                mp_c[i][j]+=mp_c[i-1][j]

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

    print(np.max(np.array(mp)+np.array(mp_c))-1)
                


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy
    h,w = map(int,input().split())
    import numpy as np
    mp = []
    for i in range(h):
        s = list(map(lambda x:1 if x=='.' else 0,input()))
        mp.append(s)
    mp_c = copy.deepcopy(mp)
    for i in range(h):
        for j in range(w):
            if mp[i][j]==0:
                continue
            if j > 0:
                if mp[i][j-1]>0:
                    mp[i][j] = mp[i][j-1]
                else:
                    for k in range(j+1,w):
                        if mp[i][k]>0:
                            mp[i][j]+=1
                        else:
                            break
            else:
                for k in range(j+1,w):
                    if mp[i][k]>0:
                        mp[i][j]+=1
                    else:
                        break
    for i in range(h):
        for j in range(w):
            if mp_c[i][j]==0:
                continue
            if i>0:
                if mp_c[i-1][j]>0:
                    mp_c[i][j]=mp_c[i-1][j]
                else:
                    for k in range(i+1,h):
                        if mp_c[k][j]>0:
                            mp_c[i][j]+=1
                        else:
                            break
            else:
                for k in range(i+1,h):
                    if mp_c[k][j]>0:
                        mp_c[i][j]+=1
                    else:
                        break
    print(np.max(np.array(mp)+np.array(mp_c))-1)
                


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = ['#' * (h + 2)]
for _ in range(h):
    grid.append('#' + input() + '#')
grid.append('#' * (h + 2))
lgrid = {(i, 0): 0 for i in range(1, h + 1)}
rgrid = {(i, w+1): 0 for i in range(1, h + 1)}
dgrid = {(h+1, i): 0 for i in range(1, w + 1)}
ugrid = {(0, i): 0 for i in range(1, w + 1)}
for i in range(1, h+1):
    for j in range(1, w+1):
        if grid[i][j] == '#':
            lgrid[(i, j)] = 0
            ugrid[(i, j)] = 0
        else:
            lgrid[(i, j)] = lgrid[(i, j - 1)] + 1
            ugrid[(i, j)] = ugrid[(i-1, j)] + 1
        if grid[i][w+1-j] == '#':
            rgrid[(i, w+1-j)] = 0
        else:
            rgrid[(i, w+1-j)] = rgrid[(i, w+2-j)] + 1
        if grid[h+1-i][j] == '#':
            dgrid[(h+1-i, j)] = 0
        else:
            dgrid[(h+1-i, j)] = dgrid[(h+2-i, j)] + 1        
cnt = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        tmp = lgrid[(i,j)]+rgrid[(i,j)]+ugrid[(i,j)]+dgrid[(i,j)] - 3
        cnt = max(cnt, tmp)
print(cnt)

Submission status: Time Limit Exceeded

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

    b = [[0] * (w + 2) for _ in range(h + 2)]
    for hi in range(h + 2):
        for wi in range(w + 2):
            if s[hi][wi] == ".":
                b[hi][wi] = 1

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

    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            if b[hi][wi]:
                u[hi][wi] = u[hi-1][wi] + 1
                l[hi][wi] = l[hi][wi-1] + 1

    for hi in range(h, 0, -1):
        for wi in range(w, 0, -1):
            if b[hi][wi]:
                d[hi][wi] = d[hi+1][wi] + 1
                r[hi][wi] = r[hi][wi+1] + 1

    ans = 0
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            cnt = u[hi][wi] + d[hi][wi] + l[hi][wi] + r[hi][wi] - 3
            ans = max(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def main():
    h, w = map(int, input().split())
    s = ["#" * (w + 2)]
    for _ in range(h):
        s.append("#" + input() + "#")
    s.append("#" * (w + 2))

    b = [[0] * (w + 2) for _ in range(h + 2)]
    for hi in range(h + 2):
        for wi in range(w + 2):
            if s[hi][wi] == ".":
                b[hi][wi] = 1

    u = deepcopy(b)
    d = deepcopy(b)
    l = deepcopy(b)
    r = deepcopy(b)
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            if s[hi][wi] == ".":
                u[hi][wi] += u[hi-1][wi]
                l[hi][wi] += l[hi][wi-1]

    for hi in range(h, 0, -1):
        for wi in range(w, 0, -1):
            if s[hi][wi] == ".":
                d[hi][wi] += d[hi+1][wi]
                r[hi][wi] += r[hi][wi+1]

    ans = 0
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            cnt = u[hi][wi] + d[hi][wi] + l[hi][wi] + r[hi][wi] - 3
            ans = max(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

b = [[0] * (w + 2) for _ in range(h + 2)]
for hi in range(h + 2):
    for wi in range(w + 2):
        if s[hi][wi] == ".":
            b[hi][wi] = 1

u = deepcopy(b)
d = deepcopy(b)
l = deepcopy(b)
r = deepcopy(b)
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        if s[hi][wi] == ".":
            u[hi][wi] += u[hi-1][wi]
            l[hi][wi] += l[hi][wi-1]

for hi in range(h, 0, -1):
    for wi in range(w, 0, -1):
        if s[hi][wi] == ".":
            d[hi][wi] += d[hi+1][wi]
            r[hi][wi] += r[hi][wi+1]

ans = 0
for hi in range(1, h + 1):
    for wi in range(1, w + 1):
        cnt = u[hi][wi] + d[hi][wi] + l[hi][wi] + r[hi][wi] - 3
        ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w = mi()
    L = [li() for _ in range(h)]
    memo = [[0] * w for _ in range(h)]
    # x 方向 scan
    for i in range(h):
        # 順方向
        cnt = 0
        for j in range(w):
            if L[i][j] == '#':
                cnt = 0
            else:
                memo[i][j] += cnt
                cnt += 1
        cnt = 1
        # 逆方向
        for j in range(w-1, -1, -1):
            if L[i][j] == '#':
                cnt = 1
            else:
                memo[i][j] += cnt
                cnt += 1
    # y 方向 scan
    for j in range(w):
        # 順方向
        cnt = 0
        for i in range(h):
            if L[i][j] == '#':
                cnt = 0
            else:
                memo[i][j] += cnt
                cnt += 1
        # 逆方向
        cnt = 1
        for i in range(h-1, -1, -1):
            if L[i][j] == '#':
                cnt = 1
            else:
                memo[i][j] += cnt
                cnt += 1
    print(max([max(line) for line in memo]) - 1)    # 縦横で自身を重複して数えている



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(x) for x in input().split()]

temp_list = []
l_list = []
r_list = []
u_list = []
d_list = []
for i in range(h):
    temp_list.append(input())
    l_list.append([0] * w)
    r_list.append([0] * w)
    u_list.append([0] * w)
    d_list.append([0] * w)

for i in range(h):
    for j in range(w):
        if temp_list[i][j] == "#":
            continue

        if i == 0:
            u_list[i][j] = 1
        else:
            u_list[i][j] = u_list[i - 1][j] + 1

        if j == 0:
            l_list[i][j] = 1
        else:
            l_list[i][j] = l_list[i][j - 1] + 1

for i in range(h - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if temp_list[i][j] == "#":
            continue

        if i == h - 1:
            d_list[i][j] = 1
        else:
            d_list[i][j] = d_list[i + 1][j] + 1

        if j == w - 1:
            r_list[i][j] = 1
        else:
            r_list[i][j] = r_list[i][j + 1] + 1

ans = 0
for i in range(h):
    for j in range(w):
        temp = l_list[i][j] + r_list[i][j] + u_list[i][j] + d_list[i][j] - 3
        if ans < temp:
            ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(x) for x in input().split()]

temp_list = []
w_count_list = []
h_count_list = []
for i in range(h):
    temp_list.append(input())
    w_count_list.append([0] * w)
    h_count_list.append([0] * w)

for i in range(h):
    s = 0
    count = 0
    for j in range(w):
        if temp_list[i][j] == ".":
            count += 1
        else:
            for k in range(s, j):
                w_count_list[i][k] = count
            s = j + 1
            count = 0
    else:
        for k in range(s, w):
            w_count_list[i][k] = count

for j in range(w):
    s = 0
    count = 0
    for i in range(h):
        if temp_list[i][j] == ".":
            count += 1
        else:
            for k in range(s, i):
                h_count_list[k][j] = count
            s = i + 1
            count = 0
    else:
        for k in range(s, h):
            h_count_list[k][j] = count

ans = 0
for i in range(h):
    for j in range(w):
        temp = w_count_list[i][j] + h_count_list[i][j] - 1
        if ans < temp:
            ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Lamp
import numpy as np

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

# 横について考える
tblW = np.zeros((h, w),dtype=np.int64)
for i in range(h):
    for j in range(w):
        if s[i, j]=='#' or tblW[i, j]>0:
            continue
        else:
            cnt = 1
            while j+cnt<w and s[i, j+cnt]!='#':
                cnt += 1
            tblW[i, j:j+cnt] = cnt
#print(tblW)
    
# 縦について考える
tblH = np.zeros((h, w),dtype=np.int64)
for j in range(w):
    for i in range(h):
        if s[i, j]=='#' or tblH[i, j]>0:
            continue
        else:
            cnt = 1
            while i+cnt<h and s[i+cnt, j]!='#':
                cnt += 1
            tblH[i:i+cnt, j] = cnt
#print(tblH)

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, tblH[i, j]+tblW[i, j]-1)

print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    done = [0] * w
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if done[j]:
            continue
        k = 0
        while lst[i][j+k] != '#':
            done[j+k] = 1
            k += 1  # kが照らせるマスの長さ
            if j+k > w-1:
                break
        for l in range(k):
            H[i][j+l] = k


for j in range(w):
    done = [0] * h
    for i in range(h):
        if lst[i][j] == '#':
            continue
        if done[i]:
            continue
        k = 0
        while lst[i+k][j] != '#':
            done[i+k] = 1
            k += 1  # kが照らせるマスの長さ
            if i+k > h-1:
                break
        for l in range(k):
            W[i+l][j] = k

ans = 0
for i in range(h):
    for j in range(w):
        if lst[i][j] != '#':
            ans = max(ans, H[i][j] + W[i][j] - 1)

print(ans)

Submission status: Time Limit Exceeded

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

grid = []

for i in range(H):
    s = input()
    r = []
    for j, x in enumerate(s):
        r.append(x)

    grid.append(r)


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

for r in range(H):
    idx = 0

    while idx < W:
        if grid[r][idx] == '.' and (idx == 0 or grid[r][idx - 1] == '#'):
            cnt = 1
            st = idx
            if idx == W - 1 or grid[r][idx + 1] == '#':
                W_cnt[r][idx] = 1
        elif grid[r][idx] == '.' and (idx == W - 1 or grid[r][idx + 1] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                W_cnt[r][i] = cnt
        elif grid[r][idx] == '.':
            cnt += 1
        elif grid[r][idx] == '#':
            pass

        idx += 1

for c in range(W):
    idx = 0

    while idx < H:
        if grid[idx][c] == '.' and (idx == 0 or grid[idx - 1][c] == '#'):
            cnt = 1
            st = idx
            if idx == H - 1 or grid[idx + 1][c] == '#':
                H_cnt[idx][c] = 1
        elif grid[idx][c] == '.' and (idx == H - 1 or grid[idx + 1][c] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                H_cnt[i][c] = cnt
        elif grid[idx][c] == '.':
            cnt += 1
        elif grid[idx][c] == '#':
            pass

        idx += 1

max_ = 0
for r in range(H):
    for c in range(W):
        max_ = max(max_, W_cnt[r][c] + H_cnt[r][c] - 1)

print(max_)

Submission status: Time Limit Exceeded

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

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 i in range(h):
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if j == 0:
            L[i][j] = 1
        else:
            if lst[i][j] == '.':
                L[i][j] = L[i][j-1] + 1
            else:
                continue

for i in range(h):
    for j in range(w)[::-1]:
        if lst[i][j] == '#':
            continue
        if j == w-1:
            R[i][j] = 1
        else:
            if lst[i][j] == '.':
                R[i][j] = R[i][j+1] + 1
            else:
                continue

for i in range(h)[::-1]:
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if i == h-1:
            D[i][j] = 1
        else:
            if lst[i][j] == '.':
                D[i][j] = D[i+1][j] + 1
            else:
                continue

for i in range(h):
    for j in range(w):
        if lst[i][j] == '#':
            continue
        if i == 0:
            U[i][j] = 1
        else:
            if lst[i][j] == '.':
                U[i][j] = U[i-1][j] + 1
            else:
                continue

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

print(ans)