Problem:


Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

S_i is a string of length W consisting of # and ..

. occurs at least once in one of the strings S_i (1 \leq i \leq H).

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the maximum possible number of squares lighted by the lamp.

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
from itertools import chain

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

def neighbours(n):
    return sum(n)

nodes = []
lastUp = [0] * w
lastLeft = 0
for i in range(h):
    lastLeft = 0
    nodes.append([])
    for j,c in enumerate(input()):
        good = 1 if c == '.' else 0
        left = 0
        up = 0
        right = w - j - 1
        down = h - i - 1
        if good == 1:
            if j > 0:
                l = nodes[i][j - 1]
                left = l[1] + l[0]
            if i > 0:
                u = nodes[i - 1][j]
                up = u[2] + u[0]
        else:
            right = 0
            down = 0
            for k in range(lastLeft, j):
                nodes[i][k][3] = j - k - 1
            for k in range(lastUp[j], i):
                nodes[k][j][4] = i - k - 1
            lastLeft = j + 1
            lastUp[j] = i + 1
        nodes[i].append([good, left, up, right, down])

print(max(map(lambda x: neighbours(x), chain(*nodes))))

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
from itertools import chain

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

class Node():
    __slots__ = ['good', 'left', 'up', 'right', 'down']
    def __init__(self, good, left, up, right, down):
        self.good = good
        self.left = left
        self.up = up
        self.right = right
        self.down = down
    def neighbours(self):
        return self.left + self.up + self.right + self.down + int(self.good)
    def __repr__(self):
        return "{} {} {} {} {}".format(self.good, self.left, self.up, self.right, self.down)

nodes = [ [ None for _ in range(w) ] for _ in range(h) ]
lastUp = [0 for _ in range(w)]
lastLeft = 0
steps = 0
for i in range(h):
    lastLeft = 0
    for j,c in enumerate(input()):
        n = Node(c == '.', 0, 0, w - j - 1, h - i - 1)
        steps += 1
        if n.good:

            if j > 0:
                l = nodes[i][j - 1]
                n.left = l.left + int(l.good)
            if i > 0:
                u = nodes[i - 1][j]
                n.up = u.up + int(u.good)
        else:
            n.right = 0
            n.down = 0
            for k in range(lastLeft, j):
                nodes[i][k].right = j - k - 1
                steps += 1
            for k in range(lastUp[j], i):
                nodes[k][j].down = i - k - 1
                steps += 1
            lastLeft = (j + 1) % w
            lastUp[j] = i + 1
        nodes[i][j] = n

print(max(map(lambda x: x.neighbours(), chain(*nodes))))

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple

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

class Node():
    __slots__ = ['good', 'left', 'up', 'right', 'down']
    def __init__(self, good, left, up, right, down):
        self.good = good
        self.left = left
        self.up = up
        self.right = right
        self.down = down
    def neighbours(self):
        return self.left + self.up + self.right + self.down + 1

nodes = {}
downStreak = [0 for i in range(w)]
for i in range(h):
    s = input()
    rightStreak = 0
    for j,c in enumerate(s):
        n = Node(c == '.', 0, 0, 0, 0)
        if n.good:
            rightStreak += 1
            downStreak[j] += 1

            if j > 0:
                l = nodes[(i, j - 1)]
                n.left = l.left + int(l.good)
                if l.good:
                    for k in reversed(range(j - rightStreak + 1, j)):
                        nodes[(i, k)].right += 1
            if i > 0:
                u = nodes[(i - 1, j)]
                n.up = u.up + int(u.good)
                if u.good:
                    for k in reversed(range(i - downStreak[j] + 1, i)):
                        nodes[(k, j)].down += 1
        else:
            rightStreak = 0
            downStreak[j] = 0
        nodes[(i, j)] = n

# print('\n'.join(map(str, nodes.items())))
print(max(map(lambda x: x.neighbours(), nodes.values())))

Submission status: Time Limit Exceeded

Solution code:
def il(l,x,y):
    if l[y][x]=="#":return 0
    re=1
    for i in range(x):
        if l[y][x-1-i]==".":re+=1
        else:break
    for j in range(w-x-1):
        if l[y][x+1+j]==".":re+=1
        else:break
    for k in range(y):
        if l[y-1-k][x]==".":re+=1
        else:break
    for m in range(h-y-1):
        if l[y+1+m][x]==".":re+=1
        else:break
    return re
h,w=map(int,input().split())
l=[input() for _ in range(h)]
ans=0
for i in range(w):
    for j in range(h):
        ans=max(ans,il(l,i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,*s=open(0)
h,w=map(int,h.split())
r=range
a,b,c,d=[[[0]*w for _ in r(h)]for i in r(4)]
for i in r(h*w):
    i,j=i//w,i%w
    a[i][j]=-~a[i][j-1]*(s[i][j]=='.')
    b[i][~j]=-~b[i][-j]*(s[i][-j-2]=='.')
    c[i][j]=-~c[i-1][j]*(s[i][j]=='.')
    d[~i][j]=-~d[-i][j]*(s[~i][j]=='.')
print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in r(h)for j in r(w)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    S = [input() for _ 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)]
    L = [[0 for i in range(W)] for j in range(H)]
    R = [[0 for i in range(W)] for j in range(H)]

    for i in range(H):
        for j in range(W):
            # 上方向
            if i > 0:
                if S[i - 1][j] == '#':
                    U[i][j] = 0
                else:
                    U[i][j] = U[i - 1][j] + 1
            
            # 左方向
            
            if j > 0:
                if S[i][j - 1] == '#':
                    L[i][j] = 0
                else:
                    L[i][j] = L[i][j - 1] + 1
    
    for i in range(H - 1, -1, -1):
        for j in range(W - 1, -1, -1):
            # 下方向
            if i < H - 1:
                if S[i + 1][j] == '#':
                    D[i][j] = 0
                else:
                    D[i][j] = D[i + 1][j] + 1
            
            # 右方向
            if j < W - 1:
                if S[i][j + 1] == '#':
                    R[i][j] = 0
                else:
                    R[i][j] = R[i][j + 1] + 1
                
            

    res = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != '#':
                res = max(res, U[i][j] + D[i][j] + R[i][j] + L[i][j])
    
    print(res + 1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())
    S = [input() for _ 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)]
    L = [[0 for i in range(W)] for j in range(H)]
    R = [[0 for i in range(W)] for j in range(H)]

    for i in range(H):
        for j in range(W):
            # 上方向
            if i > 0:
                if S[i - 1][j] == '#':
                    U[i][j] = 0
                else:
                    U[i][j] = U[i - 1][j] + 1
            # 下方向
            if i < H - 1:
                if i == 0:
                    d = 0
                    for h in range(i+1, H):
                        if S[h][j] == '.':
                            d += 1
                        else:
                            break
                    D[i][j] = d
                else:
                    if D[i - 1][j] > 0:
                        D[i][j] = D[i - 1][j] - 1
                    else:
                        d = 0
                        for h in range(i+1, H):
                            if S[h][j] == '.':
                                d += 1
                            else:
                                break
                        D[i][j] = d
            
            # 左方向
            if j > 0:
                if S[i][j - 1] == '#':
                    L[i][j] = 0
                else:
                    L[i][j] = L[i][j - 1] + 1
            
            # 右方向
            if j < W - 1:
                if j == 0:
                    r = 0
                    for w in range(j+1, W):
                        if S[i][w] == '.':
                            r += 1
                        else:
                            break
                    R[i][j] = r
                else:
                    if R[i][j - 1] > 0:
                        R[i][j] = R[i][j - 1] - 1
                    else:
                        r = 0
                        for w in range(j + 1, W):
                            if S[i][w] == '.':
                                r += 1
                            else:
                                break
                        R[i][j] = r

    res = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != '#':
                res = max(res, U[i][j] + D[i][j] + R[i][j] + L[i][j])

    print(res + 1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for _ 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)]
L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        # 上方向
        if i > 0:
            if S[i - 1][j] == '#':
                U[i][j] = 0
            else:
                U[i][j] = U[i - 1][j] + 1
        # 下方向
        if i < H - 1:
            if i == 0:
                d = 0
                for h in range(i+1, H):
                    if S[h][j] == '.':
                        d += 1
                    else:
                        break
                D[i][j] = d
            else:
                if D[i - 1][j] > 0:
                    D[i][j] = D[i - 1][j] - 1
                else:
                    d = 0
                    for h in range(i+1, H):
                        if S[h][j] == '.':
                            d += 1
                        else:
                            break
                    D[i][j] = d
        
        # 左方向
        if j > 0:
            if S[i][j - 1] == '#':
                L[i][j] = 0
            else:
                L[i][j] = L[i][j - 1] + 1
        
        # 右方向
        if j < W - 1:
            if j == 0:
                r = 0
                for w in range(j+1, W):
                    if S[i][w] == '.':
                        r += 1
                    else:
                        break
                R[i][j] = r
            else:
                if R[i][j - 1] > 0:
                    R[i][j] = R[i][j - 1] - 1
                else:
                    r = 0
                    for w in range(j + 1, W):
                        if S[i][w] == '.':
                            r += 1
                        else:
                            break
                    R[i][j] = r

res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            res = max(res, U[i][j] + D[i][j] + R[i][j] + L[i][j])

print(res + 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w = map(int,input().split())
s_list = [list(input()) for i in range(h)]
s_list_t = np.array(s_list).T

def enlight(s,x):
    count = 0
    i = 1
    try:
        while x+i <= w-1 and s[x+i] != '#':
            count += 1
            i += 1
    except IndexError:
        pass
    j = 1
    try:
        while x-j >= 0 and s[x-j] != '#' :
            count += 1
            j += 1
    except IndexError:
        pass
    return count

reply = 0
for i in range(w):
    for j in range(h):
        if s_list[j][i] != '#':
            reply = max(reply,enlight(s_list[j],i) + enlight(s_list_t[i],j) + 1)

print(reply)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

#B
def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return

#C
def C():
    n,m = LI()
    f = [1 for i in range(n+1)]
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)
    vi = [[0 for j in range(w)] for i in range(h)]
    ho = [[0 for j in range(w)] for i in range(h)]
    q = deque()
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                l = len(q)
                while q:
                    i,j = q.pop()
                    vi[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            vi[i][j] = l
    for x in range(w):
        for y in range(h):
            if s[y][x] == "#":
                l = len(q)
                while q:
                    i,j = q.pop()
                    ho[i][j] = l
            else:
                q.append((y,x))
        l = len(q)
        while q:
            i,j = q.pop()
            ho[i][j] = l
    ans = 0
    for y in range(h):
        for x in range(w):
            ans = max(ans,vi[y][x]+ho[y][x]-1)
    print(ans)
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

h, w = map(int, input().split())
map_arr1d = np.array([0 if s == '#' else 1 for _ in range(h) for s in input()[:-1]])
map_2d = map_arr1d.reshape(h, w)

h_map = []
for h_arr in map_2d:
    cnt = 0
    tmp_list = []
    for a in h_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    h_map.extend(tmp_list)
h_map = np.array(h_map).reshape(h, w)

w_map = []
for w_arr in map_2d.T:
    cnt = 0
    tmp_list = []
    for a in w_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    w_map.extend(tmp_list)
w_map = np.array(w_map).reshape(w, h).T
print((h_map + w_map).max()-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

h, w = map(int, input().split())
map_arr1d = np.array([0 if s == '#' else 1 for _ in range(h) for s in input()[:-1]])
map_2d = map_arr1d.reshape(h, w)

h_map = []
for h_arr in map_2d:
    cnt = 0
    tmp_list = []
    for a in h_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    h_map.extend(tmp_list)
h_map = np.array(h_map).reshape(h, w)

w_map = []
for w_arr in map_2d.T:
    cnt = 0
    tmp_list = []
    for a in w_arr:
        if a == 0:
            if cnt > 0:
                tmp_list.extend([cnt]*cnt)
                cnt = 0
            tmp_list.append(0)
        else:
            cnt += 1
    if cnt > 0:
        tmp_list.extend([cnt]*cnt)
    w_map.extend(tmp_list)
w_map = np.array(w_map).reshape(w, h).T
print(max((h_map + w_map).flatten())-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import takewhile

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

# 各マスについて、横方向に照らすマスの数と縦方向に照らすマスの数を求める
x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if x[i][j] == 0:
            w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
            for k in range(j, j + w):
                x[i][k] = w
        if y[i][j] == 0:
            h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
            for l in range(i, i + h):
                y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import takewhile

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

# 各マスについて、横方向に照らすマスの数と縦方向に照らすマスの数を求める
x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if x[i][j] == 0:
            c = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
            for k in range(j, j + c):
                if S[i][k] == '.':
                    x[i][k] = c
        if y[i][j] == 0:
            c = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
            for k in range(i, i + c):
                if S[k][j] == '.':
                    y[k][j] = c
ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import takewhile

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

# 各マスについて、横方向に照らすマスの数と縦方向に照らすマスの数を求める
x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if x[i][j] == 0:
            c = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
            for k in range(j, j + c):
                if S[i][k] == '.':
                    x[i][k] = c
for i in range(H):
    for j in range(W):
        if y[i][j] == 0:
            c = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
            for k in range(i, i + c):
                if S[k][j] == '.':
                    y[k][j] = c
ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)
def dmatprint(mat):

    if debug == True:
        for row in mat:
            for col in row:
                print("{0:2d} ".format(col), end="")
            print("")
        print("")

def solve():
    H, W = map(int, input().split())
    s_arr = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        s_row = input()
        for w in range(W):
            if s_row[w] == ".":
                s_arr[h][w] = 0
            else:
                s_arr[h][w] = 1

    # 上下左右の配列
    r_arr = [[0 for w in range(W)] for h in range(H)]
    l_arr = [[0 for w in range(W)] for h in range(H)]
    u_arr = [[0 for w in range(W)] for h in range(H)]
    d_arr = [[0 for w in range(W)] for h in range(H)]

    # 左から
    for h in range(H):
        for w in range(W):
            if s_arr[h][w] == 1:
                continue
            else:
                if w == 0:
                    val = 1
                else:
                    val = l_arr[h][w-1] + 1
            l_arr[h][w] = val

    # 上から
    for w in range(W):
        for h in range(H):
            if s_arr[h][w] == 1:
                continue
            else:
                if h == 0:
                    val = 1
                else:
                    val = u_arr[h-1][w] + 1
            u_arr[h][w] = val

    # 右から
    for h in range(H):
        for w in reversed(range(W)):
            if s_arr[h][w] == 1:
                continue
            else:
                if w == W-1:
                    val = 1
                else:
                    val = r_arr[h][w+1] + 1
            r_arr[h][w] = val

    # 下から
    for w in range(W):
        for h in reversed(range(H)):
            if s_arr[h][w] == 1:
                continue
            else:
                if h == H-1:
                    val = 1
                else:
                    val = d_arr[h + 1][w] + 1
            d_arr[h][w] = val

    mx_ans = 0
    for h in range(H):
        for w in range(W):
            ans = l_arr[h][w] + r_arr[h][w] + u_arr[h][w] + d_arr[h][w] - 3
            if ans >= mx_ans:
                mx_ans = ans

    print(mx_ans)
    dmatprint(s_arr)
solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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 = np.zeros((h+2,w+2,2),dtype=int)
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:
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)]
u = [[0 for i in range(w)] for j in range(h)]
r = [[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(h):
    for j in range(w):
        if s[i][j] == '#':
            l[i][j] = 0
            u[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

        if s[h-i-1][w-j-1] == '#':
            r[h-i-1][w-j-1] = 0
            d[h-i-1][w-j-1] = 0
        else:
            if i==0:d[h-i-1][w-j-1] = 1
            else:d[h-i-1][w-j-1] = d[h-i+1-1][w-j-1] + 1
            if j==0:r[h-i-1][w-j-1] = 1
            else:r[h-i-1][w-j-1] = r[h-i-1][w-j+1-1] + 1
        

sum = -1
for i in range(h):
    for j in range(w):
        sum = max(l[i][j] + u[i][j] + r[i][j] + d[i][j], sum)

print(sum-3)

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)]
u = [[0 for i in range(w)] for j in range(h)]
r = [[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(h):
    for j in range(w):
        if s[i][j] == '#':
            l[i][j] = 0
            u[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 range(h):
    for j in range(w):
        if s[h-i-1][w-j-1] == '#':
            r[h-i-1][w-j-1] = 0
            d[h-i-1][w-j-1] = 0
        else:
            if i==0:d[h-i-1][w-j-1] = 1
            else:d[h-i-1][w-j-1] = d[h-i+1-1][w-j-1] + 1
            if j==0:r[h-i-1][w-j-1] = 1
            else:r[h-i-1][w-j-1] = r[h-i-1][w-j+1-1] + 1

sum = -1
for i in range(h):
    for j in range(w):
        sum = max(l[i][j] + u[i][j] + r[i][j] + d[i][j], sum)

print(sum-3)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
MAP = [list(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):
    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

        if MAP[i][W - j - 1] == "#":
            R[i][W - j - 1] = 0
        elif j == 0:
            R[i][W - j - 1] = 1
        else:
            R[i][W - j - 1] = R[i][W - j] + 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

        if MAP[H - i - 1][j] == "#":
            D[H - i - 1][j] = 0
        elif i == 0:
            D[H - i - 1][j] = 1
        else:
            D[H - i - 1][j] = D[H - i][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:
import numpy as np

h, w = map(int, input().split())
s = []
for i in range(h):
    line = list(input())
    s.append(line)
table = np.ones([h,w])
for i in range(h):
 
    tuzuki = False
    count = 0
    for j in range(w):
        if s[i][j] == '.':
 
            if tuzuki:
                count += 1
            else:
                start = j
                count = 1
                tuzuki = True
            if j == w-1:
              table[i][start:w] = count

        else:
            if tuzuki:
                tuzuki = False
                table[i][start:j] = count
for j in range(w):
    tuzuki = False
    count = 0
    for i in range(h):
        if s[i][j] == '.':
            if tuzuki:
                count += 1
            else:
                start = i
                count = 1
                tuzuki = True
            if i == h-1:
              table[start:h, j] += count - 1
        else:
            if tuzuki:
              table[start:i, j] += count - 1
              tuzuki = False
print(int(table.max()))

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

        if MAP[i][W - j - 1] == "#":
            R[i][W - j - 1] = 0
        elif j == 0:
            R[i][W - j - 1] = 1
        else:
            R[i][W - j - 1] = R[i][W - j] + 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

        if MAP[H - i - 1][j] == "#":
            D[H - i - 1][j] = 0
        elif i == 0:
            D[H - i - 1][j] = 1
        else:
            D[H - i - 1][j] = D[H - i][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())

P = [ [ 0 if x == "#" else 0x00010001 for x in input()] for _ in range(H)]

class Union:
    def __init__(self):
        self.rx = 0
        self.ry = 0
        self.lx = 0
        self.ly = 0
    def init(self, y, x):
        value = P[y][x]
        if value == 0:
            return False

        self.lx = x
        self.ly = y
        w = value & 0xffff
        if w & 0x8000:
            self.ry = w ^ 0x8000
        else:
            self.ry = self.ly

        w = value >> 16
        if w & 0x8000:
            self.rx = w ^ 0x8000
        else:
            self.rx = self.lx

        return True

    def changeH(self, src, value):
        return (src ^ (src & 0xffff0000)) | (value << 16)
    def changeV(self, src, value):
        return (src ^ (src & 0xffff)) | value

    def changeHA(self, value):
        return self.changeH(value, self.rx | 0x8000)
    def changeVA(self, value):
        return self.changeV(value, self.ry | 0x8000)

    def getHC(self):
        return P[self.ly][self.rx] >> 16
    def setHC(self, value):
        P[self.ly][self.rx] = self.changeH(P[self.ly][self.rx], value)
    def getVC(self):
        return P[self.ry][self.lx] & 0xffff
    def setVC(self, value):
        P[self.ry][self.lx] = self.changeV(P[self.ry][self.lx], value)
        
uni = Union()

for i in range(H):
    for j in range(W):
        if P[i][j] != 0:
            if i > 0 and uni.init(i-1, j):
                uni.setVC(uni.getVC() + 1)
                P[i][j] = uni.changeVA(P[i][j])
            if j > 0 and uni.init(i, j-1):
                uni.setHC(uni.getHC() + 1)
                P[i][j] = uni.changeHA(P[i][j])


w = 0
for i in range(H):
    for j in range(W):
        if uni.init(i, j):
            w = max(w, uni.getHC() + uni.getVC() -1)

print(w)