Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

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

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

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

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

Sample Input 1

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

Sample Output 1

8

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

Sample Input 2

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

Sample Output 2

13



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


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = input()
T = ['' for j in range(W)]
for j in range(W):
    for i in range(H):
        T[j] += S[i][j]
#print(T)
yoko = [[0 for j in range(W)] for i in range(H)]
tate = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    tenretu = S[i].split('#')
    #print(tenretu)
    count = 0
    for now in tenretu:
        if now == '':
            count += 1
        else:
            length = len(now)
            for j in range(length):
                yoko[i][count] = length
                count += 1
            count += 1


for j in range(W):
    tenretu = T[j].split('#')
    #print(tenretu)
    count = 0
    for now in tenretu:
        if now == '':
            count += 1
        else:
            length = len(now)
            for i in range(length):
                tate[count][j] = length
                count += 1
            count += 1
maxdp = 0
for i in range(H):
    for j in range(W):
        maxdp = max(maxdp, tate[i][j] + yoko[i][j]-1)
print(maxdp)

#print(yoko)
#print(tate)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[input() for i in range(h)]
ans=0
judge=0
c=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            for k in s[i][:j]:
                if k==".":c+=1
                else: c=0
            judge+=c
            c=0
            for k in s[i][j:]:
                if k == ".":
                    c += 1
                else: break
            judge += c
            c = 0
            for k in range(h-i):
                if s[k+i][j]==".":c+=1
                else: break
            judge+=c
            c=0
            for k in range(0,i):
                if s[k][j]==".":c+=1
                else: c=0
            judge+=c
            ans=max(ans,judge)
            judge=c=0
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
import numpy as np

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

m_horizontal=[[0 for i in range(W)] for j in range(H)]
m_vertical=[[0 for i in range(W)] for j in range(H)]


for y in range(H):
    for x in range(W):
        if S[y][x]=='#':
            m_horizontal[y][x]=0
        elif x==0 or m_horizontal[y][x-1]==0:
            cnt=0
            i=x
            while S[y][i]=='.':
                cnt+=1
                i+=1
                if i==W:
                    break
            m_horizontal[y][x]=cnt
        else:
            m_horizontal[y][x]=m_horizontal[y][x-1]


        if S[y][x]=='#':
            m_vertical[y][x]=0
        elif y==0 or m_vertical[y-1][x]==0:
            cnt=0
            i=y
            while S[i][x]=='.':
                cnt+=1
                i+=1
                if i==H:
                    break
            m_vertical[y][x]=cnt
        else:
            m_vertical[y][x]=m_vertical[y-1][x]

ho=np.array(m_horizontal)
ve=np.array(m_vertical)
hv=ho+ve
print(np.amax(hv)-1)

Submission status: Time Limit Exceeded

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


def solve():
    H, W = map(int, input().split())
    s_arr = np.zeros(shape=(H, W))
    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

    memo = [[(-1, -1) for w in range(W)] for h in range(H)]

    def count_light(arr, pos):
        start = 0
        end = 0
        active = False
        for i, s in enumerate(arr):
            if i == pos:
                active = True
            if s == 1:
                if active == True:
                    return (start, end)
                else:
                    start = i + 1
                    end = i + 1
            else:
                end = i
        return start, end

    def count_hw_light(h, w):
        if s_arr[h][w] == 1:
            return 0

        m = memo[h][w] # (3, 2) / (-1, -1) / ( -1, 2) / (3, -1)
        count = 0
        counth = m[0]
        countw = m[1]
        if counth == -1:
            arr = s_arr[:, w]
            start, end = count_light(arr, h)
            count += (end - start) + 1
            for i in range(start, end+1):
                memo[i][w] = ((end - start) + 1, countw)
        else:
            count += counth

        if countw == -1:
            arr = s_arr[h, :]
            start, end = count_light(arr, w)
            count += (end - start) + 1
            for i in range(start, end+1):
                memo[h][i] = (counth, (end - start) + 1)
        else:
            count += countw

        return count

    mx_ans = 0
    for h in range(H):
        for w in range(W):
            ans = count_hw_light(h, w) -1 # 重複カウント消し
            if ans >= mx_ans:
                mx_ans = ans

    print(mx_ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W=map(int,input().split())
L=[]
l=["#" for i in range(W+2)]
L.append(l)
#print(L)
for i in range(H):
    s=list(input().rstrip())
    s=["#"]+s+["#"]
    L.append(s)
L.append(s)

#print(L)
A=[[[0,0,0,0]for i in range(W+2)]for j in range(H+2)]
#print(A)
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]==".":
            A[i][j][0]=A[i][j-1][0]+1
            A[i][j][1]=A[i-1][j][1]+1
#print(A)
ANS=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[H+1-i][W+1-j]==".":
            A[H+1-i][W+1-j][2]=A[H+1-i][W+2-j][2]+1
            A[H+1-i][W+1-j][3]=A[H+2-i][W+1-j][3]+1
            if sum(A[H+1-i][W+1-j])-3>ANS:
                ANS=sum(A[H+1-i][W+1-j])-3
#print(A)

print(ANS)

Submission status: Time Limit Exceeded

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

def f(H, W, S):
    hs = []
    vs = []
    sts = [0]*W

    for j, s in enumerate(S):
        st = 0
        
        for i, c in enumerate(s):
            if c == '#':
                if st < i:
                    hs.append((i-st, j, st, i))
                st = i+1

                if sts[i] < j:
                    vs.append((j-sts[i], i, sts[i], j))

                sts[i] = j+1

        if st < W:
            hs.append((W-st, j, st, W))
            
    for i in range(W):
        if sts[i] < H:
            vs.append((H-sts[i], i, sts[i], H))
	 
    hs = sorted(hs, reverse=True)
    vs = sorted(vs, reverse=True)
    m = 0

    for h in hs:
        sz1 = h[3] - h[2]

        for v in vs:
            sz2 = v[3] - v[2]
            if sz1 + sz2 - 1 <= m:
                break

            if h[1] >= v[2] and h[1] < v[3] and \
               v[1] >= h[2] and v[1] < h[3]:
    
                m = sz1 + sz2 - 1

    return m


def main():
    H,W = map(int, input().split())
    S = list(input() for i in range(H))
    print(f(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = Is()
mat = [[0]*W for i in range(H)]
inp = []
for i in range(H):
    inp.append(list(S()))
for i in range(H):
    t = 0
    for j in range(W):
        if inp[i][j] == ".":
            t += 1
            if j == W-1:
                for k in range(j+1-t,j+1):
                    mat[i][k] += t
        elif inp[i][j] == "#":
            for k in range(j-t,j):
                mat[i][k] += t
            t = 0
#print(*mat)
for j in range(W):
    t = 0
    for i in range(H):
        if inp[i][j] == ".":
            t += 1
            if i == H-1:
                for k in range(i+1-t,i+1):
                    mat[k][j] += t
        elif inp[i][j] == "#":
            for k in range(i-t,i):
                mat[k][j] += t
            t = 0    
#print(*mat)
ans = 0
for e in mat:
    ans = max(ans,max(e))
print(max(0,ans-1))

Submission status: Time Limit Exceeded

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

light_space = [[1 for i in range(w)] for j in range(h)]
max_light = 0
for i in range(w):
    light = -1
    light_right = -1
    for j in range(h):
        low_point = len(space)-j-1

        if space[j][i] == "#":
            light = -1
            light_space[j][i] = 0
        else:
            light += 1
            light_space[j][i] += light

        if space[low_point][i] == "#":
            light_right = -1
            light_space[low_point][i] = 0
        else:
            light_right += 1
            light_space[low_point][i] += light_right

for j in range(h):
    light = -1
    light_right = -1
    for i in range(w):
        right_point = len(space[j])-i-1

        if space[j][i] == "#":
            light = -1
            light_space[j][i] = 0
        else:
            light += 1
            light_space[j][i] += light
        
        if space[j][right_point] == "#":
            light_right = -1
            light_space[j][right_point] = 0
        else:
            light_right += 1
            light_space[j][right_point] += light_right

        max_light = max(max_light,light_space[j][right_point],light_space[j][i])


print(max_light)

Submission status: Time Limit Exceeded

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

area = []

for _ in range(H):
    area.append(input())
    
def area_search(x, y):
    count = 0
    # up
    for place in range(y-1, -1, -1):
        if area[place][x] == ".":
            count += 1
        else:
            break
    
    # left
    for place in range(x-1, -1, -1):
        if area[y][place] == ".":
            count += 1
        else:
            break
            
    # down
    for place in range(y + 1, H, 1):
        if area[place][x] == ".":
            count += 1
        else:
            break
            
    # right
    for place in range(x + 1, W, 1):
        if area[y][place] == ".":
            count += 1
        else:
            break
            
    # place
    count += 1
    
    return count
  
candidate = []
for i in range(H):
    for j in range(W):
        if area[i][j] == '.':
            candidate.append(area_search(j, i))
print(max(candidate))

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
state = []
for i in range(H):
    row_list = list(input())
    state.append(row_list)


def light(row, col, state):
    lighted_count = 0
    col1 = copy.copy(col)
    next = '.'
    while next == '.':
        state[row][col1] = '.'
        lighted_count += 1
        col1 += 1
        if col1 >= W:
            break
        next = state[row][col1]
    
    col2 = copy.copy(col)
    next = '.'
    while next == '.':
        state[row][col2] = '.'
        lighted_count += 1
        col2 -= 1
        if col2 < 0:
            break
        next = state[row][col2]

    row1 = copy.copy(row)
    next = '.'
    while next == '.':
        state[row1][col] = '.'
        lighted_count += 1
        row1 += 1
        if row1 >= H:
            break
        next = state[row1][col]

    row2 = copy.copy(row)
    next = '.'
    while next == '.':
        state[row2][col] = '.'
        lighted_count += 1
        row2 -= 1
        if row2 < 0:
            break
        next = state[row2][col]

    lighted_count -= 3
    return lighted_count



def blank_fun(state):
    blank_list = []
    for h in range(H):
        for w in range(W):
            if state[h][w] == '.':
                blank_list.append([h, w])
    return blank_list


blank_list = blank_fun(state)
blank_count = 0
for blank in blank_list:
    row = blank[0]
    col = blank[1]
    blank_count_now = light(row, col, state)

    if blank_count_now > blank_count:
        blank_count = blank_count_now


print(blank_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)


def search_y(i, j, matrix):
    """i, j について，y方向を埋める
    """
    to_plus = 0
    to_minus = 0
    while(True):
        to_plus += 1
        if (matrix[i + to_plus][j][0] == 0):
            continue
        else:
            to_plus -= 1
            break
    while(True):
        to_minus += 1
        if (matrix[i - to_minus][j][0] == 0):
            continue
        else:
            to_minus -= 1
            break
    sum_ = to_plus + to_minus + 1
    for i2 in range(0, to_plus + 1):
        matrix[i + i2][j][0] = sum_
    for i2 in range(0, to_minus + 1):
        matrix[i - i2][j][0] = sum_
    return matrix

def search_x(i, j, matrix):
    """i, j について，y方向を埋める
    """
    to_plus = 0
    to_minus = 0
    while(True):
        to_plus += 1
        if (matrix[i][j + to_plus][1] == 0):
            continue
        else:
            to_plus -= 1
            break
    while(True):
        to_minus += 1
        if (matrix[i][j - to_minus][1] == 0):
            continue
        else:
            to_minus -= 1
            break
    sum_ = to_plus + to_minus + 1
    for i2 in range(0, to_plus + 1):
        matrix[i][j + i2][1] = sum_
    for i2 in range(0, to_minus + 1):
        matrix[i][j - i2][1] = sum_
    return matrix

def main():
    H, W = map(int, input().split())
    matrix = []
    for i in range(0, H + 2):
        lines = []
        for j in range(0, W + 2):
            lines.append([-1, -1])
        matrix.append(lines)

    for i in range(1, H + 1):
        string = input()
        for j in range(1, W + 1):
            if string[j - 1] == "#":
                continue
            else:
                matrix[i][j] = [0, 0]

    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if (matrix[i][j][0] == 0):
                # y方向を埋める
                matrix = search_y(i, j, matrix)
            if (matrix[i][j][1] == 0):
                # x方向を埋める
                matrix = search_x(i, j, matrix)
    # print(matrix)
    
    max_sum = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            max_sum = max(matrix[i][j][0] + matrix[i][j][1], max_sum)
    print(max_sum - 1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

hhs = [[] for _ in range(H)]
for i in range(H):
    #print(i)
    j = 0
    #hhs[i] = []
    while j < W:
        if s[i][j] == '#':
            hhs[i].append(-1)
            j += 1
        else:
            if '#' in s[i][j:]:
                l = s[i][j:].index('#')
                #print(l)
                for _ in range(l):
                    hhs[i].append(l)
                j += l
            else:
                l = len(s[i][j:])
                #print('l:',l)
                for _ in range(l):
                    hhs[i].append(l)
                break
wws = [[] for _ in range(W)]
for j in range(W):
    ins = ''
    for i in range(H):
        news = ins + s[i][j]
        ins = news
    k = 0
    while k < H:
        if ins[k] == '#':
            wws[j].append(-1)
            k += 1
        else:
            if '#' in ins[k:]:
                l = ins[k:].index('#')
                #print(l)
                for _ in range(l):
                    wws[j].append(l)
                k += l
            else:
                l = len(ins[k:])
                for _ in range(l):
                    wws[j].append(l)
                break
g = -1
for i in range(H):
    for j in range(W):
        gh = hhs[i][j]
        gw = wws[j][i]
        if gh>0 and gw>0:
            g = max(g,gh+gw-1)
print(g)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = []
for y in range(h):
    s = input()
    line = []
    for x in range(len(s)):
        if s[x] == '#':
            line.append([-1, -1, 1])
        else:
            line.append([-1, -1, 0])
    a.append(line)

# Xスコア計算
for y in range(h):
    start = -1
    end = -1
    count = 0
    for x in range(w):
        if a[y][x][2] == 1 or x == w - 1:
            end = x
            if x == w - 1 and a[y][x][2] != 1:
                end  = end + 1
                count = count + 1
            for u in range(start, end):
                a[y][u][0] = count
            start = -1
            count = 0
        else:
            count = count + 1
        if start == -1:
            start = x

ans = 0

# yスコア計算
for x in range(w):
    start = -1
    end = -1
    count = 0
    for y in range(h):
        if a[y][x][2] == 1 or y == h - 1:
            end = y
            if y == h - 1 and a[y][x][2] != 1:
                end  = end + 1
                count = count + 1
            for u in range(start, end):
                a[u][x][1] = count
                # スコア計算
                if a[u][x][2] != 1:
                    score = a[u][x][0] + a[u][x][1]
                    ans = max(score, ans)
            start = -1
            count = 0
        else:
            count = count + 1
        if start == -1:
            start = y
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

val = list(map(int, input().strip().split()))
width = val[1]
height = val[0]

walls = np.zeros((height, width))

for y in range(height):
    val = input().strip()
    for x in range(width):
        walls[y, x] = 1 if val[x] == '#' else 0

left = np.zeros((height, width))
right = np.zeros((height, width))
up = np.zeros((height, width))
down = np.zeros((height, width))

# left
for y in range(height):
    cache = 0
    for x in range(width):
        if walls[y, x] == 1:
            cache = x + 1
            left[y, x] = 100000
        else:
            left[y, x] = cache

# right
for y in range(height):
    cache = 0
    for x in range(width - 1, -1, -1):
        if walls[y, x] == 1:
            cache = width - x
        else:
            right[y, x] = cache

# up
for x in range(width):
    cache = 0
    for y in range(height):
        if walls[y, x] == 1:
            cache = y + 1
        else:
            up[y, x] = cache

# down
for x in range(width):
    cache = 0
    for y in range(height - 1, -1, -1):
        if walls[y, x] == 1:
            cache = height - y
        else:
            down[y, x] = cache

all = left + right + up + down
print(int(width + height - np.amin(all) - 1))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            cnt = 1 # 光の数 自分も含む

            flg = True
            k = 1
            while flg:
                if i-k < 0:
                    flg = False
                    break
                else:
                    if S[i-k][j] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if j-k < 0:
                    flg = False
                    break
                else:
                    if S[i][j-k] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if i+k >= H:
                    flg = False
                    break
                else:
                    if S[i+k][j] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if j+k >= W:
                    flg = False
                    break
                else:
                    if S[i][j+k] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            ans = max(cnt, ans)

# print(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
nl = lambda: list(map(int, input().split()))
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())

yokos = np.zeros((H, W), dtype=np.uint64)
for row in range(H):
    count = 0
    prev = 0
    for col in range(W):
        if grid[row][col] == '.':
            count += 1
        else:
            yokos[row, prev:col] = count
            prev = col+1
            count = 0
    if count > 0:
        yokos[row, prev:W] = count

tates = np.zeros((H, W), dtype=np.uint64)
for col in range(W):
    count = 0
    prev = 0
    for row in range(H):
        if grid[row][col] == '.':
            count += 1
        else:
            tates[prev:row, col] = count
            prev = row+1
            count = 0
    if count > 0:
        tates[prev:H, col] = count

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, yokos[row, col] + tates[row, col] - 1)

print(int(res))

Submission status: Time Limit Exceeded

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

l = [0]*(w*h)
#u = [0]*(w*h)

for i in range(h):
  k = 0 
  for j in range(w):
    if s[i][j] == "#":
      k = 0 
    else:
      k += 1
    l[i*w+j] = k
#print(l)      
for i in range(h):
  k = 0
  for j in range(w):
    if s[i][(w-1)-j] == "#":
      k = 0
    else:
      k += 1
    l[i*w+(w-1)-j] += k

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

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

print(max(l)-3)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W = IL()
grid = [[i for i in S()] for i in range(H)]
cntH = [[0 for i in range(W)] for i in range(H)]
cntW = [[0 for i in range(W)] for i in range(H)]

for h in range(H):
  cnt = 0
  for w in range(W):
    if grid[h][w] == "#":
      cnt = 0
    else:
      cnt += 1
      cntW[h][w] = cnt

for h in range(H-1,-1,-1):
  cnt = 0
  for w in range(W-1,-1,-1):
    if grid[h][w] == "#":
      cnt = 0
    elif cnt == 0:
      cnt = cntW[h][w]
    else:
      cntW[h][w] = cnt

for w in range(W):
  cnt = 0
  for h in range(H):
    if grid[h][w] == "#":
      cnt = 0
    else:
      cnt += 1
      cntH[h][w] = cnt

for w in range(W-1,-1,-1):
  cnt = 0
  for h in range(H-1,-1,-1):
    if grid[h][w] == "#":
      cnt = 0
    elif cnt == 0:
      cnt = cntH[h][w]
    else:
      cntH[h][w] = cnt

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(ans,cntW[h][w]+cntH[h][w])

print(ans-1)

Submission status: Time Limit Exceeded

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

S_t = list(map(list, zip(*S)))

S_h = [[] for i in range(H)]
S_w = [[] for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h[y].append(x)
            S_w[x].append(y)

S_hh = [[0]*(W+1) for i in range(H)]
S_ww = [[0]*(H+1) for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_hh[y][x] = 1
            S_ww[x][y] = 1
        S_hh[y][x] += S_hh[y][x-1]
        S_ww[x][y] += S_ww[x][y-1]

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            c = 1
            if len(S_w[x]) == 0:
                c += H-1
            else:
                i = S_ww[x][y]
                if i == 0:
                    c += S_w[x][0]-1
                elif i == len(S_w[x]):
                    c += H-S_w[x][-1]-2
                else:
                    c += S_w[x][i]-S_w[x][i-1]-2
            if len(S_h[y]) == 0:
                c += W-1
            else:
                i = S_hh[y][x]
                if i == 0:
                    c += S_h[y][0]-1
                elif i == len(S_h[y]):
                    c += W-S_h[y][-1]-2
                else:
                    c += S_h[y][i]-S_h[y][i-1]-2
            ans = max(ans,c)

print(ans)

Submission status: Time Limit Exceeded

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


def yoko(y, x):
    ret1 = 0
    xx = x
    while xx + 1 <= W - 1 and S[y][xx + 1] != '#':
        ret1 += 1
        xx += 1
    xxx = x
    ret2 = 0
    while 0 <= xxx - 1 and S[y][xxx - 1] != '#':
        ret2 += 1
        xxx -= 1
    ret3 = ret1 + ret2
    return ret3


def tate(y, x):
    ret1 = 0
    yy = y
    while 0 <= yy - 1 and S[yy - 1][x] != '#':
        ret1 += 1
        yy -= 1
    yyy = y
    ret2 = 0
    while yyy + 1 <= H - 1 and S[yyy + 1][x] != '#':
        ret2 += 1
        yyy += 1
    ret3 = ret1 + ret2
    for i in range(yy, yyy + 1):
        S[i][x] = ret3
    return ret3


ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        elif S[y][x] != '.':
            T = S[y][x]
        else:
            T = tate(y, x)
            Y = yoko(y, x)
        ans = max(ans, T + Y)
print(ans + 1)

Submission status: Time Limit Exceeded

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

s = [[i for i in list(str(input()))] for i in range(h)]

board_w = [[0 for i in range(w)] for i in range(h)]
board_h = [[0 for i in range(h)] for i in range(w)]

# 横、縦の順に走査
for i in range(h):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == w - 1:
            for k in range(cnt_continue):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0

s = list(map(list, zip(*s)))

for i in range(w):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0
        if j == h - 1:
            for k in range(cnt_continue):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0

board_h = list(map(list, zip(*board_h)))
ans = 0

for i in range(h):
    for j in range(w):
        v = int(board_w[i][j]) + int(board_h[i][j])
        ans = max(ans, v)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
s=[input() for i in range(h)]
max_s = 0
for y in range(h):
    for x in range(w):
        if s[y][x] == "#":
            continue
        above = 0
        left = 0
        right = 0
        bottom = 0
        for i in reversed(range(0,y)):
            if s[i][x] == "#":
                break
            else:
                above += 1
        for i in range(y, h):
            if s[i][x] == "#":
                break
            else:
                bottom += 1
        for i in reversed(range(0,x)):
            if s[y][i] == "#":
                break
            else:
                left += 1
        for i in range(x, w):
            if s[y][i] == "#":
                break
            else:
                right += 1
        current_sum = above + left + right + bottom -1
        if current_sum > max_s:
            max_s = current_sum
print(max_s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def cal(S, xx):
    S1 = []
    for s in S:
        s2  = "".join(s)
        indexes = [i for i, x in enumerate(s) if x == "#"]
        indexes.append(xx+1)
        li3 = [len(ss) for ss in s2.split("#")]
        
        cnt = 0
        ret = []
        b_index = 0
        for index in indexes:
            if cnt == 0:
                ret.extend( [li3[cnt] for _ in range(index-b_index)])
            else:
                ret.extend( [li3[cnt] for _ in range(index-b_index-1)])
            ret.append(0)
            b_index = index
            cnt += 1
        ret.pop()
        ret.pop()
        S1.append(ret)
    return np.array(S1)

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

S = []
for i in range(H):
    S.append(list(input()))
    
A = np.array(S)
B = A.T

S1 = cal(A, W)
S2 = cal(B, H)

XX = S1 + S2.T
print(np.max(XX) - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
data=[list(input()) for i in range(h)]
map1=[[0]*w for i in range(h)]
map2=[[0]*w for i in range(h)]
for i in range(h):
  count=0
  for j in range(w):
    if data[i][j]=="#":
      count=0
    else:
      count+=1
      map1[i][j]=count
  count=0
  for j in range(w):
    if map1[i][-1-j]==0:
      count=0
    else:
      if count==0:count=map1[i][-1-j]
      map1[i][-1-j]=count
for i in range(w):
  count=0
  for j in range(h):
    if data[j][i]=="#":
      count=0
    else:
      count+=1
      map2[j][i]=count
  count=0
  for j in range(h):
    if map2[-j-1][i]==0:
      count=0
    else:
      count=max(map2[-j-1][i],count)
      map2[-j-1][i]=count
ans=0
for i in range(h):
  for j in range(w):
    tmp=map1[i][j]+map2[i][j]
    ans=max(ans,tmp)
print(ans-1)