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())
S = [0] * H
for i in range(H):
    S[i] = input()

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

for i in range(H):
    for j in range(W):
        if yoko[i][j] != 0:
            continue
        elif S[i][j] == "#":
            yoko[i][j] = 0
        else:
            k = 0
            while S[i][j+k] == ".":
                k += 1
                if j+k == W:
                    break
            yoko[i][j:j+k] = [k] * k

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

for j in range(W):
    for i in range(H):
        if tate[i][j] != 0:
            continue
        elif S[i][j] == "#":
            tate[i][j] = 0
        else:
            k = 0
            while S[i+k][j] == ".":
                k += 1
                if i+k == H:
                    break
            for l in range(k):
                tate[i+l][j] = k

#for i in range(H):
#    print(tate[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [[-1] * w for _ in range(h)]
cnt = [0] * 2005
ans = 0
for i in range(h):
    x = 1
    cnt[1] = 0
    for j in range(w):
        if s[i][j] == ".":
            t[i][j] = x
            cnt[x] += 1
        else:
            x += 1
            cnt[x] = 0
    for j in range(w):
        if not t[i][j] == -1:
            t[i][j] = cnt[t[i][j]]
for j in range(w):
    x = 1
    cnt[1] = 0
    for i in range(h):
        if s[i][j] == ".":
            s[i][j] = x
            cnt[x] += 1
        else:
            x += 1
            cnt[x] = 0
    for i in range(h):
        if not s[i][j] == "#":
            ans = max(ans, t[i][j] + cnt[s[i][j]] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H, W = [int(x) for x in input().split()]
board = []
for _ in range(H):
    board.append(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 board[i][j] == '.':
            if 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 board[i][j] == '.':
            if 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 board[i][j] == '.':
            if 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 board[i][j] == '.':
            if i == H - 1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

input = sys.stdin.readline

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

    for w in range(W):
        cntU, cntD = 0, 0
        for h in range(H):
            hreverse = H - h - 1
            if grid[h][w] == '.':
                cntU += 1
            else:
                cntU = 0
            if grid[hreverse][w] == '.':
                cntD += 1
            else:
                cntD = 0
            U[h][w] = cntU
            D[hreverse][w] = cntD
    
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = 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(3000)
h,w = map(int,input().split())
l = [list(input()) for _ in range(h)]

ans = 0
tmp = 0
def dfs(i,j,direc):
    global tmp
    if 0<=i<h and 0<=j<w and l[i][j] == ".":
        tmp += 1
    else:
        return
    if direc == 1:
        dfs(i+1,j,direc)
    if direc == 2:
        dfs(i,j+1,direc)
    if direc == 3:
        dfs(i-1,j,direc)
    if direc == 4:
        dfs(i,j-1,direc)
        
ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            continue
        else:
            tmp = 1
            dfs(i+1,j,1)
            dfs(i,j+1,2)
            dfs(i-1,j,3)
            dfs(i,j-1,4)
            ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

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

graph = []
for i in range(H):
    graph.append(input())

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


for y in range(H):
    for x in range(W):
        if graph[y][x] == "#":
            L[y][x] = 0
        elif x == 0:
            L[y][x] = 1
        else:
            L[y][x] = L[y][x-1] + 1

for x in range(W):
    for y in range(H):
        if graph[y][x] == "#":
            U[y][x] = 0
        elif y == 0:
            U[y][x] = 1
        else:
            U[y][x] = U[y-1][x] + 1

for x in range(W):
    for y in range(H-1, -1, -1):
        if graph[y][x] == "#":
            D[y][x] = 0
        elif y == H-1:
            D[y][x] = 1
        else:
            D[y][x] = D[y+1][x] + 1

for y in range(H):
    for x in range(W-1, -1, -1):
        if graph[y][x] == "#":
            R[y][x] = 0
        elif x == W-1:
            R[y][x] = 1
        else:
            R[y][x] = R[y][x+1] + 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
s = []
rc = [[[None]*W for _ in range(H)] for _ in range(4)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            rc[0][j][i] = 0
        elif i > 0:
            rc[0][j][i] = rc[0][j][i-1] + 1
        else:
            rc[0][j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            rc[1][j][i] = 0
        elif i < W-1:
            rc[1][j][i] = rc[1][j][i+1] + 1
        else:
            rc[1][j][i] = 1
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            rc[2][j][i] = 0
        elif j > 0:
            rc[2][j][i] = rc[2][j-1][i] + 1
        else:
            rc[2][j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            rc[3][j][i] = 0
        elif j < H-1:
            rc[3][j][i] = rc[3][j+1][i] + 1
        else:
            rc[3][j][i] = 1
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(rc[0][j][i]+rc[1][j][i]+rc[2][j][i]+rc[3][j][i]-3, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
s = []
rc = [[[None]*W for _ in range(H)] for _ in range(2)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            rc[0][j][i] = 0
        elif i > 0:
            rc[0][j][i] = rc[0][j][i-1] + 1
        else:
            rc[0][j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            continue
        elif i < W-1:
            rc[0][j][i] = max(rc[0][j][i+1], rc[0][j][i])
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            rc[1][j][i] = 0
        elif j > 0:
            rc[1][j][i] = rc[1][j-1][i] + 1
        else:
            rc[1][j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            continue
        elif j < H-1:
            rc[1][j][i] = max(rc[1][j+1][i], rc[1][j][i])
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(rc[0][j][i] + rc[1][j][i] - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
s = []
row = [[None]*W for _ in range(H)]
col = [[None]*W for _ in range(H)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            row[j][i] = 0
        elif i > 0:
            row[j][i] = row[j][i-1] + 1
        else:
            row[j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            continue
        elif i < W-1:
            row[j][i] = max(row[j][i+1], row[j][i])
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            col[j][i] = 0
        elif j > 0:
            col[j][i] = col[j-1][i] + 1
        else:
            col[j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            continue
        elif j < H-1:
            col[j][i] = max(col[j+1][i], col[j][i])
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(row[j][i] + col[j][i] - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

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

dist=[[-1]*W for _ in range(H)]
distT =[[-1]*H for _ in range(W)]
white_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            dist[h][w] = 0
            distT[w][h] = 0
        else:
            white_cells.append((h,w))
for S in dist:
    cnt = 0
    Ran = [0,1]
    for w in range(W):
        Sw = S[w]
        if Sw == 0:
            S[Ran[0]:Ran[1]-1] = [cnt]*(Ran[1]-Ran[0]-1)
            cnt = 0
            Ran[0] = Ran[1]
            Ran[1] = Ran[1] + 1
        elif Sw == -1:
            if w != W-1:
                cnt += 1
                Ran[1] +=1
            else:
                cnt +=1
                S[Ran[0]:Ran[1]] = [cnt]*(Ran[1]-Ran[0])

for Sin in distT:
    cnt = 0
    Ran = [0,1]
    for h in range(H):
        Sinh = Sin[h]
        if Sinh == 0:
            Sin[Ran[0]:Ran[1]-1] = [cnt]*(Ran[1]-Ran[0]-1)
            cnt = 0
            Ran[0] = Ran[1]
            Ran[1] = Ran[1] + 1
        elif Sinh == -1:
            if h != H-1:
                cnt += 1
                Ran[1] +=1
            else:
                cnt +=1
                Sin[Ran[0]:Ran[1]] = [cnt]*(Ran[1]-Ran[0])

Ans = 0
for _ in range(len(white_cells)):
    h,w = white_cells.pop()
    Ans = max(Ans,(dist[h][w]+distT[w][h])-1)
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
u_light = [[0]*w for _ in range(h)] #上をてらせる数
d_light = [[0]*w for _ in range(h)] #下
l_light = [[0]*w for _ in range(h)] #左
r_light = [[0]*w for _ in range(h)] #右

def count_light(i, j):
    if s[i][j] == '.':
        return 1
    else:
        return -10000

for i in range(w):
    d_light[-1][i] = count_light(-1, i)
    u_light[0][i] = count_light(0, i)
for j in range(1, h):
    for i in range(w):
        d_light[-(j+1)][i] = max(d_light[-j][i], 0) + count_light(-(j+1), i)
        u_light[j][i] = max(u_light[j-1][i], 0) + count_light(j, i)

for i in range(h):
    l_light[i][0] = count_light(i, 0)
    r_light[i][-1] = count_light(i, -1)
for j in range(1, w):
    for i in range(h):
        l_light[i][j] = max(l_light[i][j-1], 0) + count_light(i, j)
        r_light[i][-(j+1)] = max(r_light[i][-j], 0) + count_light(i, -(j+1))

score = 0
tmp_score = 0
for i in range(h):
    for j in range(w):
        tmp_score = u_light[i][j] + d_light[i][j] + l_light[i][j] + r_light[i][j]
        if tmp_score > score:
            score = tmp_score
print(score-3) # 3回ダブっているので除去

Submission status: Time Limit Exceeded

Solution code:
h,w = list(map(int, input().split()))
b = [input() + '#' for _ in range(h)]
b.append('#' * (w + 1))
ans = [[0]*w for _ in range(h)]

for r in range(h):
    c = 0
    while c < w:
        if b[r][c] == '#':
            c += 1
        else:
            st = c
            while b[r][c] == '.':
                c += 1
            for i in range(st, c):
                ans[r][i] += (c - st)

for c in range(w):
    r = 0
    while r < h:
        if b[r][c] == '#':
            r += 1
        else:
            st = r
            while b[r][c] == '.':
                r += 1
            for i in range(st, r):
                ans[i][c] += (r - st)

import itertools
print(max(itertools.chain.from_iterable(ans))-1)

Submission status: Time Limit Exceeded

Solution code:
r, c = map(int, input().split())
ans = 0

map = []
for i in range(r):
    map.append(input())

L = [[0]*c for i in range(r)]
R = [[0]*c for i in range(r)]
D = [[0]*c for i in range(r)]
U = [[0]*c for i in range(r)]

for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            L[i][j] = L[i][j - 1] + 1
        else:
            L[i][j] = 0
for i in range(r):
    for j in range(c - 1, -1, -1):
        if j == c - 1:
            if map[i][j] == ".":
                R[i][j] = 1
            continue
        if map[i][j] == ".":
            R[i][j] = R[i][j + 1] + 1
        else:
            R[i][j] = 0
for i in range(r):
    for j in range(c):
        if map[i][j] == ".":
            D[i][j] = D[i - 1][j] + 1
        else:
            D[i][j] = 0
for i in range(r - 1, -1, -1):
    for j in range(c):
        if i == r - 1:
            if map[i][j] == ".":
                U[i][j] = 1
            continue
        if map[i][j] == ".":
            U[i][j] = U[i + 1][j] + 1
        else:
            U[i][j] = 0

for i in range(r):
    for j in range(c):
        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
h, w = [int(x) for x in input().split()]
mat = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]
row_obs = [[-1] for _ in range(h)]
col_obs = [[-1] for _ in range(w)]

def main():
    for i, r in enumerate(mat):
        for j, c in enumerate(r):
            if c == '#':
                row_obs[i].append(j)
                col_obs[j].append(i)
        row_obs[i].append(w)
    for j in range(w):
        col_obs[j].append(h)

    for i in range(h):
        k = 0
        while True:
            prev, nxt = (row_obs[i][k], row_obs[i][k+1])
            for j in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == w:
                break
            k += 1

    for j in range(w):
        k = 0
        while True:
            prev, nxt = (col_obs[j][k], col_obs[j][k+1])
            for i in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == h:
                break
            k += 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, cnt[i][j] - 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
h, w = [int(x) for x in input().split()]
mat = [input() for _ in range(h)]
lr = [[None] * w for _ in range(h)]
ab = [[None] * w for _ in range(h)]
row_obs = [[] for _ in range(h)]
col_obs = [[] for _ in range(w)]

def main():
    global mat, h, w
    for i, l in enumerate(mat):
        for j, c in enumerate(l):
            if c == '#':
                row_obs[i].append(j)
                col_obs[j].append(i)
    for b in range(2):
        if b == 0:
            obs = row_obs
        else:
            obs = col_obs
            mat = list(zip(*mat))
            h, w = w, h
        for i in range(h):
            k = 0
            prev = -1
            nxt = obs[i][k] if len(obs[i]) > 0 else w
            for j in range(w):
                if mat[i][j] == '#':
                    prev = obs[i][k]
                    nxt = obs[i][k+1] if k+1 < len(obs[i]) else w
                    k += 1
                else:
                    if b == 0:
                        lr[i][j] = (prev, nxt)
                    else:
                        ab[j][i] = (prev, nxt)
    ans = 0
    h, w = w, h
    mat = list(zip(*mat))
    for i in range(h):
        for j in range(w):
            if mat[i][j] != '#':
                l, r = lr[i][j]
                a, b = ab[i][j]
                ans = max(ans, r - l - 1 + b - a - 1 - 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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


    m = -math.inf

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

    print(m)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
maze = [input() for i in range(H)]

dp_row = [[-1] * W for i in range(H)]
dp_col = [[-1] * W for i in range(H)]

# 横
def dfs_row(y, x):
    if dp_row[y][x] >= 0:
        return dp_row[y][x]

    if maze[y][x] == '#':
        return 0

    res = 1
    nx = x + 1
    if 0 <= nx < W and maze[y][nx] == '.':
        res += dfs_row(y, nx)
    dp_row[y][x] = res
    return res

for i in range(H):
    for j in range(W):
        dfs_row(i, j)
    cnt = 0
    for j in range(1, W):
        if dp_row[i][j] >= 0 and dp_row[i][j - 1] >= 0:
            dp_row[i][j] = dp_row[i][j - 1]

# 縦
def dfs_col(y, x):
    if dp_col[y][x] >= 0:
        return dp_col[y][x]

    if maze[y][x] == '#':
        return 0

    res = 1
    ny = y + 1
    if 0 <= ny < H and maze[ny][x] == '.':
        res += dfs_col(ny, x)
    dp_col[y][x] = res
    return res

for i in range(H):
    for j in range(W):
        dfs_col(i, j)

for i in range(1, H):
    for j in range(W):
        if dp_col[i][j] >= 0 and dp_col[i - 1][j] >= 0:
            dp_col[i][j] = dp_col[i - 1][j]
# 集計
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            ans = max(ans, dp_row[i][j] + dp_col[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
tizu = [input() for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
ans = [[1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if check[i][j]:
            continue
        if tizu[i][j] == "#":
            continue
        pos = [i]
        cnt = 0
        for k in range(i + 1, h):
            if tizu[k][j] == "#":
                break
            pos.append(k)
            cnt += 1
        for k in range(i - 1, -1, -1):
            if tizu[k][j] == "#":
                break
            pos.append(k)
            cnt += 1
        for l in pos:
            ans[l][j] += cnt
            check[l][j] = True

check = [[False for _ in range(w)] for _ in range(h)]
max_ans = 0
for i in range(h):
    for j in range(w):
        if check[i][j]:
            continue
        if tizu[i][j] == "#":
            continue
        pos = [j]
        cnt = 0
        for k in range(j + 1, w):
            if tizu[i][k] == "#":
                break
            pos.append(k)
            cnt += 1
        for k in range(j - 1, -1, -1):
            if tizu[i][k] == "#":
                break
            pos.append(k)
            cnt += 1
        for l in pos:
            ans[i][l] += cnt
            check[i][l] = True
            max_ans = max(max_ans, ans[i][l])
print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
s = [list(input().strip()) 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):
  c1 = 0
  c2 = 0
  for j in range(w):
    if s[i][j] == "#":
      c1 = 0
    else:
      c1 += 1
      l[i][j] = c1
    if s[i][w-j-1] == "#":
      c2 = 0
    else:
      c2 += 1
      r[i][w-j-1] = c2
for j in range(w):
  c1 = 0
  c2 = 0
  for i in range(h):
    if s[i][j] == "#":
      c1 = 0
    else:
      c1 += 1
      u[i][j] = c1
    if s[h-i-1][j] == "#":
      c2 = 0
    else:
      c2 += 1
      d[h-i-1][j] = c2
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:
H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_r=[[0]*W for i in range(H)]
l_l=[[0]*W for i in range(H)]
l_u=[[0]*W for i in range(H)]
l_d=[[0]*W for i in range(H)]
for i in range(H):
   tmp=0
   for j in range(W):
      if l[i][j] == ".":
         tmp+=1
         l_r[i][j]=tmp
      else:
         tmp=0
for i in range(H):
   tmp=0
   tmp_l=l[i]
   tmp_l=tmp_l[::-1]
   for j in range(W):
      if tmp_l[j] == ".":
         tmp+=1
         l_l[i][j]=tmp
      else:
         tmp=0
   l_l[i].reverse()
for i in range(W):
   tmp=0
   for j in range(H):
      if l[j][i]==".":
         tmp+=1
         l_d[j][i]=tmp
      else:
         tmp=0
for i in range(W):
   tmp=0
   for j in reversed(range(H)):
      if l[j][i]==".":
         tmp+=1
         l_u[j][i]=tmp
      else:
         tmp=0
ans=0
for i in range(H):
   for j in range(W):
      ans=max(ans,l_u[i][j]+l_d[i][j]+l_l[i][j]+l_r[i][j]-3)
print(ans)

Submission status: Time Limit Exceeded

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

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

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


for i in reversed(range(h)):
    for j in reversed(range(w)):
        if s[i][j] == "#":
            D[i][j] = 0
            R[i][j] = 0
        else:
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i + 1][j] + 1
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j + 1] + 1

ans = 0
for i in range(h):
    for j in range(w):
        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:
import sys
input = sys.stdin.readline

h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    si=input()
    s[i]=si
"""
h,w=4,6
s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    
"""
ww=[[0]*w for i in range(h)]
#www=[[0]*w for i in range(h)]
www=[0]*w
for i in range(h):
    jsum=0
    jcnt=1
    jj=[0]*(w+1)
    for j in range(w):
        if s[i][j]==".":
#            www[i][j]=jcnt
            www[j]=jcnt
            if j<w-1 and s[i][j+1]=="#":
                jcnt+=1
            jsum+=1
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                jj[jcnt-1]=jsum
            jsum=0
    jcnt+=1
    jj[jcnt-1]=jsum
            
    for j in range(w):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            ww[i][j]=jj[www[j]]
#    print(jj)
                
hh=[[0]*w for i in range(h)]
hhh=[0]*h
for j in range(w):
    isum=0
    icnt=1
    ii=[0]*(h+1)
    for i in range(h):
        if s[i][j]==".":
#            www[i][j]=jcnt
            hhh[i]=icnt
            if i<h-1 and s[i+1][j]=="#":
                icnt+=1
            isum+=1
        else:
#            print(jsum,jst,jed)
            if isum!=0:
                ii[icnt-1]=isum
            isum=0
    icnt+=1
    ii[icnt-1]=isum
            
    for i in range(h):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            hh[i][j]=ii[hhh[i]]
#    print(jj)
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Time Limit Exceeded

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


h,w=map(int,input().split())
#s=[[]*w for i in range(h)]
#s=[]*h
s=[[] for i in range(h)]
for i in range(h):
#    s[i]=list(input())
    si=input()
#    s[i].append(si)
    s[i]=si
"""
h,w=4,6
s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    
"""
ww=[[0]*w for i in range(h)]
for i in range(h):
    jsum=0
    jst=0
    jed=0
    for j in range(w):
        if s[i][j]==".":
            jsum+=1
            jst=min(j,jst)
            jed=max(j,jed)
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                for jj in range(jst,jed+1):
                    ww[i][jj]=jsum
            jsum=0
            jst=j+1
            jed=j+1
        if jst<w:
            for jj in range(jst,jed+1):
                ww[i][jj]=jsum
                
hh=[[0]*w for i in range(h)]
for j in range(w):
    isum=0
    ist=0
    ied=0
    for i in range(h):
        if s[i][j]==".":
            isum+=1
            ist=min(i,ist)
            ied=max(i,ied)
        else:
#            print(isum,ist,ied)
            if isum!=0:
                for ii in range(ist,ied+1):
                    hh[ii][j]=isum
            isum=0
            ist=i+1
            ied=i+1
        if ist<h:
            for ii in range(ist,ied+1):
                hh[ii][j]=isum
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)