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:
def m():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    G = [[[-1, -1] for _ in range(W)] for _ in range(H)]
    for a in range(H):
        left = 0
        for b in range(W):
            if S[a][b] == '#':
                left = 0
            else:
                G[a][b][0] = left + 1
                left = G[a][b][0]
    for b in range(W):
        top = 0
        for a in range(H):
            if S[a][b] == '#':
                top = 0
            else:
                G[a][b][1] = top + 1
                top = G[a][b][1]

    for i in reversed(range(H)):
        right = 0
        for j in reversed(range(W)):
            if G[i][j][0] == -1:
                right = 0
            else:
                G[i][j][0] = max(G[i][j][0], right)
                right = G[i][j][0]

    for j in reversed(range(W)):
        bot = 0
        for i in reversed(range(H)):
            if G[i][j][1] == -1:
                bot = 0
            else:
                G[i][j][1] = max(G[i][j][1], bot)
                bot = G[i][j][1]
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(sum(G[i][j]), ans)
    return ans-1


print(m())

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
M=[input() for _ in range(H)]
L=[[0]*W for _ in range(H)]
R=[[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):
    count=1
    for j in range(W):
        if M[i][j]=='#':
            count=0
        L[i][j]=count
        count += 1
for i in range(H):
    count=1
    for j in range(W-1,-1,-1):
        if M[i][j]=='#':
            count=0
        R[i][j]=count
        count += 1
for j in range(W):
    count=1
    for i in range(H):
        if M[i][j]=='#':
            count=0
        U[i][j]=count
        count += 1
for j in range(W):
    count=1
    for i in range(H-1,-1,-1):
        if M[i][j]=='#':
            count=0
        D[i][j]=count
        count += 1
ans=0
for i in range(H):
    for j in range(W):
        t=L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
        if ans < t:
            ans=t
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
grid = [readline().rstrip() for i in range(H)]

# 各マスについて、上下左右にそれぞれ照射できるマスがいくつあるか
L = [[0] * W for i in range(H)]
R = [[0] * W for i in range(H)]
U = [[0] * W for i in range(H)]
D = [[0] * W for i in range(H)]

for i in range(H):
  cur = 0
  for j in range(W):
    if grid[i][j] == "#":
      cur = 0
    else:
      cur += 1
    L[i][j] = cur
  cur = 0
  for j in range(W - 1,-1,-1):
    if grid[i][j] == "#":
      cur = 0
    else:
      cur += 1
    R[i][j] = cur
    
for j in range(W):
  cur = 0
  for i in range(H):
    if grid[i][j] == "#":
      cur = 0
    else:
      cur += 1
    U[i][j] = cur
  cur = 0
  for i in range(H - 1,-1,-1):
    if grid[i][j] == "#":
      cur = 0
    else:
      cur += 1
    D[i][j] = cur
    
ans = 0
for i in range(H):
  for j in range(W):
    if ans < L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3:
      ans = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
      
print(ans)

Submission status: Time Limit Exceeded

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

#横
for i in range(1,h+1):
    tmp = 1
    before = 1
    while tmp < w+2:
        if s[i][tmp] == "#":
            before += 1
            tmp += 1
        else:
            while s[i][tmp] != "#":
                tmp += 1
                if tmp == w+2:
                    break
            yoko[i][before:tmp] = [tmp-before] * (tmp - before)
            before = tmp

for i in range(1,w+1):
    tmp = 1
    before = 1
    while tmp < h+2:
        if s[tmp][i] == "#":
            before += 1
            tmp += 1
        else:
            while s[tmp][i] != "#":
                tmp += 1
                if tmp == h+2:
                    break
            tate[i][before:tmp] = [tmp-before] * (tmp - before)
            before = tmp
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        ans = max(ans,tate[j][i]+yoko[i][j]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
g = [str(input()) for _ in range(H)]
LW = [[0] * W for _ in range(H)]
LH = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W):
        if g[h][w] == '.':
            cnt += 1
        else:
            for i in range(1, cnt+1):
                LW[h][w-i] = cnt
            LW[h][w] = 0
            cnt = 0
    else:
        for i in range(cnt):
            LW[h][w-i] = cnt
for w in range(W):
    cnt = 0
    for h in range(H):
        if g[h][w] == '.':
            cnt += 1
        else:
            for i in range(1, cnt+1):
                LH[h-i][w] = cnt
            LH[h][w] = 0
            cnt = 0
    else:
        for i in range(cnt):
            LH[h-i][w] = cnt
ans = 0
for h in range(H):
    for w in range(W):
        if g[h][w] != '#':
            ans = max(ans, LH[h][w] + LW[h][w] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    ans = 0
    for h in range(H):
        for w in range(W):
            if g[h][w] != '#':
                cnt = 1
                dh = [1, -1, 0, 0]
                dw = [0, 0, 1, -1]
                for i in range(4):
                    nh = h + dh[i]
                    nw = w + dw[i]
                    while True:
                        if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                            cnt += 1
                            nh += dh[i]
                            nw += dw[i]
                        else:
                            break
                ans = max(ans, cnt)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
g = [str(input()) for _ in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        if g[h][w] != '#':
            cnt = 1
            dh = [1, -1, 0, 0]
            dw = [0, 0, 1, -1]
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                while True:
                    if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                        cnt += 1
                        nh += dh[i]
                        nw += dw[i]
                    else:
                        break
            ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    tmp = 0
    for j in range(w):
        if s[i][j] == "#":
            tmp = 0
            continue
        else:
            tmp += 1
            score_h[i][j] = tmp

for i in range(h):
    for j in range(w - 1, 0, -1):
        if score_h[i][j] == 0 or score_h[i][j - 1] == 0:
            continue
        else:
            score_h[i][j - 1] = score_h[i][j]

sT = list(zip(*s))
sT = [list(x) for x in sT]

for i in range(w):
    tmp = 0
    for j in range(h):
        if sT[i][j] == "#":
            tmp = 0
            continue
        else:
            tmp += 1
            score_w[i][j] = tmp

for i in range(w):
    for j in range(h - 1, 0, -1):
        if score_w[i][j] == 0 or score_w[i][j - 1] == 0:
            continue
        else:
            score_w[i][j - 1] = score_w[i][j]

score_w = list(zip(*score_w))
score_w = [list(x) for x in score_w]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
s = np.array([list(map(str, input().rstrip())) for _ in range(h)])

s = np.array([x == "." for x in s])

score_h = np.zeros([h, w], int)
score_w = np.zeros([w, h], int)

for i in range(h):
    tmp = 0
    for j in range(w):
        if not s[i, j]:
            tmp = 0
            continue
        else:
            tmp += 1
            score_h[i, j] = tmp

for i in range(h):
    for j in range(w - 1, 0, -1):
        if score_h[i, j] == 0 or score_h[i, j - 1] == 0:
            continue
        else:
            score_h[i, j - 1] = score_h[i, j]

s = s.T

for i in range(w):
    tmp = 0
    for j in range(h):
        if not s[i, j]:
            tmp = 0
            continue
        else:
            tmp += 1
            score_w[i, j] = tmp

for i in range(w):
    for j in range(h - 1, 0, -1):
        if score_w[i, j] == 0 or score_w[i, j - 1] == 0:
            continue
        else:
            score_w[i, j - 1] = score_w[i, j]

score_w = score_w.T

print((score_h + score_w - 1).max())

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W = NMI()
    grid = [input() for _ in range(H)]
    L = make_grid(H, W, 0)
    R = make_grid(H, W, 0)
    U = make_grid(H, W, 0)
    D = make_grid(H, W, 0)

    # left
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "#":
                continue
            elif w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w-1] + 1

    # right
    for h in range(H):
        for w in range(W-1, -1, -1):
            if grid[h][w] == "#":
                continue
            elif w == W-1:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w+1] + 1

    # up
    for w in range(W):
        for h in range(H):
            if grid[h][w] == "#":
                continue
            elif h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h-1][w] + 1

    # down
    for w in range(W):
        for h in range(H-1, -1, -1):
            if grid[h][w] == "#":
                continue
            elif h == H-1:
                D[h][w] = 1
            else:
                D[h][w] = D[h+1][w] + 1

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
H,W = map(int,input().split())
grid = []
for _ in range(H):
  grid.append(list(input()))

def dfs(i,j,direction):
  if i<0 or j<0 or i>=H or j>=W:
    return 0
  if grid[i][j] == "#":
    return 0

  if direction == "L":
    return 1 + dfs(i,j-1,direction)
  elif direction == "R":
    return 1 + dfs(i,j+1,direction)
  elif direction == "U":
    return 1 + dfs(i+1,j,direction)
  else:
    return 1 + dfs(i-1,j,direction)

res = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] != "#":
      step = 1
      for d in ["L","R","U","D"]:
        ni,nj = i,j
        if d=="L": nj = j-1
        if d=="R": nj = j+1
        if d=="U": ni = i+1
        if d=="D": ni = i-1
        step += dfs(ni,nj,d)
      res = max(res, step)
      if res == H+W-1:
        print(res)
        exit()

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
H,W = map(int,input().split())
grid = []
for _ in range(H):
  grid.append(list(input()))

def dfs(i,j,direction):
  if i<0 or j<0 or i>=H or j>=W:
    return 0
  if grid[i][j] == "#":
    return 0

  if direction == "L":
    return 1 + dfs(i,j-1,direction)
  elif direction == "R":
    return 1 + dfs(i,j+1,direction)
  elif direction == "U":
    return 1 + dfs(i+1,j,direction)
  else:
    return 1 + dfs(i-1,j,direction)

res = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] != "#":
      step = 1
      for d in ["L","R","U","D"]:
        ni,nj = i,j
        if d=="L": nj = j-1
        if d=="R": nj = j+1
        if d=="U": ni = i+1
        if d=="D": ni = i-1
        step += dfs(ni,nj,d)
      res = max(res, step)

print(res)

Submission status: Time Limit Exceeded

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

S = [[] for _ in range(H)]
for i in range(H):
    S[i] = input()

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 S[i][j] == "." and i - 1 < 0:
            D[i][j] = 1
        elif S[i][j] == "." and i - 1 >= 0:
            D[i][j] = D[i-1][j] + 1
        if S[i][j] == "." and j - 1 < 0:
            L[i][j] = 1
        elif S[i][j] == "." and j - 1 >= 0:
            L[i][j] = L[i][j-1] + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
        if S[i][j] == "." and i + 1 >= H:
            U[i][j] = 1
        elif S[i][j] == "." and i + 1 < H:
            U[i][j] = U[i+1][j] + 1
        if S[i][j] == "." and j + 1 >= W:
            R[i][j] = 1
        elif S[i][j] == "." and j + 1 < W:
            R[i][j] = R[i][j+1] + 1

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)
    cnt = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        done = [0] * W
        for j in range(W):
            if G[i][j] == "#":
                continue
            if done[j]:
                continue
            length = 0
            while j + length < W:
                if G[i][j+length] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i][j + k] += length
                done[j + k] = 1

    for j in range(W):
        done = [0] * H
        for i in range(H):
            if G[i][j] == "#":
                continue
            if done[i]:
                continue
            length = 0
            while i + length < H:
                if G[i+length][j] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i + k][j] += length
                done[i + k] = 1
    ans = 0
    for i in range(H):
        ans = max(ans, max(cnt[i]) - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    INF = 10 ** 18 + 10

    def bfs(i, j):
        d = [[INF for k in range(W)] for l in range(H)]
        q = deque()
        q.append((i, j))
        d[i][j] = 0
        cnt = 1
        while q:
            a, b = q.popleft()
            for k in range(4):
                to_w = max(0, min(W - 1, b + dx[k]))
                to_h = max(0, min(H - 1, a + dy[k]))
                if G[to_h][to_w] == "#":
                    continue
                if d[to_h][to_w] != INF:
                    continue
                if to_w != j and to_h != i:
                    continue
                d[to_h][to_w] = d[a][b] + 1
                q.append((to_h, to_w))
                cnt += 1
        # print(i, j, cnt)
        return cnt

    res = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#":
                continue
            res = max(res, bfs(h, w))
    # bfs(2, 5)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
G = []
for i in range(H):
    s = list(input())
    G.append(s)
# print(G)


dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


INF = 10 ** 18 + 10


def bfs(i, j):
    d = [[INF for k in range(W)] for l in range(H)]
    q = deque()
    q.append((i, j))
    d[i][j] = 0
    cnt = 1
    while q:
        a, b = q.popleft()
        for k in range(4):
            to_w = max(0, min(W - 1, b + dx[k]))
            to_h = max(0, min(H - 1, a + dy[k]))
            if G[to_h][to_w] == "#":
                continue
            if d[to_h][to_w] != INF:
                continue
            if to_w != j and to_h != i:
                continue
            d[to_h][to_w] = d[a][b] + 1
            q.append((to_h, to_w))
            cnt += 1
    # print(i, j, cnt)
    return cnt


res = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            continue
        res = max(res, bfs(h, w))
# bfs(2, 5)
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for i in range(H):
    s = input()
    s = [int(s_.replace("#", "1").replace(".", "0")) for s_ in s]
    S.append(s)
"""
for j in range(H):
    print(S[j])
"""
MAX = 0
for h in range(H):
    for w in range(W):
        #print("座標", h, w, S[h][w])
        if S[h][w] == 1:
            continue
        
        lamp = 1
        
        ue = 1
        while h - ue >= 0:
            if S[h-ue][w] == 1:
                break
            ue += 1
            lamp += 1
            
        shita = 1
        while h + shita < H:
            if S[h+shita][w] == 1:
                break
            shita += 1
            lamp += 1
        
        hidari = 1
        while w - hidari >= 0:
            if S[h][w-hidari] == 1:
                break
            hidari += 1
            lamp += 1
            
        migi = 1
        while w + migi < W:
            if S[h][w+migi] == 1:
                break
            migi += 1
            lamp += 1
            
        #print(lamp, ue-1, shita-1, hidari-1, migi-1)
        
        MAX = max(MAX, lamp)

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = np.zeros((H, W), dtype='i8')
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light[h, wr:w] += count
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light[h, wr:w + 1] += count
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light[hr:h, w] += count
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light[hr:h + 1, w] += count
                hr = -1
                count = 0

    print(np.max(light) - 1)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

mtx = [input() for _ in range(h)]

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

# left 2 right
for i in range(h):
    for j in range(w):
        if mtx[i][j] == '.':
            ret_mtx[i][j][0] = 1 if i == 0 else ret_mtx[i-1][j][0] + 1
            ret_mtx[i][j][1] = 1 if j == 0 else ret_mtx[i][j-1][1] + 1
        if mtx[-1-i][-1-j] == '.':
            ret_mtx[-1-i][-1-j][2] = 1 if i == 0 else ret_mtx[-i][-1-j][2] + 1
            ret_mtx[-1-i][-1-j][3] = 1 if j == 0 else ret_mtx[-1-i][-j][3] + 1

ret = 0

for i in range(len(ret_mtx)):
    for j in range(len(ret_mtx[i])):
        tmp = sum(ret_mtx[i][j]) - 3
        ret = max(ret, tmp)

print(ret)

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    s = input()
    for j, ch in enumerate(s):
        mtx[i][j] = 1 if ch == '#' else 0

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

# left 2 right
for i in range(h):
    for j in range(w):
        if mtx[i][j] == 0:
            ret_mtx[i][j][0] = 1 if i == 0 else ret_mtx[i-1][j][0] + 1
            ret_mtx[i][j][1] = 1 if j == 0 else ret_mtx[i][j-1][1] + 1
        if mtx[-1-i][-1-j] == 0:
            ret_mtx[-1-i][-1-j][2] = 1 if i == 0 else ret_mtx[-i][-1-j][2] + 1
            ret_mtx[-1-i][-1-j][3] = 1 if j == 0 else ret_mtx[-1-i][-j][3] + 1

ret = 0

for i in range(len(ret_mtx)):
    for j in range(len(ret_mtx[i])):
        tmp = sum(ret_mtx[i][j]) - 3
        ret = max(ret, tmp)

print(ret)

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    s = input()
    for j, ch in enumerate(s):
        mtx[i][j] = 1 if ch == '#' else 0

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

# left 2 right
for i in range(h):
    for j in range(w):
        if mtx[i][j] == 1:
            continue
        else:
            ret_mtx[i][j][0] = 1 if i == 0 else ret_mtx[i-1][j][0] + 1
            ret_mtx[i][j][1] = 1 if j == 0 else ret_mtx[i][j-1][1] + 1


for i in range(h):
    for j in range(w):
        if mtx[-1-i][-1-j] == 1:
            continue
        else:
            ret_mtx[-1-i][-1-j][2] = 1 if i == 0 else ret_mtx[-i][-1-j][2] + 1
            ret_mtx[-1-i][-1-j][3] = 1 if j == 0 else ret_mtx[-1-i][-j][3] + 1

ret = 0

for i in range(len(ret_mtx)):
    for j in range(len(ret_mtx[i])):
        tmp = sum(ret_mtx[i][j]) - 3
        ret = max(ret, tmp)

print(ret)

Submission status: Time Limit Exceeded

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

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

for i in range(h):
    s = input()
    for j, ch in enumerate(s):
        mtx[i][j] = 1 if ch == '#' else 0

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

# left 2 right
for i in range(h):
    cur = 0
    for j, ch in enumerate(mtx[i]):
        if mtx[i][j] == 0:
            cur += 1
            ret_mtx[i][j][0] = cur
        else:
            cur = 0

for i in range(h):
    cur = 0
    for j in range(1, w+1):
        if mtx[i][-j] == 0:
            cur += 1
            ret_mtx[i][-j][1] = cur
        else:
            cur = 0

for j in range(w):
    cur = 0
    for i in range(h):
        if mtx[i][j] == 0:
            cur += 1
            ret_mtx[i][j][2] = cur
        else:
            cur = 0

for j in range(w):
    cur = 0
    for i in range(1, h+1):
        if mtx[-i][j] == 0:
            cur += 1
            ret_mtx[-i][j][3] = cur
        else:
            cur = 0

ret = 0

for i in range(len(ret_mtx)):
    for j in range(len(ret_mtx[i])):
        tmp = sum(ret_mtx[i][j]) - 3
        ret = max(ret, tmp)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  S = tuple(input().rstrip() 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 i in range(h):
    for j in range(w):
      if j > 0:
        if S[i][j-1] == ".":
          L[i][j] = L[i][j-1]+1
        if S[i][w-j] == ".":
          R[i][w-1-j] = R[i][w-j]+1
      if i > 0:
        if S[i-1][j] == ".":
          U[i][j] = U[i-1][j]+1
        if S[h-i][j] == ".":
          D[h-1-i][j] = D[h-i][j]+1
  ans = 0
  for i in range(h):
    for j in range(w):
      if S[i][j] == ".":
        temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
        ans = max(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  S = [input().rstrip() 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 i in range(h):
    for j in range(w):
      if j > 0:
        if S[i][j-1] == ".":
          L[i][j] = L[i][j-1]+1
        if S[i][w-j] == ".":
          R[i][w-1-j] = R[i][w-j]+1
      if i > 0:
        if S[i-1][j] == ".":
          U[i][j] = U[i-1][j]+1
        if S[h-i][j] == ".":
          D[h-1-i][j] = D[h-i][j]+1
  ans = 0
  for i in range(h):
    for j in range(w):
      if S[i][j] == ".":
        temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
        ans = max(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

dists = [[[0, 0] for j in range(W)] for i in range(H)]

tile = [0 for i in range(H)]

for i in range(H):
    tile[i] = readline().decode().strip()

for i in range(H):
    count = 0
    start = 0
    for j in range(W):
        if tile[i][j] == '#':
            for x in range(start, j):
                dists[i][x][0] = count
            count = 0
            start = j + 1
        else:
            count += 1 
    for x in range(start, W):
        dists[i][x][0] = count

for j in range(W):
    count = 0
    start = 0
    for i in range(H):
        if tile[i][j] == '#':
            for y in range(start, i):
                dists[y][j][1] = count
            count = 0
            start = i + 1
        else:
            count += 1 
    for y in range(start, H):
        dists[y][j][1] = count


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

dists = [[[0, 0] for j in range(W)] for i in range(H)]

tile = [0 for i in range(H)]

for i in range(H):
    tile[i] = readline().decode().strip()

for i in range(H):
    for j in range(W):
        c = tile[i][j]
        if c == '#':
            continue
        
        d = dists[i][j]
        if d[0] == 0:
            # search horizontally
            x = j
            count = 0
            while x < W and tile[i][x] != '#':
                x += 1
                count += 1
            for a in range(j, x):
                dists[i][a][0] = count
        if d[1] == 0:
            # search vertically
            y = i
            count = 0
            while y < H and tile[y][j] != '#':
                y += 1
                count += 1
            for b in range(i, y):
                dists[b][j][1] = count

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

Submission status: Time Limit Exceeded

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

for i in range(H):
    for j in range(W):
        now = 0
        if S[i][j] == ".":
            k = j
            while k < W and S[i][k] == ".":
                now += 1
                k += 1
            k = j - 1 
            while k >= 0 and S[i][k] == ".":
                now += 1
                k -= 1

            k = i + 1
            while k < H and S[k][j] == ".":
                now += 1
                k += 1
            k = i - 1
            while k >= 0 and S[k][j] == ".":
                now += 1
                k -= 1

            ans = max(ans, now)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

a,b = map(int,input().split())
L = [list(input()) for _ in range(a)]
L_tate = []
for i in range(b):
    temp = []
    for j in range(a):
        temp.append(L[j][i])
    L_tate.append(temp)



def yoko(i,j):
    yoko = L[i]
    ans = 0
    for k in range(j+1,b):
        if yoko[k] == ".":
            ans += 1
        elif yoko[k] == "#":
            break

    for k in range(j+1):
        if yoko[j-k] == ".":
            ans += 1
        elif yoko[j-k] == "#":
            break
    return ans

def tate(i,j):
    tate = L_tate[j]
    ans = 0
    for k in range(i+1,a):
        if tate[k] == ".":
            ans += 1
        elif tate[k] == "#":
            break

    for k in range(i+1):
        if tate[i-k] == ".":
            ans += 1
        elif tate[i-k] == "#":
            break
    return ans

ans = 0
for i in range(a):
    for j in range(b):
        ans = max(ans,yoko(i,j)+tate(i,j))
        

print(ans-1)