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:
#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache

input = stdin.readline
setrecursionlimit(10000)

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

#variable

#function
@lru_cache(maxsize=None)
def L(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == 1:
            return 1
        else:
            return L(i,j-1) + 1

@lru_cache(maxsize=None)
def R(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if j == W:
            return 1
        else:
            return R(i,j+1) + 1

@lru_cache(maxsize=None)
def U(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == 1:
            return 1
        else:
            return U(i-1,j) + 1

@lru_cache(maxsize=None)
def D(i,j):
    if S[i-1][j-1] == "#":
        return 0
    elif S[i-1][j-1] == ".":
        if i == H:
            return 1
        else:
            return D(i+1,j) + 1

#class

#main function
def main():
    maxScore = 0
    for i in range(1,H+1):
        for j in range(1,W+1):
            score = L(i,j)+R(i,j)+U(i,j)+D(i,j)-3
            if score > maxScore:
                maxScore = score
    print(maxScore)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
decoder = lambda x: True if x == "#" else False

def main():
  H, W = list(map(int, input().split()))
  Map = [list(map(decoder, list(input()))) for i in range(H)]
  
  U = [[0] * W for i in range(H)]
  D = [[0] * W for i in range(H)]
  L = [[0] * W for i in range(H)]
  R = [[0] * W for i in range(H)]
  for w in range(W):
    count = 0
    for h in range(H):
      if Map[h][w]:
        count = 0
      else:
        count += 1
      U[h][w] = count
    count = 0
    for h in range(H-1, -1, -1):
      if Map[h][w]:
        count = 0
      else:
        count += 1
      D[h][w] = count
  
  for h in range(H):
    count = 0
    for w in range(W):
      if Map[h][w]:
        count = 0
      else:
        count += 1
      L[h][w] = count
    count = 0
    for w in range(W-1, -1, -1):
      if Map[h][w]:
        count = 0
      else:
        count += 1
      R[h][w] = count
  
  max_change = 0
  for h in range(H):
    for w in range(W):
      change = U[h][w] + D[h][w] + L[h][w] + R[h][w] - 3
      max_change = max(max_change, change)
        
  print(max_change)
  
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
decoder = lambda x: False if x == "#" else True

def main():
  H, W = list(map(int, input().split()))
  Map = [list(map(decoder, list(input()))) for i in range(H)]
  
  max_change = 0
  for h in range(H):
    for w in range(W):
      if Map[h][w]:
        change = 0
        for i in range(h-1, -1, -1):
          if Map[i][w]:
            change += 1
          else:
            break
        for i in range(h+1, H):
          if Map[i][w]:
            change += 1
          else:
            break
        for i in range(w-1, -1, -1):
          if Map[h][i]:
            change += 1
          else:
            break
        for i in range(w+1, W):
          if Map[h][i]:
            change += 1
          else:
            break
        change += 1
        max_change = max(max_change, change)
        
  print(max_change)
  
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0
S_t=list(map(list,zip(*S)))
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                S_t[i][j-k]+=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S_t[i][j-k]+=ans
            ans=0
            S_t[i][j]=0
c=0
for i in S_t:
    c=max(c,max(i))
print(c-1)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0
S_t=list(map(list,zip(*S)))
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                S_t[i][j-k]=ans+1+S_t[i][j-k]
            ans=0
        else:
            for k in range(1,ans+1):
                S_t[i][j-k]=ans+S_t[i][j-k]
            ans=0
            S_t[i][j]=0
c=0
for i in S_t:
    c=max(c,max(i))
print(c-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0
q=list()
S_t=list(map(list,zip(*S)))
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                q.append(ans+1+int(S_t[i][j-k]))
            ans=0
        else:
            for k in range(1,ans+1):
                q.append(ans+int(S_t[i][j-k]))
            ans=0
c=0
print(max(q)-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0
q=list()
S_t=np.array(S).T.tolist()
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                q.append(ans+1+int(S_t[i][j-k]))
            ans=0
        else:
            for k in range(1,ans+1):
                q.append(ans+int(S_t[i][j-k]))
            ans=0
c=0
print(max(q)-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
S=list(list(input()) for _ in range(H))
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#' and j!=W-1:
            ans+=1
        elif S[i][j]!='#'and j==W-1 :
            for k in range(ans+1):
                S[i][j-k]=ans+1
            ans=0
        else:
            for k in range(1,ans+1):
                S[i][j-k]=ans
            ans=0

S_t=np.array(S).T.tolist()
ans=0
for i in range(W):
    for j in range(H):
        if S_t[i][j]!='#' and j!=H-1:
            ans+=1
        elif S_t[i][j]!='#'and j==H-1 :
            for k in range(ans+1):
                S_t[i][j-k]=ans+1+int(S_t[i][j-k])
            ans=0
        else:
            for k in range(1,ans+1):
                S_t[i][j-k]=ans+int(S_t[i][j-k])
            ans=0
c=0
for p in S_t:
    for q in p:
        if q !='#':
            c=max(int(c),int(q)-1)
print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
left = [[0 for i in range(W)] for j in range(H)]
right = [[0 for i in range(W)] for j in range(H)]
down = [[0 for i in range(W)] for j in range(H)]
up = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        left[i][j] = cnt

for i in range(H):
    cnt = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        right[i][j] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        down[i][j] = cnt
    
for j in range(W):
    cnt = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        up[i][j] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + down[i][j] + up[i][j] -3)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3.4
 
# abc129_d
 
class Value:
    def __init__(self, v):
        self.v = v
 
def main():
    # Input
    h, w = [int(s) for s in input().split()]
    s = [input() for _ in range(h)]
    # Get ans
    yoko = [[Value(0) for _ in range(w)] for _ in range(h)]
    tate = [[Value(0) for _ in range(w)] for _ in range(h)]
    for i in range(h):
        cur = None
        for j in range(w):
            if s[i][j] == '#':
                cur = None
            else:
                if cur == None:
                    cur = Value(1)
                else:
                    cur.v += 1
                yoko[i][j] = cur
    for j in range(w):
        cur = None
        for i in range(h):
            if s[i][j] == '#':
                cur = None
            else:
                if cur == None:
                    cur = Value(1)
                else:
                    cur.v += 1
                tate[i][j] = cur
    def gene_ans():
        for i in range(h):
            for j in range(w):
                if s[i][j] == '.':
                    yield tate[i][j].v + yoko[i][j].v
    ans = max(gene_ans())-1
    # Output
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
import numpy as np
 
h,w = [ int(x) for x in sys.stdin.readline().split() ]
rows= []
cols= [ "" for _ in range(w) ]
for i in range(h):
    row = sys.stdin.readline().strip()
    rows.append( row )
    for i in range(w): cols[i]+= row[i]
#
l= np.zeros( shape=(h,w),dtype=np.int32 )
r= np.zeros( shape=(h,w),dtype=np.int32 )
i = 0
for row in rows:
    ll = l[i,:]
    rr = r[i,:]
    j= 0
    for m in row:
        if m=="#": ll[j]= 0
        elif j==0: ll[j]= 1
        else: ll[j]= ll[j-1] + 1
        j+=1
    #
    j= w
    for m in reversed(row):
        j-= 1
        if  m=="#": rr[j]= 0
        elif j==w-1: rr[j]= 1
        else: rr[j]= rr[j+1] + 1
    i+= 1
#
u= np.zeros( shape=(h,w),dtype=np.int32 )
d= np.zeros( shape=(h,w),dtype=np.int32 )
j = 0
for col in cols:
    uu = u[:,j]
    dd = d[:,j]
    i=0
    for m in col:
        if m=="#": uu[i]= 0
        elif i==0: uu[i]= 1
        else: uu[i]= uu[i-1] + 1
        i+= 1
    #
    i= h
    for m in reversed(col):
        i-=1
        if m=="#": dd[i]= 0
        elif i==h-1: dd[i]= 1
        else: dd[i]= dd[i+1] + 1
    #
    j+= 1
#
print( np.amax(l+r+u+d)-3 )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
import numpy as np

h,w = [ int(x) for x in sys.stdin.readline().split() ]
masu = np.ndarray( shape=(h,w),dtype='U1' )
for i in range(h):
    row = sys.stdin.readline()
    for j in range(w): masu[i][j]= str( row[j] )
#
# l, r
w1 = w - 1
l= np.ndarray( shape=(h,w),dtype=np.int32 )
r= np.ndarray( shape=(h,w),dtype=np.int32 )
for i in range(h):
    for j in range(w):
        if masu[i][j]=="#": l[i][j]= 0
        elif j==0: l[i][j]= 1
        else: l[i][j]= l[i][j-1] + 1
    #
for i in range(h):
    for j in range(w1,-1,-1):
        if masu[i][j]=="#": r[i][j]= 0
        elif j==w1: r[i][j]= 1
        else: r[i][j]= r[i][j+1] + 1
#
# u, d
h1= h - 1
u= np.ndarray( shape=(h,w),dtype=np.int32 )
d= np.ndarray( shape=(h,w),dtype=np.int32 )
for j in range(w):
    for i in range(h):
        if masu[i][j]=="#": u[i][j]= 0
        elif i==0: u[i][j]= 1
        else: u[i][j]= u[i-1][j] + 1
    #
for j in range(w):
    for i in range(h1,-1,-1):
        if masu[i][j]=="#": d[i][j]= 0
        elif i==h1: d[i][j]= 1
        else: d[i][j]= d[i+1][j] + 1
#
print( np.amax( l+r+u+d )-3 )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
import numpy as np

h,w = [ int(x) for x in sys.stdin.readline().split() ]
masu = np.ndarray( shape=(h,w),dtype='U1' )
for i in range(h):
    row = sys.stdin.readline()
    for j in range(w): masu[i][j]= str( row[j] )
#
# l, r
w1 = w - 1
l= np.ndarray( shape=(h,w),dtype=np.int32 )
r= np.ndarray( shape=(h,w),dtype=np.int32 )
for i in range(h):
    for j in range(w):
        if masu[i][j]=="#": l[i][j]= 0
        elif j==0: l[i][j]= 1
        else: l[i][j]= l[i][j-1] + 1
    #
    for j in range(w1,-1,-1):
        if masu[i][j]=="#": r[i][j]= 0
        elif j==w1: r[i][j]= 1
        else: r[i][j]= r[i][j+1] + 1
#
# u, d
h1= h - 1
u= np.ndarray( shape=(h,w),dtype=np.int32 )
d= np.ndarray( shape=(h,w),dtype=np.int32 )
for j in range(w):
    for i in range(h):
        if masu[i][j]=="#": u[i][j]= 0
        elif i==0: u[i][j]= 1
        else: u[i][j]= u[i-1][j] + 1
    #
    for i in range(h1,-1,-1):
        if masu[i][j]=="#": d[i][j]= 0
        elif i==h1: d[i][j]= 1
        else: d[i][j]= d[i+1][j] + 1
#
print( np.amax( l+r+u+d )-3 )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
 
h,w = [ int(x) for x in sys.stdin.readline().split() ]
rows= []
cols= [ "" for _ in range(w) ]
for i in range(h):
    row = sys.stdin.readline().strip()
    rows.append( row )
    for i in range(w): cols[i]+= row[i]
#
l= []
r= []
for row in rows:
    ll = []
    rr = []
    for m in row:
        if m=="#": ll.append( 0 )
        elif not ll: ll.append( 1 )
        else: ll.append( ll[-1] + 1 )
    #
    for m in reversed(row):
        if  m=="#": rr.append( 0 )
        elif not rr: rr.append( 1 )
        else: rr.append( rr[-1] + 1 )
    #
    rr.reverse()
    l.append(ll)
    r.append(rr)
#
u= [ [] for _ in range(h) ]
d= [ [] for _ in range(h) ]
for col in cols:
    uu, dd = [], []
    for m in col:
        if m=="#": uu.append( 0 )
        elif not uu: uu.append( 1 )
        else: uu.append( uu[-1] + 1 )
    #
    for m in reversed(col):
        if m=="#": dd.append( 0 )
        elif not dd: dd.append( 1 )
        else: dd.append( dd[-1] + 1 )
    #
    dd.reverse()
    for u_ in u: u_.append( uu.pop() )
    for d_ in d: d_.append( dd.pop() )
#
u.reverse()
d.reverse()
mv= 0
for i in range(h):
    ll,rr,uu,dd = l[i],r[i],u[i],d[i]
    row = rows[i]
    for j in range(w):
        if row[j]=="#": continue
        tmp= ll[j] + rr[j] + uu[j] + dd[j] - 3
        if tmp>mv: mv= tmp
#
print( mv )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
 
h,w = [ int(x) for x in sys.stdin.readline().split() ]
rows= []
cols= [ "" for _ in range(w) ]
for i in range(h):
    row = sys.stdin.readline().strip()
    rows.append( row )
    for i in range(w): cols[i]+= row[i]
#
l= []
r= []
for row in rows:
    ll = []
    rr = []
    for m in row:
        if m=="#": ll.append( 0 )
        elif not ll: ll.append( 1 )
        else: ll.append( ll[-1] + 1 )
    #
    for m in reversed(row):
        if  m=="#": rr.append( 0 )
        elif not rr: rr.append( 1 )
        else: rr.append( rr[-1] + 1 )
    #
    rr.reverse()
    l.append(ll)
    r.append(rr)
#
u= []
d= []
for col in cols:
    uu, dd = [], []
    for m in col:
        if m=="#": uu.append( 0 )
        elif not uu: uu.append( 1 )
        else: uu.append( uu[-1] + 1 )
    #
    for m in reversed(col):
        if m=="#": dd.append( 0 )
        elif not dd: dd.append( 1 )
        else: dd.append( dd[-1] + 1 )
    #
    dd.reverse()
    u.append( uu )
    d.append( dd )
#
mv= 0
for i in range(h):
    row = rows[i]
    for j in range(w):
        if row[j]=="#": continue
        tmp= l[i][j] + r[i][j] + u[j][i] + d[j][i] - 3
        if tmp>mv: mv= tmp
#
print( mv )

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input().strip()+'#' for i in range(h)]+['#'*(w+2)]
dp = [[[0]*4 for i in range(w+2)] for i in range(h+2)]
ans = 0

for i in range(h+2):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][0] = 0
     else:
      dp[i][j][0] = dp[i][j-1][0] + 1
for i in range(h+2):
  for j in range(w+1,0,-1):
     if l[i][j] == '#':
      dp[i][j][1] = 0
     else:
      dp[i][j][1] = dp[i][j+1][1] + 1
for i in range(h+2):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][2] = 0
     else:
      dp[i][j][2] = dp[i-1][j][2] + 1
for i in range(h+1,0,-1):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][3] = 0
     else:
      dp[i][j][3] = dp[i+1][j][3] + 1
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans, sum(dp[i][j]) - 3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#   ABC129　D問題
import numpy as np

H, W = map(int, input().split())    #   1 <= H, W <= 2000
S_arr = []
for _ in range(H):
    S_arr.append(list(input()))

point_arr = np.zeros((H, W))

start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            point_arr[y, start:stop] += stop - start
            start = stop + 1
    point_arr[y, start:W] += W - start
    

for x in range(W):  #   コードのコピペ禁止の原則に違反してるけど、改善方法が思いつかない問題
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            point_arr[start:stop, x] += stop - start
            start = stop + 1
    point_arr[start:H, x] += H - start

print(int(np.max(point_arr))-1) 
#   O(H*W)程度の計算量で十分高速だと思ってたのに、そうでもない問題
#   2019/06/10 現在未解決　Numpy配列の計算量かな？ポインタ復習が必要かな？

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
dp = [[[0]*4 for i in range(w+2)] for i in range(h+2)]
ans = 0

for i in range(h+2):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][0] = 0
     else:
      dp[i][j][0] = dp[i][j-1][0] + 1
for i in range(h+2):
  for j in range(w+1,0,-1):
     if l[i][j] == '#':
      dp[i][j][1] = 0
     else:
      dp[i][j][1] = dp[i][j+1][1] + 1
for i in range(h+2):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][2] = 0
     else:
      dp[i][j][2] = dp[i-1][j][2] + 1
for i in range(h+1,0,-1):
  for j in range(w+2):
     if l[i][j] == '#':
      dp[i][j][3] = 0
     else:
      dp[i][j][3] = dp[i+1][j][3] + 1
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans, sum(dp[i][j]) - 3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
 
import sys
 
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]
#
# l, r
w1 = w - 1
l= [ [ 0 ] * w for _ in range(h) ]
r= [ [ 0 ] * w for _ in range(h) ]
for i in range(h):
    for j in range(w):
        if masu[i][j]=="#": l[i][j]= 0
        elif j==0: l[i][j]= 1
        else: l[i][j]= l[i][j-1] + 1
    #
    for j in range(w1,-1,-1):
        if masu[i][j]=="#": r[i][j]= 0
        elif j==w1: r[i][j]= 1
        else: r[i][j]= r[i][j+1] + 1
#
# u, d
h1= h - 1
u= [ [ 0 ] * w for _ in range(h) ]
d= [ [ 0 ] * w for _ in range(h) ]
for j in range(w):
    for i in range(h):
        if masu[i][j]=="#": u[i][j]= 0
        elif i==0: u[i][j]= 1
        else: u[i][j]= u[i-1][j] + 1
    #
    for i in range(h1,-1,-1):
        if masu[i][j]=="#": d[i][j]= 0
        elif i==h1: d[i][j]= 1
        else: d[i][j]= d[i+1][j] + 1
#
mv= 0
for i in range(h):
    for j in range(w):
        if masu[i][j]=="#": continue
        tmp= l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        if tmp>mv: mv= tmp
#
print( mv )

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = map(int,input().split())
orimap = []
for _ in range(H):
    orimap.append(input())
L = np.zeros((H,W),dtype = int)
R = np.zeros((H,W),dtype = int)
U = np.zeros((H,W),dtype = int)
D = np.zeros((H,W),dtype = int)

for i in range(H):
    for j in range(W):
        if orimap[i][j] == "#":
            L[i][j] = 0
            U[i][j] = 0
        else:
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1]+1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

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

best = 0
for i in range(H):
    for j in range(W):
        cur = L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
        if best < cur:
            best = cur
print(best)

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()))
r1 = np.zeros((h, w))
for i in range(h):
  tmp = []
  for j in range(w):
    if s[i][j] == '#':
      if len(tmp) > 0:
        for k in tmp:
          r1[i][k] = len(tmp)
      tmp = []
    else:
      tmp.append(j)
  else:
    if len(tmp) > 0:
      for k in tmp:
        r1[i][k] = len(tmp)
r2 = np.zeros((h, w))
for j in range(w):
  tmp = []
  for i in range(h):
    if s[i][j] == '#':
      if len(tmp) > 0:
        for k in tmp:
          r2[k][j] = len(tmp)
      tmp = []
    else:
      tmp.append(i)
  else:
    if len(tmp) > 0:
      for k in tmp:
        r2[k][j] = len(tmp)
print(int(np.max(r1 + r2 - 1)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

point_arr = np.zeros((H, W))

x = 0
start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            point_arr[y, start:stop] += stop - start
            start = stop + 1
    point_arr[y, start:W] += W - start
    

for x in range(W):
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            point_arr[start:stop, x] += stop - start
            start = stop + 1
    point_arr[start:H, x] += H - start

print(int(np.max(point_arr))-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

point_arr = np.zeros((H, W))

x = 0
start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            point_arr[y, start:stop] += stop - start
            start = stop + 1
    point_arr[y, start:W] += W - start
    
#print(point_arr)

for x in range(W):
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            point_arr[start:stop, x] += stop - start
            start = stop + 1
    point_arr[start:H, x] += H - start

print(int(np.max(point_arr))-1)

Submission status: Time Limit Exceeded

Solution code:
def inpl():
    return list(map(int, input().split()))


H, W = inpl()
S = [input() for i in range(H)]

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

for h in range(H):
    if S[h][0] == ".":
        L[h][0] = 1
    if S[h][-1] == ".":
        R[h][-1] = 1
    for w in range(1, W):
        if S[h][w] == ".":
            L[h][w] = L[h][w - 1] + 1
        else:
            L[h][w] = 0

        if S[h][-w - 1] == ".":
            R[h][-w - 1] = R[h][-w] + 1
        else:
            R[h][-w - 1] = 0

for w in range(W):
    if S[0][w] == ".":
        U[0][w] = 1
    if S[-1][w] == ".":
        D[-1][w] = 1
    for h in range(1, H):
        if S[h][w] == ".":
            U[h][w] = U[h - 1][w] + 1
        else:
            U[h][w] = 0

        if S[-h - 1][w] == ".":
            D[-h - 1][w] = D[-h][w] + 1
        else:
            R[-h - 1][w] = 0

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, U[h][w] + D[h][w] + L[h][w] + R[h][w] - 3)

print(ans)

Submission status: Time Limit Exceeded

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

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i, gs in enumerate(Gs):
        count = 0
        for j, s in enumerate(gs):
            if s == '#':
                count = 0
                Gc[i][j] = 0
            else:
                count += 1
                Gc[i][j] = count

    return Gc

Gs1 = np.asarray(S)
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
maze = [['#']*(W+2)]
for i in range(H):
    append_str = '#' + input() + '#'
    maze.append(list(append_str))
maze.append(['#']*(W+2))
L = [[0]*(W+2)]
for i in range(H+1):
    L.append([0]*(W+2))
import sys
sys.setrecursionlimit(100000000)
import copy
R = copy.deepcopy(L)
U = copy.deepcopy(L)
D = copy.deepcopy(L)

for h in range(H+2):
    for w in range(W+2):
       if maze[h][w] == '.':
           L[h][w] = L[h][w-1]+1
           U[h][w] = U[h-1][w]+1
       if maze[h][W+2-w-1]=='.':
           R[h][W+2-w-1] = R[h][W+2-w]+1
       if maze[H+2-h-1][w]=='.':
           D[H+2-h-1][w] = D[H+2-h][w]+1
           
ans = -1
for h in range(H+2):
    for w in range(W+2):
        ans = max(ans,(L[h][w]+R[h][w]+U[h][w]+D[h][w]-3))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = list()
S.append("#" * (W+2))
for i in range(H):
  S.append("#"+input()+"#")
S.append("#" * (W+2))
ans = 1

for i in range(1,H+1):
  for j in range(1, W+1):
    if S[i][j] == ".":
      tmp = 1
      k = 1
      while S[i][j+k] == ".":
        tmp += 1
        k += 1
      k = 1
      while S[i][j-k] == ".":
        tmp += 1
        k += 1
      k = 1
      while S[i+k][j] == ".":
        tmp += 1
        k += 1
      k = 1
      while S[i-k][j] == ".":
        tmp += 1
        k += 1
      ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
L=[]
for inp in range(h):
    L.append(input())
#print(L)

#left
grid_l=[]
for y in range(h):
    grid_l.append([])
    n=0
    for x_chr in L[y]:
        if x_chr=="#":
            n=0
        else:
            n+=1
        grid_l[y].append(n)
    
#print(grid_l)

for y in range(h):
    n=0
    for x in range(w):
        if L[y][w-x-1]=="#":
            n=0
        else:
            n+=1
        grid_l[y][w-x-1]+=n
    
#print(grid_r)

for x in range(w):
    n=0
    for y in range(h):
        if L[y][x]=="#":
            n=0
        else:
            n+=1
        grid_l[y][x]+=n

#print(grid_u)

for x in range(w):
    n=0
    for y in range(h):
        if L[h-y-1][x]=="#":
            n=0
        else:
            n+=1
        grid_l[h-y-1][x]+=n

#print(grid_d)

res=0
for y in range(h):
    maxy=max(grid_l[y])
    res=max(res,maxy)
#print(grid)
print(max(res-3,0))

Submission status: Time Limit Exceeded

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

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

Gs = np.asarray(S)
Gs_ = np.rot90(Gs, k=1)

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i, gs in enumerate(Gs):
        count = 0
        gc = []
        for j, s in enumerate(gs):
            if s == '#':
                count = 0
                Gc[i][j] = 0
            else:
                count += 1
                Gc[i][j] = count

    Gn = np.empty((h,w))
    for i, gc in enumerate(Gc):
        count = -1
        gn = []
        for j, c in enumerate(reversed(gc)):
            if c == 0:
                count = -1
                Gn[i][w-j-1] = 0
            else:
                if count == -1:
                    count = c
                Gn[i][w-j-1]  = count

    return Gn

Gn = count_light(Gs, H, W)
Gn_ = count_light(Gs_, W, H)
Gn_ = np.rot90(Gn_, k=-1)

Gsum = Gn+Gn_
ans = np.max(Gsum)-1

        
print(int(ans))