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:
H, W = map(int, input().split())
MAP = [[] for _ in range(H)]
L = [[[] for h in range(W)] for _ in range(H)]
R = [[[] for h in range(W)] for _ in range(H)]
D = [[[] for h in range(W)] for _ in range(H)]
U = [[[] for h in range(W)] for _ in range(H)]
for i in range(H):
    MAP[i] = list(input())

for i in range(H):
    for j in range(W):
        if MAP[i][j] == "#":
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j - 1] + 1


for i in range(H):
    for j in reversed(range(W)):
        if MAP[i][j] == "#":
            R[i][j] = 0
        elif j == W - 1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j + 1] + 1

for j in range(W):
    for i in range(H):
        if MAP[i][j] == "#":
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i - 1][j] + 1

for j in range(W):
    for i in reversed(range(H)):
        if MAP[i][j] == "#":
            D[i][j] = 0
        elif i == H - 1:
            D[i][j] = 1
        else:
            D[i][j] = D[i + 1][j] + 1
result = 0
for i in range(H):
    for j in range(W):
        result = max(result, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(result)

Submission status: Time Limit Exceeded

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

tate_value = [[0]*W for i in range(H)]
yoko_value = [[0]*W for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      yoko_value[i][j] = 0
    else:
      if j==0:
        left = 0
        right = W-1
        for k in range(0,W):
          if S[i][k] == '#':
            right = k-1
            break
        yoko_value[i][j] = right+1
      else:
        if S[i][j-1] == '.':
          yoko_value[i][j] = yoko_value[i][j-1]
        else:
          right = W-1
          for k in range(j,W):
            if S[i][k] == '#':
              right = k-1
              break
          yoko_value[i][j] = right-j+1

for j in range(W):
  for i in range(H):
    if S[i][j] == '#':
      tate_value[i][j] = 0
    else:
      if i==0:
        up = 0
        down = H-1
        for k in range(0,H):
          if S[k][j] == '#':
            down = k-1
            break
        tate_value[i][j] = down+1
      else:
        if S[i-1][j] == '.':
          tate_value[i][j] = tate_value[i-1][j]
        else:
          down = H-1
          for k in range(i,H):
            if S[k][j] == '#':
              down = k-1
              break
          tate_value[i][j] = down-i+1
max = 0
for i in range(H):
  for j in range(W):
    temp = yoko_value[i][j] + tate_value[i][j]-1
    if temp>max:
      max = temp
      
print(max)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = []
l_list = []
r_list = []
u_list = [[] for _ in range(h)]
d_list = [[] for _ in range(h)]
for _ in range(h):
    s.append(input())
for i in range(h):
    h_temp = s[i]
    l_temp = []
    l_temp.extend([0 if h_temp[0] == "#" else 1])
    h_temp_rev = list(reversed(h_temp))
    r_temp = []
    r_temp.extend([0 if h_temp_rev[0] == "#" else 1])
    for j in range(w - 1):
        if h_temp[j + 1] == ".":            
            temp = l_temp[j] + 1
        else:
            temp = 0
        l_temp.append(temp)
        if h_temp_rev[j + 1] == ".":            
            temp = r_temp[j] + 1
        else:
            temp = 0
        r_temp.append(temp)
    l_list.append(l_temp)        
    r_list.append(list(reversed(r_temp)))
for i in range(w):
    h_temp = list(map(lambda x: x[i], s))
    u_temp = []
    u_temp.extend([0 if h_temp[0] == "#" else 1])    
    for j in range(h - 1):
        if h_temp[j + 1] == ".":            
            temp = u_temp[j] + 1
        else:
            temp = 0
        u_temp.append(temp)
    for k in range(h):
        u_list[k].append(u_temp[k])
    h_temp = list(reversed(list(map(lambda x: x[i], s))))
    d_temp = []
    d_temp.extend([0 if h_temp[0] == "#" else 1])    
    for j in range(h - 1):
        if h_temp[j + 1] == ".":            
            temp = d_temp[j] + 1
        else:
            temp = 0
        d_temp.append(temp)
    for k in range(h):
        d_list[h - k - 1].append(d_temp[k])
ans = 0
for i in range(h):
    for j in range(w):
        temp = u_list[i][j] + d_list[i][j] + r_list[i][j] + l_list[i][j] - 3
        ans = max(temp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import functools


def _gen_f(line):
    acc = 0
    for c in line:
        if c == "#":
            for _ in range(acc):
                yield acc
            yield 0
            acc = 0
        else:
            acc += 1

    for _ in range(acc):
        yield acc


def f(line):
    return list(_gen_f(line))


H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]


row_wise = list(map(f, grid))
col_wise = list(zip(*map(f, zip(*grid))))

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

# row_wise = np.apply_along_axis(f, 0, grid)
# col_wise = np.apply_along_axis(f, 1, grid)

# for row in grid:
#     print("".join(row))
# print()
# print(row_wise)
# print()
# print(col_wise)
# print()

# ans = (row_wise + col_wise).max() - 1
print(ans)

Submission status: Time Limit Exceeded

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

L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W)] for j in range(H)]
U = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H)]

for i in range(W):
  U[0][i] = 1 if S[0][i]=='.' else 0
  D[-1][i] = 1 if S[-1][i]=='.' else 0

for i in range(H):
  L[i][0] = 1 if S[i][0]=='.' else 0
  R[i][-1] = 1 if S[i][-1]=='.' else 0

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

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

print(ans)

Submission status: Time Limit Exceeded

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

row = [[[-1,-1] for i in range(w)] for j in range(h)]
col = [[[-1,-1] for i in range(w)] for j in range(h)]

for i in range(h):
    tmp = input()
    count_l = 0
    count_r = 0
    for j in range(w):
        if tmp[j] == ".":
            row[i][j][0] = count_l
            count_l += 1
        else:
            count_l = 0
        if tmp[w-1-j] == ".":
            row[i][w-1-j][1] = count_r
            count_r += 1
        else:
            count_r = 0

for j in range(w):
    count_u = 0
    count_d = 0
    for i in range(h):
        if row[i][j][0] >= 0:
            col[i][j][0] = count_u
            count_u += 1
        else:
            count_u = 0
        if row[h-1-i][j][0] >= 0:
            col[h-1-i][j][1] = count_d
            count_d += 1
        else:
            count_d = 0

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, row[i][j][0] + row[i][j][1] + col[i][j][0] + col[i][j][1] + 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input().strip()+'#' for i in range(h)]+['#'*(w+2)]
dp = [[[0]*2 for i in range(w+2)] for i in range(h+2)]
cnt = 0
ans = 0

def dfsw(x,y,cnt):
  if l[x][y+1] == '.':
    cnt += 1
    dp[x][y][0] = dfsw(x,y+1,cnt)
    return dp[x][y][0]
  else:
    dp[x][y][0] = cnt
    return dp[x][y][0]

def dfsh(x,y,cnt):
  if l[x+1][y] == '.':
    cnt += 1
    dp[x][y][1] = dfsh(x+1,y,cnt)
    return dp[x][y][1]
  else:
    dp[x][y][1] = cnt
    return dp[x][y][1]

for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      if dp[i][j][0] == 0:
        dfsw(i,j,1)
      if dp[i][j][1] == 0:
        dfsh(i,j,1)
      ans = max(ans, sum(dp[i][j]) - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys


def calc(a, H, W):
    # 横方向
    for j in range(H):
        prev = 0
        start = 0
        for i in range(W + 1):
            if a[j, i] > 0:
                if prev == 0:
                    start = i
                    prev = 1
            else:
                if prev == 1:
                    num = i - start
                    a[j, start:i] = num
                    prev = 0
    # 縦方向
    for i in range(W):
        prev = 0
        start = 0
        for j in range(H + 1):
            if a[j, i] > 0:
                if prev == 0:
                    start = j
                    prev = 1
            else:
                if prev == 1:
                    num = j - start - 1
                    a[start:j, i] += num
                    prev = 0


def get_data(stream):
    buf = b''
    b = stream.buffer.read(1)
    while b != b'\n':
        buf += b
        b = stream.buffer.read(1)
    H, W = map(int, buf.split())
    c = stream.buffer.read(H * (W + 1))
    arr = np.array(c.split())
    arr = np.frombuffer(arr, dtype='S1').reshape((H, W))
    return H, W, arr


def main():
    H, W, arr = get_data(sys.stdin)
    a = np.zeros((H + 1, W + 1), dtype='i8')
    a[:-1, :-1] = arr == b'.'

    calc(a, H, W)
    print(a.max())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input().strip()+'#' for i in range(h)]+['#'*(w+2)]
dp = [[[0]*2 for i in range(w+2)] for i in range(h+2)]
cnt = 0
ans = 0

def dfsw(x,y,cnt):
  if l[x][y+1] == '.':
    cnt += 1
    dp[x][y][0] = dfsw(x,y+1,cnt)
    return dp[x][y][0]
  else:
    dp[x][y][0] = cnt
    return dp[x][y][0]

def dfsh(x,y,cnt):
  if l[x+1][y] == '.':
    cnt += 1
    dp[x][y][1] = dfsh(x+1,y,cnt)
    return dp[x][y][1]
  else:
    dp[x][y][1] = cnt
    return dp[x][y][1]

for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.' and dp[i][j][0] == 0:
      dfsw(i,j,1)
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.' and dp[i][j][1] == 0:
      dfsh(i,j,1)
    
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans, sum(dp[i][j]) - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
h,*s=open(0)
h,w=int32(h.split())
s=[[u>'#'for u in t]for t in s]
s,a,b,c,d=eval('int32(s),'*5)
for i in range(w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in range(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(amax(a+b+c+d)-3)

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
h,*s=open(0)
h,w=int32(h.split())
s,a,b,c,d=eval('int32([[u>"#"for u in t]for t in s]),'*5)
for i in range(w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in range(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(amax(a+b+c+d)-3)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#入力部
H, W = [int(i) for i in input().split()]
#mapの入力
mymap = [] #mapの配列
for i in range(H):
    mymap.append(list(input()))
Lmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列
Rmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列（逆順）
Umap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列
Dmap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列（逆順）

#Lmap
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1
      
#Rmap
for i in range(H):
  mycnt = 1
  for j in reversed(range(W)):
    if mymap[i][j] == '#':
      Rmap[i][j] = 0
      mycnt = 1
    else: 
      Rmap[i][j] = mycnt
      mycnt += 1

#Dmap & 最大値の探索
for i in range(W):
  mycnt = 1
  for j in reversed(range(H)):
    if mymap[j][i] == '#':
      Dmap[j][i] = 0
      mycnt = 1
    else: 
      Dmap[j][i] = mycnt
      mycnt += 1

#Umap
for i in range(W):
  mycnt = 1
  for j in range(H):
    if mymap[j][i] == '#':
      Umap[j][i] = 0
      mycnt = 1
    else: 
      Umap[j][i] = mycnt
      mycnt += 1
#なぜか最後だけnparray       
print(np.max(np.array(Lmap)+np.array(Rmap)+np.array(Umap)+np.array(Dmap)) -3)

Submission status: Time Limit Exceeded

Solution code:
#入力部
H, W = [int(i) for i in input().split()]
#mapの入力
mymap = [] #mapの配列
for i in range(H):
    mymap.append(list(input()))
Lmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列
Rmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列（逆順）
Umap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列
Dmap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列（逆順）

#Lmap
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1

#Rmap
for i in range(H):
  mycnt = 1
  for j in reversed(range(W)):
    if mymap[i][j] == '#':
      Rmap[i][j] = 0
      mycnt = 1
    else: 
      Rmap[i][j] = mycnt
      mycnt += 1

#Dmap & 最大値の探索
for i in range(W):
  mycnt = 1
  for j in reversed(range(H)):
    if mymap[j][i] == '#':
      Dmap[j][i] = 0
      mycnt = 1
    else: 
      Dmap[j][i] = mycnt
      mycnt += 1

#Umap
for i in range(W):
  mycnt = 1
  for j in range(H):
    if mymap[j][i] == '#':
      Umap[j][i] = 0
      mycnt = 1
    else: 
      Umap[j][i] = mycnt
      mycnt += 1

      
#Lmap  & 最大値の検索
mymax = -99
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1
      #最大値の検索
      if Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] > mymax:
        mymax = Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] 
        
print(mymax-3)

Submission status: Time Limit Exceeded

Solution code:
#入力部
H, W = [int(i) for i in input().split()]
#mapの入力
mymap = [] #mapの配列
for i in range(H):
    mymap.append(list(input()))
Lmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列
Rmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列（逆順）
Umap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列
Dmap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列（逆順）

#Lmap
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1

#Rmap
for i in range(H):
  mycnt = 1
  for j in reversed(range(W)):
    if mymap[i][j] == '#':
      Rmap[i][j] = 0
      mycnt = 1
    else: 
      Rmap[i][j] = mycnt
      mycnt += 1

#Umap
for i in range(W):
  mycnt = 1
  for j in range(H):
    if mymap[j][i] == '#':
      Umap[j][i] = 0
      mycnt = 1
    else: 
      Umap[j][i] = mycnt
      mycnt += 1

#Dmap
for i in range(W):
  mycnt = 1
  for j in reversed(range(H)):
    if mymap[j][i] == '#':
      Dmap[j][i] = 0
      mycnt = 1
    else: 
      Dmap[j][i] = mycnt
      mycnt += 1

      #最大値の検索
mymax = -99
for i in range(H):
  for j in range(W):
    if Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] > mymax:
      mymax = Lmap[i][j]+ Rmap[i][j]+ Umap[i][j]+ Dmap[i][j] 
      
print(mymax-3)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
 
sys.setrecursionlimit(1000000)
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
memo_W = [[0] * W for _ in range(H)]
memo_H = [[0] * W for _ in range(H)]


def D_w(i, j, w):
    if not(0 <= j < W) or S[i][j] == '#':
        return w
    if S[i][j] == '.':
        w = D_w(i, j + 1, w + 1)
        memo_W[i][j] = w
        return w


def D_h(i, j, w):
    if not(0 <= i < H) or S[i][j] == '#':
        return w
    if S[i][j] == '.':
        w = D_h(i + 1, j, w + 1)
        memo_H[i][j] = w
        return w


ans = 0
for i in range(H):
    for j in range(W):
        if memo_W[i][j] == 0:
            memo_W[i][j] = D_w(i, j, 0)
        if memo_H[i][j] == 0:
            memo_H[i][j] == D_h(i, j, 0)
        ans = max(ans, memo_H[i][j] + memo_W[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy


def main():
    h, w = [int(x) for x in input().split()]
    board = [input() for _ in range(h)]
    boardint = [[1 if c == '.' else 0 for c in board[i]] for i in range(h)]
    ansrow = copy.deepcopy(boardint)
    for i in range(h):
        for j in range(1, w):
            ansrow[i][j] = ansrow[i][j - 1] + 1 if boardint[i][j] == 1 else 0
        for j in range(w - 2, -1, -1):
            ansrow[i][j] = ansrow[i][j + 1] if boardint[i][j:j+2] == [1, 1] else ansrow[i][j]
    anscol = copy.deepcopy(boardint)
    for j in range(w):
        for i in range(1, h):
            anscol[i][j] = anscol[i - 1][j] + 1 if boardint[i][j] == 1 else 0
        for i in range(h - 2, -1, -1):
            anscol[i][j] = anscol[i + 1][j] if boardint[i][j] == 1 and boardint[i + 1][j] == 1 else anscol[i][j]
    print(max([ansrow[i][j] + anscol[i][j] - 1 for i in range(h) for j in range(w)]))
    


main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
import numpy as np


def main():
    h, w = [int(x) for x in input().split()]
    board = [input() for _ in range(h)]
    boardint = [[1 if c == '.' else 0 for c in board[i]] for i in range(h)]
    ansrow = copy.deepcopy(boardint)
    for i in range(h):
        for j in range(1, w):
            ansrow[i][j] = ansrow[i][j - 1] + 1 if boardint[i][j] == 1 else 0
        for j in range(w - 2, -1, -1):
            ansrow[i][j] = ansrow[i][j + 1] if boardint[i][j:j+2] == [1, 1] else ansrow[i][j]
    anscol = copy.deepcopy(boardint)
    for j in range(w):
        for i in range(1, h):
            anscol[i][j] = anscol[i - 1][j] + 1 if boardint[i][j] == 1 else 0
        for i in range(h - 2, -1, -1):
            anscol[i][j] = anscol[i + 1][j] if boardint[i][j] == 1 and boardint[i + 1][j] == 1 else anscol[i][j]
    print(np.max(np.array(ansrow) + np.array(anscol)) - 1)


main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [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 S[h][w] == ".":
            L[h][w] = L[h][w-1] + 1
            U[h][w] = U[h-1][w] + 1
        if S[h][W-w-1] == ".":
            R[h][-w-1] = R[h][-w] + 1
        if S[H-h-1][w] == ".":
            D[-h-1][w] = D[-h][w] + 1
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, R[h][w] + L[h][w] + U[h][w] + D[h][w] - 3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import functools


def gen_f(line):
    acc = 0
    for c in line:
        if c == "#":
            for _ in range(acc):
                yield acc
            yield 0
            acc = 0
        else:
            acc += 1

    for _ in range(acc):
        yield acc


def f(line):
    return list(gen_f(line))


H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]
row_wise = np.apply_along_axis(f, 0, np.array(grid))
col_wise = np.apply_along_axis(f, 1, np.array(grid))

# for row in grid:
#     print("".join(row))
# print()
# print(row_wise)
# print()
# print(col_wise)
# print()

ans = (row_wise + col_wise).max() - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(1000000)
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
memo_W = [[0] * W for _ in range(H)]
memo_H = [[0] * W for _ in range(H)]


def D_w(i, j, w):
    if not(0 <= j < W) or S[i][j] == '#':
        return w
    if S[i][j] == '.':
        w = D_w(i, j + 1, w + 1)
        memo_W[i][j] = w
        return w


def D_h(i, j, w):
    if not(0 <= i < H) or S[i][j] == '#':
        return w
    if S[i][j] == '.':
        w = D_h(i + 1, j, w + 1)
        memo_H[i][j] = w
        return w


ans = 0
for i in range(H):
    for j in range(W):
        if memo_W[i][j] == 0:
            memo_W[i][j] = D_w(i, j, 0)
        if memo_H[i][j] == 0:
            memo_H[i][j] == D_h(i, j, 0)
        ans = max(ans, memo_H[i][j] + memo_W[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import functools


def g(acc, x):
    if x == "#":
        res = 0
    elif acc:
        res = acc[-1] + 1
    else:
        res = 1
    acc.append(res)
    return acc


def h(acc, x):
    if x == 0:
        res = 0
    elif acc:
        res = max(acc[-1], x)
    else:
        res = x
    acc.append(res)
    return acc


def f(line):
    res = functools.reduce(g, line, [])
    res = functools.reduce(h, reversed(list(res)), [])
    return list(reversed(list(res)))


H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]


# row_wise = list(map(f, grid))
# col_wise = list(zip(*map(f, zip(*grid))))

## numpy
row_wise = np.apply_along_axis(f, 0, np.array(grid))
col_wise = np.apply_along_axis(f, 1, np.array(grid))

# ans = 0
# for i in range(H):
#     for j in range(W):
#         ans = max(ans, row_wise[i][j] + col_wise[i][j] - 1)

## numpy
ans = (row_wise + col_wise).max() - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#入力部
H, W = [int(i) for i in input().split()]

mymap = [] #mapの配列
myansmap = list(list(-1 for a in range(W)) for b in range(H)) #列方向を探索配列
myansmap2 = list(list(-1 for a in range(W)) for b in range(H)) #行方向を探索配列

#入力しながら，列方向を探索する
for i in range(H):
  myinput =  input()
  for j in range(W):
    if myinput[j] == '#':
      myansmap[i][j] = 0
    elif myinput[j] == '.':
      if myansmap [i][j] == -1 :
        mycnt = 0
        for m in range(j,W):
          if myinput[m] == '#':
            break
          mycnt += 1
      for k in range(j, m+1):
        myansmap[i][k] = mycnt
  mymap.append(myinput)

mymax = -99 #出力用変数

#行方向を探索する
for i in range(H):
  for j in range(W):
    #探索していない箇所について
    if myansmap2 [i][j] == -1:
      mycnt = 0
      for m in range(i,H):
        if myansmap[m][j] == 0:
          break
        mycnt += 1
      for k in range(i, m+1):
        if i > 0 and i < H or  j > 0 and i < W:
          myansmap2[k][j] = mycnt
        else: 
          myansmap2[k][j] = mycnt
    if myansmap[i][j] == 0:
      myansmap2[i][j] = 0

      
    if mymax < myansmap[i][j] + myansmap2[i][j]:
      mymax=myansmap[i][j] + myansmap2[i][j]

print(mymax-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding utf-8 -*-

H, W = map(int, input().split())
field = []    # field[h][w]

for i in range(H):
    field.append(list(input()) + ['#'])
field.append(['#'] * (W + 1))

ans = 0

beam_h = [[0] * W for _ in range(H)]
for h in range(H):
    l = 0
    r = 0
    while r < W + 1:
        num = 0
        while field[h][r] == '.':
            r += 1
            num += 1
        if l != r:
            beam_h[h][l:r] = [num] * num
            ans = max(ans, num)
            l = r
        l += 1
        r += 1

beam_w = [[0] * W for _ in range(H)]
for w in range(W):
    l = 0
    r = 0
    while r < H + 1:
        num = 0
        while field[r][w] == '.':
            r += 1
            num += 1
        if l != r:
            # beam_w[l:r][w] = [num] * num
            for i in range(l, r):
                beam_w[i][w] = num
                ans = max(ans, beam_w[i][w] + beam_h[i][w] - 1)
            l = r
        l += 1
        r += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import functools


def g(acc, x):
    if x == "#":
        res = 0
    elif acc:
        res = acc[-1] + 1
    else:
        res = 1
    acc.append(res)
    return acc


def h(acc, x):
    if x == 0:
        res = 0
    elif acc:
        res = max(acc[-1], x)
    else:
        res = x
    acc.append(res)
    return acc


def f(line):
    res = functools.reduce(g, line, [])
    res = functools.reduce(h, reversed(list(res)), [])
    return list(reversed(list(res)))


H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]

row_wise = list(map(f, grid))
col_wise = list(zip(*map(f, zip(*grid))))

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

# row_wise = np.apply_along_axis(f, 0, grid)
# col_wise = np.apply_along_axis(f, 1, grid)
# print((row_wise + col_wise).max() - 1)


# for row in grid:
#     print(row)
# print()

# for row in row_wise:
#     print(row)
# print()

# for row in col_wise:
#     print(row)

# input_ = grid[0]
# output = f(input_)
# print(f"input : {input_}")
# print(f"output: {output}")


print(ans)

Submission status: Time Limit Exceeded

Solution code:
input_line = input()
H,W = [int(s) for s in input_line.split(' ') if s]
S = []
matrix = [[0 for _ in range(W+1)] for _ in range(H+1)]
matrix_debug = [[0 for _ in range(W+1)] for _ in range(H+1)]

for _ in range(H):
    input_line = input()
    S.append(input_line+'#')
S.append('#'*W)

for i in range(H):
    start = 0
    flag = False
    for j in range(W+1):
        if S[i][j] == '#' and flag:
            for k in range(start, j):
                matrix[i][k] += j-start
            flag = False
        elif S[i][j] == '.' and not flag:
            start = j
            flag = True

# print(matrix)

for i in range(W):
    start = 0
    flag = False
    for j in range(H+1):
        if S[j][i] == '#' and flag:
            for k in range(start, j):
                matrix[k][i] += j-start
                matrix_debug[k][i] += j-start
            flag = False
        elif S[j][i] == '.' and not flag:
            start = j
            flag = True

# print(matrix)
# print(matrix_debug)
# print(max(matrix))

print(max([max(l) for l in matrix])-1)

Submission status: Time Limit Exceeded

Solution code:
#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(10000)

#constant
H, W = list(map(int,input().split()))
S = [input() for _ in range(H)]

#variable

#function
#@lru_cache(maxsize=None)
def Left(i,j,listL):
    if S[i][j] == "#":
        return 0
    elif S[i][j] == ".":
        if j == 0:
            return 1
        else:
            return listL[i][j-1] + 1

def Right(i,j,listR):
    if S[i][j] == "#":
        return 0
    elif S[i][j] == ".":
        if j == W-1:
            return 1
        else:
            return listR[i][j+1] + 1

def Up(i,j,listU):
    if S[i][j] == "#":
        return 0
    elif S[i][j] == ".":
        if i == 0:
            return 1
        else:
            return listU[i-1][j] + 1

def Down(i,j,listD):
    if S[i][j] == "#":
        return 0
    elif S[i][j] == ".":
        if i == H-1:
            return 1
        else:
            return listD[i+1][j] + 1

#class

#main function
def main():
    L = [[None for _ in range(W)] for _ in range(H)]
    R = [[None for _ in range(W)] for _ in range(H)]
    U = [[None for _ in range(W)] for _ in range(H)]
    D = [[None for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            L[i][j] = Left(i,j,L)
            R[i][W-1-j] = Right(i,W-j-1,R)
            U[i][j] = Up(i,j,U)
            D[H-1-i][j] = Down(H-i-1,j,D)
    maxScore = 0
    for i in range(H):
        for j in range(W):
            score = L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
            if score > maxScore:
                maxScore = score
    print(maxScore)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(10000)

#constant
H, W = list(map(int,input().split()))
S = [input() for _ in range(H)]

#variable

#function
@lru_cache(maxsize=None)
def L(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == 1:
            return 1
        else:
            return L(i,j-1) + 1

@lru_cache(maxsize=None)
def R(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == W:
            return 1
        else:
            return R(i,j+1) + 1

@lru_cache(maxsize=None)
def U(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == 1:
            return 1
        else:
            return U(i-1,j) + 1

@lru_cache(maxsize=None)
def D(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == H:
            return 1
        else:
            return D(i+1,j) + 1

#class

#main function
def main():
    for i in range(1,H+1):
        for j in range(1,W+1):
            left = L(i,j)
            right = R(i,j)
            up = U(i,j)
            down = D(i,j)
    maxScore = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            score = L(i,j)+R(i,j)+U(i,j)+D(i,j)-3
            if score > maxScore:
                maxScore = score
    print(maxScore)


if __name__ == "__main__":
    main()