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:
import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

H, W = MAP()
M = [input().rstrip() for _ in range(H)]
# for m in M:
# 	print(m)

O = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': O.append([i, j])

# print(O)

DU = [-1,1]
LR = [-1,1]
D = [[0]*W for _ in range(H)]
memo = [[-1]*W for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if M[i][j] == '#':
			D[i][j] = 9
			continue
		tmp = [0,0]
		
		skip = -1
		if memo[i-1][j] != -1:
			tmp[0] = memo[i-1][j][0]
			skip = 1
			D[i][j] = 1
		if memo[i][j-1] != -1:
			tmp[1] = memo[i][j-1][1]
			skip = 5 if skip == 1 else 2
			D[i][j] = 5 if D[i][j]==1 else 2
		
		if skip == 1 or skip == -1:
			lr = 0
			for idx,move in enumerate(LR):
				nw = j
				dw = move
				while True:
					nw += dw
					# print(i, j, nh, nw)
					if nw>W-1 or nw<0 or M[i][nw] == '#': break
					lr += 1
				tmp[1] = lr

		if skip == 2 or skip == -1:
			du = 0
			for idx,move in enumerate(DU):
				nh = i
				dh = move
				while True:
					nh += dh
					# print(i, j, nh, nw)
					if nh>H-1 or nh<0 or M[nh][j] == '#': break
					du += 1
				tmp[0] = du
		
		memo[i][j] = tmp
		ans = max(ans, sum(tmp)+1)
	
# for mem in memo:
# 	print(mem)
# for m in M:
# 	print(m)
# for d in D:
# 	print(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

H, W = MAP()
M = [input().rstrip() for _ in range(H)]
# for m in M:
# 	print(m)

O = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': O.append([i, j])

# print(O)

MOVE = [[-1,0],[1,0],[0,-1],[0,1]]

memo = [[-1]*W for _ in range(H)]
ans = 0
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': continue
		tmp = [0,0,0,0]
		skip = []
		if memo[i-1][j] != -1:
			tmp[0] = memo[i-1][j][0]
			tmp[1] = memo[i-1][j][1]
			skip.extend([0, 1])
		if memo[i][j-1] != -1:
			tmp[2] = memo[i][j-1][2]
			tmp[3] = memo[i][j-1][3]
			skip.extend([2, 3])
		for idx,move in enumerate(MOVE):
			if idx in skip:
				# print('skipping')
				continue
			cnt = 0
			nh, nw = i, j
			dh, dw = move
			while True:
				nh += dh
				nw += dw
				# print(i, j, nh, nw)
				if nh>H-1 or nh<0 or nw>W-1 or nw<0: break
				if M[nh][nw] == '#': break
				cnt += 1
			tmp[idx] = cnt
		memo[i][j] = tmp
		ans = max(ans, sum(tmp)+1)
	
print(ans)
# print(memo)

Submission status: Time Limit Exceeded

Solution code:
import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

H, W = MAP()
M = [input().rstrip() for _ in range(H)]
# for m in M:
# 	print(m)

O = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': O.append([i, j])

# print(O)

MOVE = [[-1,0],[1,0],[0,-1],[0,1]]

ans = 0
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': continue
		cnt = 1 # 自分
		for move in MOVE:
			nh, nw = i, j
			dh, dw = move
			while True:
				nh += dh
				nw += dw
				# print(i, j, nh, nw)
				if nh>H-1 or nh<0 or nw>W-1 or nw<0: break
				if M[nh][nw] == '#': break
				cnt += 1
		ans = max(ans, cnt)
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

H, W = MAP()
M = [input().rstrip() for _ in range(H)]
# for m in M:
# 	print(m)

O = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': O.append([i, j])

# print(O)

ans = 0
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': continue
		u = i
		d = H-i-1
		l = j
		r = W-j-1
		# print(u,d,l,r, " / i, j:", i,j)
		for o in O:
			oh, ow = o
			if oh==i:
				# 障害物が同じ行の右側にある場合
				if ow > j:
					r = min(r, ow-j-1)
				# 障害物が同じ行の左側にある場合
				else:
					l = min(l, j-ow-1)
			if ow==j:
				# 障害物が同じ列の上側にある場合
				if oh < i:
					u = min(u, i-oh-1)
				# 障害物が同じ列の下側にある場合
				else:
					d = min(d, oh-i-1)
		# print(u,d,l,r)
		ans = max(ans, sum([u, d, l, r])+1)
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
mat = []
for _ in range(H):
    a = list(input())[:-1]
    mat.append(a)

def calc(H, W, mat):
    x = np.array([])
    for h in range(H):
        cnt = 0
        clm = np.array([])
        for w in range(W):
            if mat[h][w] == '#':
                if cnt == 0:
                    clm = np.hstack( [clm, 0] )
                    cnt = 0
                else:
                    clm = np.hstack( [clm, [cnt]*cnt, 0] )
                    cnt = 0
            else:
                cnt += 1
                if w == W-1:
                    clm = np.hstack( [clm, [cnt]*cnt] )
        x = np.append( x, clm )
    return x.reshape(H, W)

x = calc(H, W, mat)
y = calc(W, H, np.array(mat).T).T
res = np.max( x+y ) - 1
print(int(res))

Submission status: Time Limit Exceeded

Solution code:
#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W=map(int,input().split())
S=[0]*H
for i in range(H):
    S[i]=list(input())


MAP=[[[0,0,0,0] for i in range(W)]for i in range(H)]
MAX=0
#ue

for i in range(W):
    c=0
    d=0
    for j in range(H):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        if(S[H-j-1][W-i-1]=="."):
            d+=1
            MAP[H-j-1][W-i-1][0]+=d
        else:
            d=0

#hidari
for j in range(H):
    c=0
    d=0
    for i in range(W):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
            MAX=max(MAX,MAP[j][i][0]-3)
        else:
            c=0
        if(S[H-j-1][W-i-1]=="."):
            d+=1
            MAP[H-j-1][W-i-1][0]+=d
            MAX=max(MAX,MAP[H-j-1][W-i-1][0]-3)
        else:
            d=0

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W=map(int,input().split())
S=[0]*H
for i in range(H):
    S[i]=list(input())


MAP=[[[0,0,0,0] for i in range(W)]for i in range(H)]
#MAP[H][W]

#ue
for i in range(W):
    c=0
    d=0
    for j in range(H):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        if(S[H-j-1][W-i-1]=="."):
            d+=1
            MAP[H-j-1][W-i-1][0]+=d
        else:
            d=0

#hidari
for j in range(H):
    c=0
    d=0
    for i in range(W):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        if(S[H-j-1][W-i-1]=="."):
            d+=1
            MAP[H-j-1][W-i-1][0]+=d
        else:
            d=0

#migi
MAX=0
for j in range(H):
    for i in range(W-1,-1,-1):
        MAX=max(MAX,MAP[j][i][0]-3)

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W=map(int,input().split())
S=[0]*H
for i in range(H):
    S[i]=list(input())


MAP=[[[0,0,0,0] for i in range(W)]for i in range(H)]
#MAP[H][W]

#ue
for i in range(W):
    c=0
    for j in range(H):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0

#shita
for i in range(W):
    c=0
    for j in range(H-1,-1,-1):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0

#hidari
for j in range(H):
    c=0
    for i in range(W):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0

#migi
MAX=0
for j in range(H):
    c=0
    for i in range(W-1,-1,-1):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        MAX=max(MAX,MAP[j][i][0]-3)

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W=map(int,input().split())
S=[0]*H
for i in range(H):
    S[i]=list(input())


MAP=[[[0,0,0,0] for i in range(W)]for i in range(H)]
#MAP[H][W]

#ue
for i in range(W):
    c=0
    for j in range(H):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]=c
        else:
            c=0
            MAP[j][i][0]=c

#shita
for i in range(W):
    c=0
    for j in range(H-1,-1,-1):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][1]=c
        else:
            c=0
            MAP[j][i][1]=c

#hidari
for j in range(H):
    c=0
    for i in range(W):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][2]=c
        else:
            c=0
            MAP[j][i][2]=c

#migi
for j in range(H):
    c=0
    for i in range(W-1,-1,-1):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][3]=c
        else:
            c=0
            MAP[j][i][3]=c

MAX=0
for i in range(W):
    for j in range(H):
        t=0
        t+=MAP[j][i][0]
        t+=MAP[j][i][1]
        t+=MAP[j][i][2]
        t+=MAP[j][i][3]  
        t-=3              
        MAX=max(MAX,t)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, W = map(int, input().split())
    maze = [[] for _ in range(H)]
    for i in range(H):
        maze[i] = list(input())

    u = [[0 for _ in range(W)] for _ in range(H)]
    r = [[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)]
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '#':
                continue
            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-1, -1, -1):
        for j in range(W-1, -1, -1):
            if maze[i][j] == '#':
                continue
            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] + r[i][j] + d[i][j] + l[i][j] - 3)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve():
    H, W = map(int, input().split())
    maze = [[] for _ in range(H)]
    for i in range(H):
        maze[i] = list(input())

    u = [[0 for _ in range(W)] for _ in range(H)]
    r = [[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)]
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '#':
                continue
            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-1, -1, -1):
        for j in range(W-1, -1, -1):
            if maze[i][j] == '#':
                continue
            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

    num_sum = np.zeros(H*W, int).reshape(H, W)
    for i in range(H):
        for j in range(W):
            num_sum[i][j] = u[i][j] + r[i][j] + d[i][j] + l[i][j] - 3
    print(num_sum.max())


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product

input = sys.stdin.readline

H, W = map(int, input().split())
S = [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, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue
    if j == 0:
        L[i][j] = 1
    else:
        L[i][j] = L[i][j - 1] + 1
    if i == 0:
        U[i][j] = 1
    else:
        U[i][j] = U[i - 1][j] + 1

for i, j in product(range(H), range(W - 1, -1, -1)):
    if S[i][j] == '#':
        continue
    if j == W - 1:
        R[i][j] = 1
    else:
        R[i][j] = R[i][j + 1] + 1

for i, j in product(range(H - 1, -1, -1), range(W)):
    if S[i][j] == '#':
        continue
    if i == H - 1:
        D[i][j] = 1
    else:
        D[i][j] = D[i + 1][j] + 1

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

Submission status: Time Limit Exceeded

Solution code:
def func_R(li, s, hi):
    for wi, si in enumerate(s):
        if si == '#':
            li[hi][wi] = 0
        else:
            if wi == 0:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi][wi-1] + 1

def func_L(li, s, hi):
    for wi, si in enumerate(s[::-1]):
        wi = w - wi - 1
        if si == '#':
            li[hi][wi] = 0
        else:
            if wi == w-1:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi][wi+1] + 1

def func_U(li, s, wi):
    for hi, si in enumerate(s):
        if si == '#':
            li[hi][wi] = 0
        else:
            if hi == 0:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi-1][wi] + 1

def func_D(li, s, wi):
    for hi, si in enumerate(s[::-1]):
        hi = h - hi - 1
        if si == '#':
            li[hi][wi] = 0
        else:
            if hi == h-1:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi+1][wi] + 1

def main():
    import sys
    input = sys.stdin.readline
    global h, w
    h, w = map(int, input().split())
    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)]
    s_list = ['']*w
    for hi in range(h):
        s = input()[:-1]
        func_L(L, s, hi)
        func_R(R, s, hi)
        for wi, si in enumerate(s):
            s_list[wi] += si

    for wi in range(w):
        s = s_list[wi]
        func_U(U, s, wi)
        func_D(D, s, wi)

    ans = 0
    for hi in range(h):
        for wi in range(w):
            ans = max(ans, L[hi][wi] + R[hi][wi] + U[hi][wi] + D[hi][wi])

    print(ans-3)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def func_R(li, s, hi):
    for wi, si in enumerate(s):
        if si == '#':
            li[hi][wi] = 0
        else:
            if wi == 0:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi][wi-1] + 1

def func_L(li, s, hi):
    for wi, si in enumerate(s[::-1]):
        wi = w - wi - 1
        if si == '#':
            li[hi][wi] = 0
        else:
            if wi == w-1:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi][wi+1] + 1

def func_U(li, s, wi):
    for hi, si in enumerate(s):
        if si == '#':
            li[hi][wi] = 0
        else:
            if hi == 0:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi-1][wi] + 1

def func_D(li, s, wi):
    for hi, si in enumerate(s[::-1]):
        hi = h - hi - 1
        if si == '#':
            li[hi][wi] = 0
        else:
            if hi == h-1:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi+1][wi] + 1

def main():
    global h, w
    h, w = map(int, input().split())
    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)]
    s_list = ['']*w
    for hi in range(h):
        s = input()
        func_L(L, s, hi)
        func_R(R, s, hi)
        for wi, si in enumerate(s):
            s_list[wi] += si

    for wi in range(w):
        s = s_list[wi]
        func_U(U, s, wi)
        func_D(D, s, wi)

    ans = 0
    for hi in range(h):
        for wi in range(w):
            ans = max(ans, L[hi][wi] + R[hi][wi] + U[hi][wi] + D[hi][wi])

    print(ans-3)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = np.zeros(H * W).reshape(H, W)
ans = np.zeros(H * W).reshape(H, W)

for h in range(H):
    s = [0 if i == '.' else -1 for i in input().strip()]
    S[h] = np.array(s)

for i, s in enumerate(S):
    c = 0
    q = deque([])
    for k, j in enumerate(s):
        if j == 0:
            c += 1
            q.append(k)
            continue
        for qq in q:
            ans[i, qq] = c
        q = deque([])
        c = 0
    else:
        for qq in q:
            ans[i, qq] = c
 
ans_max = 0
for w in range(W):
    c = 0
    q = []
    for i, s in enumerate(S):
        if s[w] == 0:
            c += 1
            q.append(i)
            continue
        for qq in q:
            ans[qq, w] += c
            ans_max = max(ans_max, ans[qq, w])
        q = []
        c = 0
    else:
        for qq in q:
            ans[qq, w] += c
            ans_max = max(ans_max, ans[qq, w])
        q = []
        c = 0

print(int(ans_max-1))

Submission status: Time Limit Exceeded

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

R=[[0 for i in range(W)] for j 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)]
D=[[0 for i in range(W)] for j in range(H)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] = [x * y for x, y in zip(u[hh], maze01[hh])]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] = [x * y for x, y in zip(u[hh], maze01[hh])]
    d[H - hh - 1, :] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] = [x * y for x, y in zip(d[H - hh -1], maze01[H - hh - 1])]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] = [x * y for x, y in zip(l[:, ww], maze01[:, ww])]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] = [x * y for x, y in zip(r[:, W - ww -1], maze01[:, W -ww - 1])]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze_x = [input() for _ in range(H)]
maze01 = np.array([[int(x=='.') for x in maze_x[i]] for i in range(H)])

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst1 = [i for i in maze[hh].split('#') if i != '']
        lst2 = [i for i in maze[hh].split('.') if i != '']
        ww = 0
        k1 = 0
        k2 = 0
        if maze[hh][0]=='#':
            ww += len(lst2[0])
            k2 += 1
          
        while len(lst1)>k1:
            if maze[hh][ww] == '.':
                ln = len(lst1[k1])
                cnt[hh][ww:ww+ln] = [ln]*ln
                k1 += 1
                ww += ln
            else:
                ln = len(lst2[k2])
                cnt[hh][ww:ww+ln] = [0]*ln
                k2 += 1
                ww += ln

    return cnt
u = np.zeros((H, W), dtype=np.int32)
l = np.zeros((H, W), dtype=np.int32)

u[0] = maze01[0]
l[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] = [x * y for x, y in zip(u[hh], maze01[hh])]
    l[H - hh - 1, :] = l[H - hh] + maze01[H - hh - 1]
    l[H - hh - 1] = [x * y for x, y in zip(l[H - hh -1], maze01[H - hh - 1])]

cnt = np.array(count_light(maze_x, W, H)) + u + l - 2

print(max([max(cnt[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import groupby
import sys
input = sys.stdin.readline

H, W = map(int,input().split())
S = np.array([[0 if i == "." else 1 for i in list(input())] for _ in range(H)])
rot_S = np.rot90(S, -1)

answer = np.array([[-1]*W for _ in range(H)])
for i,s in enumerate(S):
    j = 0
    for key, group in groupby(s):
        group_len = len(list(group))
        if key == 0:
            answer[i][j:j+group_len] += group_len
        j += group_len

for i,s in enumerate(rot_S):
    j = H
    for key, group in groupby(s):
        group_len = len(list(group))
        if key == 0:
            answer[j-group_len:j, i:i+1] += group_len
        j -= group_len

print(answer.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
grid = [[] for i in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        grid[i].append(1 if s[j] == '#' else 0)
#print(grid)
grid = np.array(grid)

def getRowContinue(s):
    num = [0]*len(s)
    cnt = 0
    for i in range(len(s)):
        if s[i] == 1:
            num[i] = 0
            cnt = 0
        else:
            cnt += 1
            num[i] = cnt
            for j in range(cnt):
                num[i - j] = num[i]
    return num

def getColContinue(g):
    num = [[] for _ in range(len(g))]
    for i in range(len(g)):
        for _ in range(len(g[i])):
            num[i].append(0)

    h = len(g)
    w = len(g[0])
    for j in range(w):
        cnt = 0
        for i in range(h):
            if g[i][j] == 1:
                cnt = 0
                num[i][j] = 0
            else:
                cnt += 1
                num[i][j] = cnt
                for k in range(cnt):
                    num[i - k][j] = num[i][j]
    return num


contRow = []
for i in range(H):
    contRow.append(getRowContinue(grid[i]))
contCol = getColContinue(grid)
contRow = np.array(contRow)
contCol = np.array(contCol)
cont = contRow + contCol
#print(cont.flatten())
print(np.max(cont.flatten()) - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst1 = [i for i in maze[hh].split('#') if i != '']
        lst2 = [i for i in maze[hh].split('.') if i != '']
        
        ww = 0
        k1 = 0
        k2 = 0
        while len(lst1)>k1:
            if maze[hh][ww] == '.':
                ln = len(lst1[k1])
                cnt[hh][ww:ww+ln] = [ln]*ln
                k1 += 1
            else:
                ln = len(lst2[k2])
                cnt[hh][ww:ww+ln] = [0]*ln
                k2 += 1
            ww += ln
    return cnt
cnt = (np.array(count_light(maze_x, W, H)) + np.array(count_light(maze_y, H, W)).T -1)

print(max([max(cnt[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst1 = [i for i in maze[hh].split('#') if i != '']
        lst2 = [i for i in maze[hh].split('.') if i != '']
        
        ww = 0
        k1 = 0
        k2 = 0
        
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                ln = len(lst1[k1])
                cnt[hh][ww:ww+ln] = [ln]*ln
                ww += ln
                if len(lst1)==k1:break
                k1 += 1
            else:
                ln = len(lst2[k2])
                cnt[hh][ww:ww+ln] = [0]*ln
                ww += ln
                k2 += 1
    return cnt
cnt = (np.array(count_light(maze_x, W, H)) + np.array(count_light(maze_y, H, W)).T -1)

print(max([max(cnt[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst1 = [i for i in maze[hh].split('#') if i != '']
        ww = 0
        k = 0
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                ln = len(lst1[k])
                cnt[hh][ww:ww+ln] = [ln]*ln
                ww += ln-1
                if len(lst1)==k:break
                k += 1
            ww += 1
    return cnt
cnt = (np.array(count_light(maze_x, W, H)) + np.array(count_light(maze_y, H, W)).T -1)

print(max([max(cnt[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst = [i for i in maze[hh].split('#') if i != '']
        ww = 0
        k = 0
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                ln = len(lst[k])
                cnt[hh][ww:ww+ln] = [ln]*ln
                ww += ln-1
                k += 1
            ww += 1
    return cnt
cnt = (np.array(count_light(maze_x, W, H)) + np.array(count_light(maze_y, H, W)).T -1)

print(max(0,max([max(cnt[i]) for i in range(H)])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst = [i for i in maze[hh].split('#') if i != '']
        ww = 0
        k = 0
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                for i in range(len(lst[k])):
                    cnt[hh][ww + i] = len(lst[k])
                ww += i
                k += 1
            ww += 1
    return cnt

cnt_x = np.array(count_light(maze_x, W, H))
cnt_y = np.array(count_light(maze_y, H, W))
cnt = (cnt_y.T + cnt_x - 1).tolist()

print(max(0,max([max(cnt[i]) for i in range(H)])))

Submission status: Time Limit Exceeded

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

maze = [input() for _ in range(H)]

light_max = 0

def light(xx, yy):
    ans = 0
    for dy in [-1, 1]:
        xx0 = xx
        yy0 = yy + dy
        while 0 <= yy0 <= H-1:
            if maze[yy0][xx0] == '#':break
            ans += 1
            yy0 += dy
    return ans

for hh in range(H):
    hh_lst = [i for i in maze[hh].split('#') if i !='']
    ww = 0
    k = 0
    while ww<=W-1:
        if maze[hh][ww] == '.':
            for j in range(len(hh_lst[k])):
                light_max = max(light_max, light(ww + j, hh)+len(hh_lst[k]))
                
            ww += j
            k += 1
        ww += 1
print(light_max)