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 = []
for i in range(h):
    s1 = list(input())
    s.append(s1)
p = []
q = []
r = []
t = []
l = []
for i in range(h):
    count1 = 0
    count2 = 0
    p1 = []
    q1 = []
    for j in range(w):
        if s[i][j] == ".":
            count1 = count1 + 1
            p1.append(count1)
        elif s[i][j] == "#":
            count1 = 0
            p1.append(count1)
        if s[i][w-j-1] == ".":
            count2 = count2 + 1
            q1.append(count2)
        elif s[i][w-j-1] == "#":
            count2 = 0
            q1.append(count2)
    q1.reverse()
    p.append(p1)
    q.append(q1)
for i in range(w):
    count1 = 0
    count2 = 0
    r1 = []
    t1 = []
    for j in range(h):
        if s[j][i] == ".":
            count1 = count1 + 1
            r1.append(count1)
        elif s[j][i] == "#":
            count1 = 0
            r1.append(count1)
        if s[h-j-1][i] == ".":
            count2 = count2 + 1
            t1.append(count2)
        elif s[h-j-1][i] == "#":
            count2 = 0
            t1.append(count2)
    t1.reverse()
    r.append(r1)
    t.append(t1)
for i in range(h):
    for j in range(w):
        l.append(p[i][j]+q[i][j]+r[j][i]+t[j][i])
print(max(l)-3)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
import numpy as np
MOD = 1000000007

buffer = sys.stdin.buffer
H, W = list(map(int,buffer.readline().split()))
S = np.empty((0, W), int)
for i in range(H):
	tmp = np.frombuffer(buffer.readline(), dtype='B')
	S = np.append(S,[(tmp == ord("."))[:W]], axis=0)
L = np.empty((H,W), dtype="i4")
R = np.empty((H,W), dtype="i4")
U = np.empty((H,W), dtype="i4")
D = np.empty((H,W), dtype="i4")
 
L[:,0] = S[:,0]
for i in range(1,W):
    L[:,i] = (L[:,i-1] + 1) * S[:,i]
 
R[:,-1] = S[:,-1]
for i in range(1,W):
    R[:,-1-i] = (R[:,-i] + 1) * S[:,-1-i]
 
U[0] = S[0]
for i in range(1,H):
    U[i] = (U[i-1] + 1) * S[i]
 
D[-1] = S[-1]
for i in range(1,H):
    D[-1-i] = (D[-i] + 1) * S[-1-i]
 
score = L + R + U + D - 3
print(int(score.max()))

Submission status: Time Limit Exceeded

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


class UnionFind:

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

columns = UnionFind(W*H)
rows = UnionFind(W*H)

# init columns
for row in range(H):
    for col1, col2 in zip(range(W), range(1, W)):
        if grid[row][col1] == "." and grid[row][col2] == ".":
            columns.union(row*W+col1, row*W+col2)

# init rows:
for col in range(W):
    for row1, row2 in zip(range(H), range(1, H)):
        if grid[row1][col] == "." and grid[row2][col] == ".":
            rows.union(row1*W+col, row2*W+col)

ans = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == ".":
            un = row*W+col
            tmp = rows.get_size(un)+columns.get_size(un)-1
            ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
import numpy as np
MOD = 1000000007
def culc(s, h, w, x, y):
	count = 1
	return count

h, w = map(int, input().split())
s = np.zeros((h, w), int)
for i in range(h):
	s2 = input()
	for j in range(len(s2)):
		s[i][j] = (1 if s2[j] == "#" else 0)

max = 0
left = np.zeros((h, w), int)
right = np.zeros((h, w), int)
up = np.zeros((h, w), int)
down = np.zeros((h, w), int)
for i in range(h):
	for j in range(w):
		left[i][j] = 0 if s[i][j] == 1 else 1 if j <= 0 else left[i][j - 1] + 1
		right[i][w - j - 1] = 0 if s[i][w - j - 1] == 1 else 1 if j <= 0 else right[i][w - j] + 1
		up[i][j] = 0 if s[i][j] == 1 else 1 if i <= 0 else up[i - 1][j] + 1
		down[h - i - 1][j] = 0 if s[h - i - 1][j] == 1 else 1 if i <= 0 else down[h - i][j] + 1
			
for i in range(h):
	for j in range(w):
		tmp = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
		if max < tmp:
			max = tmp

print(max)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
MOD = 1000000007
def culc(s, h, w, x, y):
	count = 1
	return count

h, w = map(int, input().split())
s = []
for i in range(h):
	s2 = input()
	s3 = []
	for j in range(len(s2)):
		s3.append(1 if s2[j] == "#" else 0)
	s.append(s3)

max = 0
left = [[0] * w for i in range(h)]
right = [[0] * w for i in range(h)]
up = [[0] * w for i in range(h)]
down = [[0] * w for i in range(h)]
for i in range(h):
	for j in range(w):
		left[i][j] = 0 if s[i][j] == 1 else 1 if j <= 0 else left[i][j - 1] + 1
		right[i][w - j - 1] = 0 if s[i][w - j - 1] == 1 else 1 if j <= 0 else right[i][w - j] + 1
		up[i][j] = 0 if s[i][j] == 1 else 1 if i <= 0 else up[i - 1][j] + 1
		down[h - i - 1][j] = 0 if s[h - i - 1][j] == 1 else 1 if i <= 0 else down[h - i][j] + 1
			
for i in range(h):
	for j in range(w):
		tmp = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
		if max < tmp:
			max = tmp

print(max)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[]
for _ in range(h):
    s.append(list(input()))
l=[[0 for x in range(w+2)] for y in range(h+2)]
r=[[0 for x in range(w+2)] for y in range(h+2)]
u=[[0 for x in range(w+2)] for y in range(h+2)]
d=[[0 for x in range(w+2)] for y in range(h+2)]
#l
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i-1][j-1]==".":
            l[i][j]=l[i][j-1]+1
        else:
            l[i][j]=0
#r
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i-1][w-(j-1)-1]==".":
            r[i][w+1-j]=r[i][w+1-j+1]+1
        else:
            r[i][w+1-j]=0
#u
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i-1][j-1]==".":
            u[i][j]=u[i-1][j]+1
        else:
            u[i][j]=0
#d
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[h-(i-1)-1][j-1]==".":
            d[h+1-i][j]=d[h+1-i+1][j]+1
        else:
            d[h+1-i][j]=0
ans=0
for y in range(1,h+1):
    for x in range(1,w+1):
        sum=r[y][x]+l[y][x]+u[y][x]+d[y][x]-3
        if ans<sum:
            ans=sum
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, heapq
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

H, W = read_int()
grid = []
import numpy as np
L = np.zeros((H, W), int)
R = np.zeros((H, W), int)
U = np.zeros((H, W), int)
D = np.zeros((H, W), int)
res = np.zeros((H, W), int)
# L = [[0 for _ in range(W)] for _ in range(H)]
# R = [[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)]
# res = [[0 for _ in range(W)] for _ in range(H)]

for _ in range(H):
    row = list(" ".join(input()).split())
    grid.append(row)

# r = []
# heapq.heapify(r)
# for i in range(H * W):
#     heapq.heappush(r, 0)
# r = [3 for i in range(H*W)]
def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == "#":
                L[i][j] = U[i][j] = 0
            else:
                L[i][j] = 1 if j == 0 else L[i][j - 1] + 1
                U[i][j] = 1 if i == 0 else U[i - 1][j] + 1
                res[i][j] += L[i][j] + U[i][j]
                ans = max(res[i][j], ans)
                # r[i* W + j] -= L[i][j] + U[i][j]

            if grid[H - i - 1][W - j - 1] == "#":
                R[H - i - 1][W - j - 1] = D[H - i - 1][W - j - 1] = 0
            else:
                R[H - i - 1][W - j - 1] = 1 if j == 0 else R[H - i - 1][W - j] + 1
                D[H - i - 1][W - j - 1] = 1 if i == 0 else D[H - i][W - j - 1] + 1
                res[H - i - 1][W - j - 1] += R[H - i - 1][W - j - 1] + D[H - i - 1][W - j - 1]
                ans = max(res[H - i - 1][W - j - 1], ans)
    return ans - 3

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

s = [list(input().rstrip()) for _ in range(h)]

left = np.zeros((h + 2, w + 2), dtype=int)
right = np.zeros((h + 2, w + 2), dtype=int)
up = np.zeros((h + 2, w + 2), dtype=int)
down = np.zeros((h + 2, w + 2), dtype=int)

ans = 0
for r, c in ((r, c) for r in range(1, h + 1) for c in range(1, w + 1)):
    r_r, c_r = h + 1 - r, w + 1 - c
    if s[r - 1][c - 1] == '.':
        left[r][c] = left[r][c - 1] + 1
        up[r][c] = up[r - 1][c] + 1
    if s[r_r - 1][c_r - 1] == '.':
        right[r_r][c_r] = right[r_r][c_r + 1] + 1
        down[r_r][c_r] = down[r_r + 1][c_r] + 1


summary = left + right + up + down - 3
print(int(np.max(summary)))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
MOD = 1000000007
def culc(s, h, w, x, y):
	if s[y][x] == 1:
		return 0
	count = 1
	for i in range(x):
		if s[y][x - i - 1] == 1:
			break
		count+=1
	for i in range(w - x - 1):
		if s[y][x + i + 1] == 1:
			break
		count+=1
	for i in range(y):
		if s[y - i - 1][x] == 1:
			break
		count+=1
	for i in range(h - y - 1):
		if s[y + i + 1][x] == 1:
			break
		count+=1
	return count

h, w = map(int, input().split())
s = []
for i in range(h):
	s2 = input()
	s3 = []
	for j in range(len(s2)):
		s3.append(1 if s2[j] == "#" else 0)
	s.append(s3)

max = 0
for i in range(h):
	for j in range(w):
		tmp = culc(s, h, w, j, i)
		if max < tmp:
			max = tmp

print(max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

s = [list(input().rstrip()) for _ in range(h)]

left = np.zeros((h + 2, w + 2))
right = np.zeros((h + 2, w + 2))
up = np.zeros((h + 2, w + 2))
down = np.zeros((h + 2, w + 2))

for r, c in ((r, c) for r in range(1, h + 1) for c in range(1, w + 1)):
    r_r, c_r = h + 1 - r, w + 1 - c
    if s[r - 1][c - 1] == '.':
        left[r][c] = left[r][c - 1] + 1
        up[r][c] = up[r - 1][c] + 1
    if s[r_r - 1][c_r - 1] == '.':
        right[r_r][c_r] = right[r_r][c_r + 1] + 1
        down[r_r][c_r] = down[r_r + 1][c_r] + 1

summary = left + right + up + down - 3
print(int(np.max(summary)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

s = [input().rstrip() for _ in range(h)]

left = np.zeros((h + 2, w + 2))
right = np.zeros((h + 2, w + 2))
up = np.zeros((h + 2, w + 2))
down = np.zeros((h + 2, w + 2))

for r, c in ((r, c) for r in range(1, h + 1) for c in range(1, w + 1)):
    r_r, c_r = h + 1 - r, w + 1 - c
    if s[r - 1][c - 1] == '.':
        left[r][c] = left[r][c - 1] + 1
        up[r][c] = up[r - 1][c] + 1
    if s[r_r - 1][c_r - 1] == '.':
        right[r_r][c_r] = right[r_r][c_r + 1] + 1
        down[r_r][c_r] = down[r_r + 1][c_r] + 1

summary = left + right + up + down - 3
print(int(np.max(summary)))

Submission status: Time Limit Exceeded

Solution code:
def checklamp(S,y,x,H,W):
    count = 1 #初期位置のみ

    #←
    ty = y
    tx = x
    while True:
        if tx-1 >= 0:
            if S[ty][tx-1] == '.':
                count += 1
                tx -= 1
            else:
                break
        else:
            break
    #→
    ty = y
    tx = x
    while True:
        if tx+1 <= W-1:
            if S[ty][tx+1] == '.':
                count += 1
                tx += 1
            else:
                break
        else:
            break

    #↑
    ty = y
    tx = x
    while True:
        if ty-1 >= 0:
            if S[ty-1][tx] == '.':
                count += 1
                ty -= 1
            else:
                break
        else:
            break

    #↓
    ty = y
    tx = x
    while True:
        if ty+1 <= H-1:
            if S[ty+1][tx] == '.':
                count += 1
                ty += 1
            else:
                break
        else:
            break

    return count

#メイン処理
H,W = map(int,input().split())
S = []

#2次元配列で保存
for _ in range(H):
    a = input()
    S.append(list(a))

maxlamp = 0

for i in range(H):
    for j in range(W):
        #[i(y)][j(x)]のステータス確認
        if S[i][j] != '#':
            tmp = checklamp(S,i,j,H,W)
            maxlamp = max(tmp,maxlamp)

print(maxlamp)

Submission status: Time Limit Exceeded

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

row = [[0] * W for _ in range(H)]
line = [[0] * W for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if i != 0:
                if row[i-1][j] != 0:
                    row[i][j] = row[i-1][j]
                    continue
            c = 1
            if i+c == H:
                row[i][j] = c
                continue
            while S[i+c][j] == '.':
                c += 1
                if i+c == H:
                    break
            row[i][j] = c

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if j != 0:
                if line[i][j-1] != 0:
                    line[i][j] = line[i][j-1]
                    ans = max(ans, row[i][j]+line[i][j]-1)
                    continue
            c = 1
            if j+c == W:
                line[i][j] = c
                ans = max(ans, row[i][j]+line[i][j]-1)
                continue
            while S[i][j+c] == '.':
                c += 1
                if j+c == W:
                    break
            line[i][j] = c
            ans = max(ans, row[i][j]+line[i][j]-1)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
def count_max_space(mat, H, W):
	max_count = 0
	for x in range(H):
		for y in range(W):
			if(mat[x][y]=='#'):
				L[x][y]=0
				R[x][y]=0
				U[x][y]=0
				D[x][y]=0
			elif(mat[x][y]=='.'):
				if(y==0):
					L[x][y]=1
				if(y>0):
					L[x][y]=L[x][y-1]+1

				if(L[x][y]==1):
					i=y
					while(i<W and mat[x][i]=='.'):
						R[x][y]+=1
						i+=1
				if(L[x][y]>1):
					R[x][y]=R[x][y-1]-1
				
				if(x==0):
					U[x][y]=1
				if(x>0):
					U[x][y]=U[x-1][y]+1
				if(U[x][y]==1):	
					i=x
					while(i<H and mat[i][y]=='.'):
						D[x][y]+=1
						i+=1
				if(U[x][y]>1):
					D[x][y]=D[x-1][y]-1

			count_so_far = L[x][y]+R[x][y]+U[x][y]+D[x][y]
			if(count_so_far>max_count):
				max_count=count_so_far

	return max_count-3

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

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

for i in range(H):
	mat.append(input())

print(count_max_space(mat, H, W))

Submission status: Time Limit Exceeded

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

S = []
for i in range(h):
    s = input()
    #print(s)
    S.append(s)
#print(S)
#sys.exit()
max_light = 0
for i in range(h):
    for j in range(w):
        # 障害物の上に照明は置かない
        if S[i][j] == 0:
            continue
        row = list(S[i])
        column = [S[k][j] for k in range(h)]
        #print(row, column)
        #sys.exit()
        sum_row = 0
        for k in range(len(row)):
            if row[k] == '#':
                if k > j:
                    break
                else:
                    sum_row = 0
            else:
                sum_row += 1
        sum_column = 0
        for k in range(len(column)):
            if column[k] == '#':
                if k > i:
                    break
                else:
                    sum_column = 0
            else:
                sum_column += 1
        
        sum_light = sum_row + sum_column -1
        if max_light < sum_light:
            max_light = sum_light
                
        
print(max_light)

Submission status: Time Limit Exceeded

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

S = []
for i in range(h):
    s = input()
    #print(s)
    s = [1 if x=="." else 0 for x in s]
    #print(s)
    S.append(s)
#print(S)
max_light = 0
for i in range(h):
    for j in range(w):
        if S[i][j] == 0:
            continue
        row = S[i]
        column = [S[k][j] for k in range(h)]
        left, right, up, down = 0, 0, 0, 0
        # 左探索
        while(True):
            if j-left == 0:
                # 左方向はすべて光る
                break
            elif row[j-left] == 0:
                left -= 1
                break
            else:
                left += 1
        row_left = sum(row[j-left:j])
        # 右探索
        while(True):
            if j+right == w-1:
                # 右方向はすべて光る
                break
            elif row[j+right] == 0:
                right -= 1
                break
            else:
                right += 1
        row_right = sum(row[j+1:j+right+1])
        # 上探索
        while(True):
            if i-up == 0:
                # 左方向はすべて光る
                break
            elif column[i-up] == 0:
                up -= 1
                break
            else:
                up += 1
        column_up = sum(column[i-up:i])
        # 下探索
        while(True):
            if i+down == h-1:
                # 右方向はすべて光る
                break
            elif column[i+down] == 0:
                down -= 1
                break
            else:
                down += 1
        column_down = sum(column[i+1:i+down+1])
        
        light = row_right + row_left + column_up + column_down + 1
        if light > max_light:
            max_light = light
print(max_light)

Submission status: Time Limit Exceeded

Solution code:
def count_max_space(mat, H, W):
	max_count = 0
	spot = None
	for x in range(H):
		for y in range(W):
			if(mat[x][y]=='.'):
				count=0
				for i in range(x,-1,-1):
					if(mat[i][y]=='.'):
						count+=1
					else:
						break
				for i in range(x,H):
					if(mat[i][y]=='.'):
						count+=1
					else:
						break
				for j in range(y,-1,-1):
					if(mat[x][j]=='.'):
						count+=1
					else:
						break
				for j in range(y,W):
					if(mat[x][j]=='.'):
						count+=1
					else:
						break
				if(count>max_count):
					max_count = count
					spot = (x,y)

	return max_count-3


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

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

print(count_max_space(mat, H, W))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

Height, Width = map(int,input().split(" "))

lineBlocks = [(input()) for i in range(Height)]

twoDimMap = []
for Block in lineBlocks:
  twoDimMap.append(list(Block))
  
ansList = []
heightList = np.zeros((Height, Width), dtype=int)
widthList  = np.zeros((Height, Width), dtype=int)

for i in range(Height):
  for j in range(Width):
    
    if '#' == twoDimMap[i][j]:
      heightList[i][j] = 0
      widthList[i][j]  = 0
      continue

    else:
        if heightList[i][j] == 0:

            k_up = i+1
            height_len = 0
            while( k_up < Height and twoDimMap[k_up][j] != "#"):
                height_len += 1
                k_up += 1
                
            
            k_down = i-1
            while( k_down >= 0 and twoDimMap[k_down][j] != "#"):
                height_len += 1
                k_down -= 1
            
            for k in range(k_down+1,k_up):
                heightList[k][j] = height_len + 1


        if widthList[i][j] == 0:
            k_right = j+1
            width_len = 0
            while(k_right < Width and twoDimMap[i][k_right] != "#"):
                width_len += 1
                k_right += 1

            k_left = j-1
            while(k_left >= 0 and twoDimMap[i][k_left] != "#"):
                width_len += 1
                k_left -= 1
            
            for k in range(k_left+1,k_right):
                widthList[i][k] = width_len

print(np.array(heightList + widthList).max())

Submission status: Time Limit Exceeded

Solution code:
Height, Width = map(int,input().split(" "))

lineBlocks = [(input()) for i in range(Height)]

twoDimMap = []
for Block in lineBlocks:
  twoDimMap.append(list(Block))

ansList = []
for i in range(Height):
  for j in range(Width):
    
    if '#' == twoDimMap[i][j]:
      continue

    else:
        k = i+1
        height_len = 0
        while( k < Height and twoDimMap[k][j] != "#"):
          height_len += 1
          k += 1
        
        k = i-1
        while( k >= 0 and twoDimMap[k][j] != "#"):
          height_len += 1
          k -= 1
    
        k = j+1
        width_len = 0
        while(k < Width and twoDimMap[i][k] != "#"):
          width_len += 1
          k += 1

        k = j-1
        while(k >= 0 and twoDimMap[i][k] != "#"):
          width_len += 1
          k -= 1

        light_range = height_len + width_len + 1
        ansList.append(light_range)
        
print(max(ansList))

Submission status: Time Limit Exceeded

Solution code:
def main():
	H, W = map(int, input().split())
	S = [""]*H
	for i in range(H):
		S[i] = input()
	r = [[0 for _ in range(W)] for _ in range(H)]
	c = [[0 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		for j in range(W):
			if S[i][j] == "#":
				continue
			r[i][j] = r[i][j-1]+1 if j > 0 else 1
		for j in range(W-2, -1, -1):
			if r[i][j+1] == 0 or r[i][j] == 0:
				continue
			r[i][j] = r[i][j+1]

	for j in range(W):
		for i in range(H):
			if S[i][j] == "#":
				continue
			c[i][j] = c[i-1][j]+1 if i > 0 else 1
		for i in range(H-2, -1, -1):
			if c[i+1][j] == 0 or c[i][j] == 0:
				continue
			c[i][j] = c[i+1][j]

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


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

hidari=[[0 for i in range(w)] for j in range(h)]
migi=[[0 for i in range(w)] for j in range(h)]
ue=[[0 for i in range(w)] for j in range(h)]
sita=[[0 for i in range(w)] for j in range(h)]

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

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

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


mx=0
for i in range(w):
  count=0
  for j in range(h):
    if s[j][i]=="#":
      count=0
      ue[j][i]=0
    else:
      count+=1
      ue[j][i]=count
    mx=max(mx,hidari[j][i]+migi[j][i]+ue[j][i]+sita[j][i])
print(mx-3)

Submission status: Time Limit Exceeded

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

hidari=[[0 for i in range(w)] for j in range(h)]
migi=[[0 for i in range(w)] for j in range(h)]
ue=[[0 for i in range(w)] for j in range(h)]
sita=[[0 for i in range(w)] for j in range(h)]

for j in range(h):
  count=0
  for i in range(w):
    if s[j][i]=="#":
      count=0
      hidari[j][i]=0
    elif i==0:
      count=1
      hidari[j][i]=1
    else:
      count+=1
      hidari[j][i]=count

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

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


mx=0
for i in range(w):
  count=0
  for j in range(h):
    if s[j][i]=="#":
      count=0
      ue[j][i]=0
    elif j==0:
      count=1
      ue[j][i]=1
    else:
      count+=1
      ue[j][i]=count
    mx=max(mx,hidari[j][i]+migi[j][i]+ue[j][i]+sita[j][i])
print(mx-3)

Submission status: Time Limit Exceeded

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

hidari=[[0 for i in range(w)] for j in range(h)]
migi=[[0 for i in range(w)] for j in range(h)]
ue=[[0 for i in range(w)] for j in range(h)]
sita=[[0 for i in range(w)] for j in range(h)]

for j in range(h):
  count=0
  for i in range(w):
    if s[j][i]=="#":
      count=0
      hidari[j][i]=0
    elif i==0:
      count=1
      hidari[j][i]=1
    else:
      count+=1
      hidari[j][i]=count

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

for i in range(w):
  count=0
  for j in range(h):
    if s[j][i]=="#":
      count=0
      ue[j][i]=0
    elif j==0:
      count=1
      ue[j][i]=1
    else:
      count+=1
      ue[j][i]=count

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

mx=0
for j in range(h):
  for i in range(w):
    mx=max(mx,hidari[j][i]+migi[j][i]+ue[j][i]+sita[j][i])
print(mx-3)

Submission status: Time Limit Exceeded

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

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]


for j in range(h):
  count_yoko=0
  for i in range(w):
    if s[j][i]==".":
      if count_yoko>0:
        for k in range(count_yoko):
          yoko[j][i-k-1]+=1
      count_yoko+=1
      yoko[j][i]+=count_yoko
    else:
      count_yoko=0

for i in range(w):
  count_tate=0
  for j in range(h):
    if s[j][i]==".":
      if count_tate>0:
        for k in range(count_tate):
          yoko[j-k-1][i]+=1
      count_tate+=1
      yoko[j][i]+=count_tate
    else:
      count_tate=0

mx=0
for j in range(h):
  for i in range(w):
    mx=max(mx,yoko[j][i]+tate[j][i])
print(mx-1)

Submission status: Time Limit Exceeded

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

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]


for j in range(h):
  count_yoko=0
  for i in range(w):
    if s[j][i]==".":
      if count_yoko>0:
        for k in range(count_yoko):
          yoko[j][i-k-1]+=1
      count_yoko+=1
      yoko[j][i]+=count_yoko
    else:
      count_yoko=0

for i in range(w):
  count_tate=0
  for j in range(h):
    if s[j][i]==".":
      if count_tate>0:
        for k in range(count_tate):
          yoko[j-k-1][i]+=1
      count_tate+=1
      yoko[j][i]+=count_tate
    else:
      count_tate=0

wa = np.array(yoko) + np.array(tate)
print(np.amax(wa)-1)

Submission status: Time Limit Exceeded

Solution code:
#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
#from functools import lru_cache
import numpy as np

input = stdin.readline
#setrecursionlimit(1000)

#constant


#variable

#function
#@lru_cache(maxsize=None)

#class

#main function
def main():
    H, W = list(map(int,input().split()))
    S = [input() for _ in range(H)]
    L = np.zeros((H,W))
    R = np.zeros((H,W))
    U = np.zeros((H,W))
    D = np.zeros((H,W))

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

            if S[i][W-j-1] == "#":
                R[i,W-j-1] = 0
            elif S[i][W-j-1] == ".":
                if j == 0:
                    R[i,W-j-1] = 1
                else:
                    R[i,W-j-1] = R[i,W-j] + 1

            if S[i][j] == "#":
                U[i,j] = 0
            elif S[i][j] == ".":
                if i == 0:
                    U[i,j] = 1
                else:
                    U[i,j] = U[i-1,j] + 1

            if S[H-i-1][j] == "#":
                D[H-i-1,j] = 0
            elif S[H-i-1][j] == ".":
                if i == 0:
                    D[H-i-1,j] = 1
                else:
                    D[H-i-1,j] = D[H-i,j] + 1

    maxScore = 0
    score = np.array([L[i,j]+R[i,j]+U[i,j]+D[i,j]-3 for i in range(H) for j in range(W)])
    print(int(score.max()))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, raw_input().split())
S = [[0 if c == "." else 1 for c in raw_input()] for i in range(h)]
L = [[0]*w for i in range(h)]
R = [[0]*w for i in range(h)]
U = [[0]*w for i in range(h)]
D = [[0]*w for i in range(h)]

for i in xrange(h):
    ps = 0
    for j in xrange(w):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            L[i][j] = ps

for j in xrange(w):
    ps = 0
    for i in xrange(h):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            U[i][j] = ps

for i in xrange(h-1, -1, -1):
    ps = 0
    for j in xrange(w-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            R[i][j] = ps
for j in xrange(w-1, -1, -1):
    ps = 0
    for i in xrange(h-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            D[i][j] = ps
maxLight = 0
for i in xrange(h):
    for j in xrange(w):
        maxLight = max(maxLight, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print maxLight