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 numpy as np
H, W = map(int, input().split())
S = []
ij = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for i in range(H):
    S.append(input())
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ij[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ij[start:end+1, j] += cnt
            cnt = 0

ij = ij - 1  # 自分が2回足されるので、1引く
ans = ij.max()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
map = [list('#' + input() + '#') for j in range(H)]
map.insert(0,['#' for i in range(W + 2)])
map.append(['#' for i in range(W + 2)])


def f(i,j):
    ret = 0
    for x, y in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
        k = 0
        while map[i + x * k][j + y * k] == '.':
            k += 1
        ret += k
    ret -= 3
    return ret

ans = 0
for i, line in enumerate(map):
    for j, dot in enumerate(line):
        if dot == '.':
            ans = max(ans, f(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

H, W = map(int, input().split())
F = [input() for _ in range(H)]
FH = [[0]*W for _ in range(H)]
FV = [[0]*W for _ in range(H)]


def search(x, y, c, d):
    if not (0 <= x < H and 0 <= y < W):
        return c
    if F[x][y] == "#":
        return c
    else:
        if d == "h":
            return search(x, y+1, c+1, "h")
        else:
            return search(x+1, y, c+1, "v")

ans = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == "#":
            FH[i][j] = 0
        elif F[i][j] == ".":
            if FH[i][j-1] > 0:
                FH[i][j] = FH[i][j-1]
            else:
                FH[i][j] = search(i, j+1, 1, "h")

ans = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == "#":
            FV[i][j] = 0
        elif F[i][j] == ".":
            if FV[i-1][j] > 0:
                FV[i][j] = FV[i-1][j]
            else:
                FV[i][j] = search(i+1, j, 1, "v")

        if FH[i][j] + FV[i][j] > ans:
            ans = FH[i][j] + FV[i][j]

if ans >= 2:
    print(ans-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

countL2R = [[0 for i in range(w)] for j in range(h)]
countR2L = [[0 for i in range(w)] for j in range(h)]
countU2D = [[0 for i in range(w)] for j in range(h)]
countD2U = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            countL2R[i][j] = -1
            countR2L[i][j] = -1
            countU2D[i][j] = -1
            countD2U[i][j] = -1

for i in range(h):
    for j in range(w):
        if j > 0 and countL2R[i][j] != -1:
                countL2R[i][j] = countL2R[i][j - 1] + 1

        j = w - j - 1
        if j < w - 1 and countR2L[i][j] != -1:
            countR2L[i][j] = countR2L[i][j + 1] + 1

        if i > 0 and countU2D[i][j] != -1:
            countU2D[i][j] = countU2D[i - 1][j] + 1

        I = i
        i = h - i - 1
        if i < h - 1 and countD2U[i][j] != -1:
            countD2U[i][j] = countD2U[i + 1][j] + 1
        i = I

ans = 0
for i in range(h):
    for j in range(w):
        if countD2U[i][j] != -1:
            ans = max(ans, countD2U[i][j] + countU2D[i][j] + countR2L[i][j] + countL2R[i][j])

print(ans + 1)

Submission status: Time Limit Exceeded

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

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

for j, chara in enumerate(S):
    for index, char in enumerate(chara):
        S_2[index][j] = char

Ans = []
for index, char in enumerate(S):
    tmp = 0
    stepper = 0
    a = []
    for i in char:
        if i == "#" and tmp == 0:
            a.append(0)
        elif i == "." and tmp == 0:
            tmp = 1
            stepper += 1
        elif i == "." and tmp == 1:
            stepper += 1

        elif i == "#" and tmp == 1:
            tmp = 0
            for j in range(stepper):
                a.append(stepper)
            stepper = 0
            a.append(0)
    if stepper > 0:
        for j in range(stepper):
            a.append(stepper)
    Ans.append(a)

Ans2 = []
for index, char in enumerate(S_2):
    tmp = 0
    stepper = 0
    a = []
    for i in char:
        if i == "#" and tmp == 0:
            a.append(0)
        elif i == "." and tmp == 0:
            tmp = 1
            stepper += 1
        elif i == "." and tmp == 1:
            stepper += 1

        elif i == "#" and tmp == 1:
            tmp = 0
            for j in range(stepper):
                a.append(stepper)
            stepper = 0
            a.append(0)
    if stepper > 0:
        for j in range(stepper):
            a.append(stepper)
    Ans2.append(a)

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

for j, chara in enumerate(Ans2):
    for index, char in enumerate(chara):
        S3[index][j] = char

maxNum = 0
for i in range(H):
    for j in range(W):
        mx = Ans[i][j] + S3[i][j]
        if mx > maxNum:
            maxNum = mx

print(maxNum-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
[H,W] = list(map(int,input().split()))

S =[]
while True:
    try:
        S.append(list(input()))
    except:
        break;

yoko = np.zeros((H,W))
tate = np.zeros((H,W))

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

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

out = tate + yoko
print(int(np.max(out)-1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def show(s,H):
    for h in range(H):
        print(s[h])

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

s_str = [['.'] * W for i in range(H)]
s = [[1] * W for i in range(H)]
for i in range(H):
    s_str[i] = list(input())

for h in range(H):
    for w in range(W):
        if s_str[h][w] == '#':
            s[h][w] = -1

#show(s,H)

a0 = [[0] * W for i in range(H)]
a1 = [[0] * W for i in range(H)]
a2 = [[0] * W for i in range(H)]
a3 = [[0] * W for i in range(H)]

#0:左
#1:右
#2:上
#3:下


for h in range(H):
    for w in range(W):
        if s[h][w] > 0:

            if w > 0:
                a0[h][w] = a0[h][w-1] + max(0,s[h][w-1])

            if h > 0:
                a2[h][w] = a2[h-1][w] + max(0,s[h-1][w])



for h in reversed(range(H)):
    for w in reversed(range(W)):
        if s[h][w] > 0:

            if w < (W - 1):
                a1[h][w] = a1[h][w+1] + max(0,s[h][w+1])

            if h < (H - 1):
                a3[h][w] = a3[h+1][w] + max(0,s[h+1][w])

            #show(a1,H)


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

for h in range(H):
    for w in range(W):
        if s[h][w] > 0:
            ans[h][w] = a0[h][w] + a1[h][w] + a2[h][w] + a3[h][w]
#print('---')
#show(ans,H)
print(np.max(ans) + 1)

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=0 if 1 in A else 1
for i in range(2, N+1):
        if i in A: dp[i] = 0
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])
"""
def genArr2(h,w):
        return [0]*(h*w)
def setArr2(A,i,j,x):
        A[i*W + j] = x
def getArr2(A,i,j):
        return A[i*W + j]
H,W=map(int, input().split())
S=genArr2(H,W)
for i in range(H):
        s=input()
        l=list(s)
        for j in range(W):
                setArr2(S,i,j,l[j])

SWR=genArr2(H,W)
for i in range(H):
        setArr2(SWR, i, 0, 0 if getArr2(S, i, 0) == "#" else 1)
        for j in range(1,W):
                if getArr2(S, i, j) == "#": setArr2(SWR, i, j, 0)
                else: setArr2(SWR, i, j, getArr2(SWR, i, j-1) + 1)
SWL=genArr2(H,W)
for i in range(H):
        setArr2(SWL, i, W-1, 0 if getArr2(S, i, W-1) == "#" else 1)
        for j in range(W-2,-1,-1):
                if getArr2(S, i, j) == "#": setArr2(SWL, i, j, 0)
                else: setArr2(SWL, i, j, getArr2(SWL, i, j+1) + 1)
SHB=genArr2(H,W)
for j in range(W):
        setArr2(SHB, 0, j, 0 if getArr2(S, 0, j) == "#" else 1)
        for i in range(1,H):
                if getArr2(S, i, j) == "#": setArr2(SHB, i, j, 0)
                else: setArr2(SHB, i, j, getArr2(SHB, i-1, j) + 1)
SHT=genArr2(H,W)
for j in range(W):
        setArr2(SHT, H-1, j, 0 if getArr2(S, H-1, j) == "#" else 1)
        for i in range(H-2, -1, -1):
                if getArr2(S, i, j) == "#": setArr2(SHT, i, j, 0)
                else: setArr2(SHT, i, j, getArr2(SHT, i+1, j) + 1)

ans=0
for i in range(H):
        for j in range(W):
                x=getArr2(SWR, i, j) + getArr2(SWL, i, j) + getArr2(SHB, i, j) + getArr2(SHT,i,j) - 3
                ans=max(ans,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [input() for _ in range(h)]
a = [[None] * w for _ in range(h)]
for i in range(h):
    p = 0
    while p < w:
        j = p
        while j < w and s[i][j] == '.':
            j += 1
        for k in range(p, j):
            a[i][k] = j - p
        p = j + 1
r = 0
for j in range(w):
    p = 0
    while p < h:
        i = p
        while i < h and s[i][j] == '.':
            i += 1
        for k in range(p, i):
            r = max(r, a[k][j] + i - p - 1)
        p = i + 1

print(r)

Submission status: Time Limit Exceeded

Solution code:
import time
from itertools import groupby
dbg = False
h, w = map(int, input().split())
maze = []
for hh in range(h):
  row = list(input())
  maze.append(row)
hscore = []

t = time.time()

for hh in range(h):
  hrow = []
  for key, group in groupby(maze[hh]):
    n = len((list(group)))
    if key == '.':
      hrow += [n] * n
    else:
      hrow += [0] * n
  hscore.append(hrow)

# transpose
if dbg:
  print('hscore done')
  print(time.time() - t)
  t = time.time()
maze_t = list(map(list, zip(*maze)))
vscore = []

h, w = w, h

for hh in range(h):
  hrow = []
  for key, group in groupby(maze_t[hh]):
    n = len((list(group)))
    if key == '.':
      hrow += [n] * n
    else:
      hrow += [0] * n
  vscore.append(hrow)

vscore = list(map(list, zip(*vscore)))
if dbg:
  print('vscore done')
  print(time.time() - t)
  t = time.time()

h, w = w, h

max_score = 0
for hh in range(h):
  score = max([x + y - 1 for x, y in zip(hscore[hh], vscore[hh])])
  max_score = max([max_score, score])

print(max_score)

if dbg:
  print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
s = np.zeros((H, W), np.int64)


def conv(c):
    if c == '#':
        return -1
    else:
        return 0


for i in range(H):
    l = input()
    for j in range(W):
        s[i][j] = conv(l[j])

s1 = np.zeros((H, W), np.int64)
for i in range(H):
    n = 0
    prev = 0
    for j in range(W):
        if s[i][j] == -1:
            if prev != j:
                s1[i][prev:j] = n
            n = 0
            prev = j+1
        else:
            n += 1
    if n != 0:
        if prev != W:
            s1[i][prev:W] = n

s2 = np.zeros((W, H), np.int64)
for i in range(W):
    n = 0
    prev = 0
    for j in range(H):
        if s[j][i] == -1:
            if prev != j:
                s2[i][prev:j] = n
            n = 0
            prev = j+1
        else:
            n += 1
    if n != 0:
        if prev != H:
            s2[i][prev:H] = n

s_sum = s1 + s2.T
ans = np.amax(s_sum) - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def numset(a):
    li = []
    preS = - 1
    for i, v in enumerate(a):
        if v == "#":
            li.append(0)
            preS = i
        else:
            hoge = a[i:].find("#")
            if hoge > 0:
                li.append(hoge+i-(preS+1))
            else:
                li.append(len(a)-(preS+1))
    return li

H, W = map(int, input().split())
S = [input() for i in range(H)]
xs = [numset(i) for i in S]

xy = []
for i in range(W):
  stt = ''
  for j in range(H):
    stt += S[j][i]
  xy.append(numset(stt)) 
#print(xy)

ans = 0
for i in range(W):
  for j in range(H):
    aa = xs[j][i] + xy[i][j] -1
    if aa > ans:
      ans = aa
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

import sys

def getspan(s,now,n):
    i= now + s[now:].find(".")
    if i<now: return None
    #
    j= i + s[i:].find("#")
    if j<i: return [i,n]
    else: return [i,j]
#
h,w = [ int(x) for x in sys.stdin.readline().split() ]

masu = [ ["" for _ in range(w)] for _ in range(h)  ]
#
for i in range(h):
    row = sys.stdin.readline()
    for j in range(w): masu[i][j]= row[j]
#
rows= [ "" ] * h
for i in range(h): rows[i]= "".join( masu[i][0:w] )
cols= [ "" ] * w
for j in range(w):
    for i in range(h): cols[j]+= masu[i][j]
#
maxval= 0
i= 0
colspan= [ [-1,-1,0] for _ in range(w) ]
while i<h:
    for j in range(w):
        if colspan[j][1]>i: continue
        span= getspan( cols[j],i,h )
        if not span: colspan[j]= [-1,h+1,0]
        else:
            k,l = span
            colspan[j]= [k,l,l-k]
    #
    j= 0
    while j<w:
        span = getspan( rows[i],j,w )
        if not span: break
        k,l = span
        #
        tmp1= l-k
        tmp2= 1
        for m in range(k,l):
            if colspan[m][0]>i: continue
            t= colspan[m][2]
            if t>tmp2: tmp2= t
        #
        tm = tmp1 + tmp2 - 1
        if tm>maxval: maxval= tm
        j= l
    #
    i+=1
print( maxval )

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
n, m = map(int, input().split())
mat = sys.stdin.readlines()
# print(mat)

arr = np.array([[0] * m] * n)
brr = np.array([[0] * n] * m)
# print(arr)

for i in range(n):
  l = 0
  r = 0
  count = 0
  for j in range(m):
    if mat[i][j] == "#":
      arr[i][l:r+1] = count
      count = 0
      l = j + 1
    else:
      count += 1
      r = j
  arr[i][l:r+1] = count

for j in range(m):
  l = 0
  r = 0
  count = 0
  for i in range(n):
    if mat[i][j] == "#":
      brr[j][l:r+1] = count
      count = 0
      l = i + 1
    else:
      count += 1
      r = i
  brr[j][l:r+1] = count

print((arr + brr.T).max() - 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    h, w = im.inputMultiple()
    s = []
    for _ in range(h):
        s.append(line_to_int(im.inputSingle(dtype=str)))
    # Logic ############################################################################################################
        vertical = [[-1] * h for _ in range(w)]
    horizontal = [[-1] * w for _ in range(h)]
    # Vertical
    for x in range(w):
        temp_y = 0
        for y in range(h):
            if s[y][x] == 0:
                if y > temp_y:
                    vertical[x][temp_y:y] = [y - temp_y] * (y - temp_y)
                temp_y = y + 1
                continue
            if y == h - 1:
                vertical[x][temp_y:y] = [y - temp_y + 1] * (y - temp_y + 1)
    # Horizontal
    for y in range(h):
        temp_x = 0
        for x in range(w):
            if s[y][x] == 0:
                if x > temp_x:
                    horizontal[y][temp_x:x] = [x - temp_x] * (x - temp_x)
                temp_x = x + 1
                continue
            if x == w - 1:
                horizontal[y][temp_x:x] = [x - temp_x + 1] * (x - temp_x + 1)
    maxim = 0
    for y in range(h):
        for x in range(w):
            if (vertical[x][y] + horizontal[y][x]  - 1) > maxim:
                maxim = vertical[x][y] + horizontal[y][x] - 1
    # Output ###########################################################################################################
    print(maxim)
    # Return ###########################################################################################################
    return

def line_to_int(line):
    line_int = []
    for idx in range(len(line)):
        if line[idx] == '#':
            line_int.append(0)
        else:
            line_int.append(1)
    return line_int

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Time Limit Exceeded

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys
from pprint import pprint

WARU = 1000000007

H, W = [ int(x) for x in input().split() ]
S = []
for _i in range(H):
    S.append(input())

def key(h,w):
    return "{}:{}".format(h,w)

ans = [ [] for x in range(H)] # right,under
for h in range(H):
    ans[h] = [ [0,0] for x in range(W) ]

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        right = 0
        under = 0
        if w == 0:
            right = 1
        else:
            right = ans[h][w-1][0] + 1
        if h == 0:
            under = 1
        else:
            under = ans[h-1][w][1] + 1
        ans[h][w] = [right,under]

ans2 = [ [] for x in range(H)] # right,under
for h in range(H):
    ans2[h] = [ [0,0] for x in range(W) ]


for h in range(H-1,-1,-1):
    for w in range(W-1,-1,-1):
        if S[h][w] == "#":
            continue
        right = 0
        under = 0
        if w == W - 1:
            right = 1
        else:
            right = ans2[h][w+1][0] + 1
        if h == H - 1:
            under = 1
        else:
            under = ans2[h+1][w][1] + 1
        ans2[h][w] = [right,under]

max_mass = 0
max_count = 0

ans3 = [ [] for x in range(H)] # right,under
for h in range(H):
    ans3[h] = [ [0,0] for x in range(W) ]


for h in range(H):
    for w in range(W):
        ans3[h][w] = ans[h][w][0] + ans[h][w][1] + ans2[h][w][0] + ans2[h][w][1]


max = 0
for h in range(H):
    for w in range(W):
        if max < ans3[h][w]:
            max = ans3[h][w]
print (max - 3)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int, input().split())  #複数数値入力

list_s = []
for i in range(h):
    list_s.append([0 if x=='.' else 1 for x in input()])
    
arr_s = np.array(list_s)

list_rows = []
for y in range(h):
    list_target = arr_s[y,:]
    l = []
    tmp = 0

    for i,x in enumerate(list_target):
        if list_target[i] == 0:
            tmp += 1
        else:
            l += [tmp for _ in range(tmp)] + [0]
            tmp = 0
    l += [tmp for _ in range(tmp)]
    
    list_rows.append(l)
    
arr_rows = np.array(list_rows)

list_cols = []
for x in range(w):
    list_target = arr_s[:,x]
    l = []
    tmp = 0

    for i,x in enumerate(list_target):
        if list_target[i] == 0:
            tmp += 1
        else:
            l += [tmp for _ in range(tmp)] + [0]
            tmp = 0
    l += [tmp for _ in range(tmp)]
    
    list_cols.append(l)
    
arr_cols = np.array(list_cols).T

print((arr_rows + arr_cols).max()-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H ,W = map(lambda x: int(x),input().split())

x = np.zeros((H,W))
room = np.zeros((H,W))


for i in range(H):
    #a  = list(range(H))
    b = np.array(list(map(lambda x:int(x),list(input().replace('.', '1').replace('#', "0")))))
    x[i]=b

for i in range(H):
    tmp = []
    #print(np.where(x[i]==1)[0])
    for j in np.where(x[i]==1)[0]:
        #print(j)
        if len(tmp)==0:
            tmp.append(j)
            continue
        if j-tmp[-1]>1:
            #print(tmp)
            for t in tmp:
                room[i][t] += len(tmp)
            tmp=[j]
        else:
            tmp.append(j)
    if len(tmp)>0:
        for t in tmp:
                room[i][t] += len(tmp)
        tmp=[]

#print(room)

x=x.T
room=room.T

#print(room)
#print(x)

for i in range(W):
    tmp = []
    #print(np.where(x[i]==1)[0])
    for j in np.where(x[i]==1)[0]:
        #print(j)
        if len(tmp)==0:
            tmp.append(j)
            continue
        if j-tmp[-1]>1:
            #print(tmp)
            for t in tmp:
                room[i][t] += len(tmp)
            tmp=[j]
        else:
            tmp.append(j)
    if len(tmp)>0:
        for t in tmp:
                room[i][t] += len(tmp)
        tmp=[]

#print(room)
print(int(room.max())-1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
l = []
for i in range(n):
    a = input()
    a.split()
    l.append(a)
def f(x,y):
    global l ,n,m
    ans = -3
    if l[x][y] == "#":
        return 0
    else :
        for i in range(x,n):
            if l[i][y] == ".":
                ans += 1
            else :
                break
        for i in range(x+1):
            if l[x-i][y] == ".":
                ans += 1
            else :
                break
        for i in range(y,m):
            if l[x][i] == ".":
                ans += 1
            else :
                break
        for i in range(y+1):
            if l[x][y-i] == ".":
                ans += 1
            else:
                break
        return ans
k = 1
for i in range(n):
    for j in range(m):
        k = max(k,f(i,j))
print(k)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
#print(S)
ans = 0
for i in range(H):
    cou = 0
    l = 0
    ws = [0]*W
    for j in range(W):
        #print(i,j,S[i][j])
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    Grid1[i] = ws

for i in range(W):
    cou = 0
    l = 0
    ws = [0]*H
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    for j in range(H):
        ans =max(Grid1[j][i] +ws[j], ans)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

l = np.zeros((h,w))

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

print(int(l.max()+0.1)-3)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
l = [0] * W
L = [l] * H
for i in range(H):
	l = [0] * W
	s = list(input())
	count = 0
	for j in range(W):
		if s[j] == '#':
			for k in range(count):
				l[j - k - 1] += count
			count = 0
		else:
			count += 1
	for k in range(count):
		l[W - k - 1] += count			
	L[i] = l
for i in range(W):
	count = 0
	for j in range(H):
		if L[j][i] == 0:
			for k in range(count):
				L[j - k - 1][i] += count
			count = 0
		else:
			count += 1
	for k in range(count):
		L[H - k - 1][i] += count			
ans = 0
for i in range(H):
	ans = max(max(L[i]) - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for i in range(H)]
distW = [[0 for j in range(W)] for i in range(H)]
distH = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    j = 0
    while j < W:
        if S[i][j]==".":
            dj = 1
            for nj in range(1, W+1):
                if j+nj == W or S[i][j+nj] == "#":
                    for nnj in range(nj):
                        dj = nj
                        distW[i][j+nnj] = nj
                    break
            j += dj
        elif S[i][j]=="#":
            distW[i][j] = 0
            j+=1

for j in range(W):
    i = 0
    while i < H:
        if S[i][j]==".":
            di = 1
            for ni in range(1, H+1):
                if i+ni == H or S[i+ni][j] == "#":
                    di = ni
                    for nni in range(ni):
                        distH[i+nni][j] = ni
                    break
            i += di
        elif S[i][j]=="#":
            distH[i][j] = 0
            i+=1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = []
for i in range(H):
    S += [['#'] + list(input()) + ['#']]
S = [['#' for i in range(W+2)]] + S + [['#' for i in range(W+2)]]

ans,v = 0,[0 for i in range(W)]
for i in range(1,W+1):
    k = 1
    while S[k][i] == '.':
        k += 1
    v[i-1] = k - 1

for i in range(1,H+1):
    j,dot = 1,0
    while j < W+1:
        while S[i][j] == '.':
                dot += 1
                j += 1
        for k in range(j-dot,j):
            if ans < dot + v[k-1]:    ans = dot + v[k-1]

        dot = 0
        k = i+1
        if j < W+1:
            while S[k][j] == '.':
                k += 1
            v[j-1] = k - i - 1
            j += 1 
print(ans-1)

Submission status: Time Limit Exceeded

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

s = []

for i in range(h):
    s.append(input())

_h = [[0 for i in range(w)] for j in range(h)]
_w = [[0 for i in range(w)] for j in range(h)]
_h2 = [[0 for i in range(w)] for j in range(h)]
_w2 = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    _h[i][0] = 1 if s[i][0] == "." else 0

for i in range(w):
    _w[0][i] = 1 if s[0][i] == "." else 0

for i in range(h):
    for j in range(1, w):
        _h[i][j] = _h[i][j - 1] + 1 if s[i][j] == "." else 0

for i in range(1, h):
    for j in range(w):
        _w[i][j] = _w[i - 1][j] + 1 if s[i][j] == "." else 0

for i in range(h):
    _h2[i][w - 1] = 1 if s[i][w - 1] == "." else 0

for i in range(w):
    _w2[h - 1][i] = 1 if s[h - 1][i] == "." else 0

for i in range(h):
    for j in range(w - 2, -1, -1):
        _h2[i][j] = _h2[i][j + 1] + 1 if s[i][j] == "." else 0

for i in range(h - 2, -1, -1):
    for j in range(w):
        _w2[i][j] = _w2[i + 1][j] + 1 if s[i][j] == "." else 0

maximum = 0

for i in range(h):
    for j in range(w):
        ans = _h[i][j] + _h2[i][j] + _w[i][j] + _w2[i][j] - 3
        if ans >= maximum:
            maximum = ans

print(maximum)