Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

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

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

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

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

Sample Input 1

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

Sample Output 1

8

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

Sample Input 2

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

Sample Output 2

13



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


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
import sys

H,W=map(int,next(sys.stdin).split())
S=[[*ln] for ln in map(str.strip,sys.stdin)]

xs=[[0]*(W+1) for _ in range(H+1)]
ys=[[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            if j==0:
                xs[i][j]=1
            else:
                xs[i][j]+=1+xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue
        if xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys
from collections import (
    Counter,
    defaultdict as ddict,
    deque,
    namedtuple as ntuple,
)
from functools import lru_cache
from heapq import *
from itertools import *
from pprint import pprint
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits,
)

cache=lru_cache(None)

hexdigits=digits+'ABCDEFabcdef'

inf=float('inf')
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615
ansmod=1000000007

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

################################################

H,W=ris()
S=rg()

xs=[[0]*(W+1) for _ in range(H+1)]
ys=[[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            if j==0:
                xs[i][j]=1
            else:
                xs[i][j]+=1+xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue
        if xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys
from collections import (
    Counter,
    defaultdict as ddict,
    deque,
    namedtuple as ntuple,
)
from functools import lru_cache
from heapq import *
from itertools import *
from pprint import pprint
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits,
)

cache=lru_cache(None)

hexdigits=digits+'ABCDEFabcdef'

inf=float('inf')
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615
ansmod=1000000007

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

################################################

H,W=ris()
S=rg()

xs=[[0]*W for _ in range(H)]
ys=[[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            if j==0:
                xs[i][j]=1
            else:
                xs[i][j]+=1+xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

#pprint(xs, width=60)
#pprint(ys, width=60)

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j]=='#':
            continue
        if j+1<W:
            xs[i][j]=max(xs[i][j],xs[i][j+1])
        if i+1<H:
            ys[i][j]=max(ys[i][j],ys[i+1][j])
        x=xs[i][j]
        y=ys[i][j]
        ans=max(ans,x+y-1)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
def ko(h,w,j):
  #hは配列
  a = [0 for _ in range(w)]
  for k in range(w):
    if h[k]=='.':
      cou = 0
      t = k
      s = k
      while t>0 and h[t-1]=='.':
        cou += 1
        t -= 1
    #  print("left",cou)
      while s+1<w and h[s+1]=='.':
        cou += 1
        s += 1
     # print("right",cou)
      cou += 1
      a[k] += cou
      #print(a)
  return a[j]
      
h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
s1 = [list(x) for x in zip(*s)]

ma = 0
for i in range(h):
  for j in range(w):
    c = s[i][j]
    if c==".":
      ma1 = ko(s[i],w,j) + ko(s1[j],h,i)
      ma = max(ma,ma1-1)
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys

from collections import *
ddict=defaultdict

from functools import lru_cache
cache=lru_cache(None)

from heapq import *
from itertools import *
from statistics import *

from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits
)
alnum=letters+digits
xdigits='01234567890abcdefabcdef'

from pprint import pprint

inf=float('inf')
ansmod=1000000007
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

################################################

H,W=ris()
S=rg()

xs=[[0]*W for _ in range(H)]
for i in range(H):
    j=0
    while j<W:
        ct=0
        k=j
        while k<W and S[i][k]!='#':
            ct+=1
            k+=1
        while j<k:
            xs[i][j]=ct
            j+=1
        j+=1

ans=0
ys=[[0]*W for _ in range(H)]
for j in range(W):
    i=0
    while i<H:
        ct=0
        k=i
        while k<H and S[k][j]!='#':
            ct+=1
            k+=1
        while i<k:
            ans=max(ans,xs[i][j]+ct-1)
            i+=1
        i+=1

#pprint(xs,width=60)
#print()
#pprint(ys,width=60)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys

from collections import *
ddict=defaultdict

from functools import lru_cache
cache=lru_cache(None)

from heapq import *
from itertools import *
from statistics import *

from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits
)
alnum=letters+digits
xdigits='01234567890abcdefabcdef'

from pprint import pprint

inf=float('inf')
ansmod=1000000007
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

################################################

H,W=ris()
S=rg()

def count(i,j,di,dj):
    ct=0
    while 0<=i<H and 0<=j<W and S[i][j]!='#':
        ct,i,j=ct+1,i+di,j+dj
    return ct

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            k=1
            k+=count(i-1,j,-1,0)
            k+=count(i,j+1,0,+1)
            k+=count(i+1,j,+1,0)
            k+=count(i,j-1,0,-1)
            ans=max(ans,k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

H,W = list(map(int,input().split()))
s = [input().rstrip() for _ in range(H)]
maperW = [[0]*W for _ in range(H)]
maperH = [[0]*W for _ in range(H)]


#--W方向を調べる--#
for ih in range(H):
    for iw in range(W):
        if s[ih][iw]=='#':
            maperW[ih][iw]=0
        elif s[ih][iw]=='.' and iw == 0:
            maperW[ih][iw]=1
        else:
            maperW[ih][iw]=1+maperW[ih][iw-1]
    for iw in range(W-2,-1,-1):
        if maperW[ih][iw+1] == 0 or maperW[ih][iw]==0:
            continue
        else:
            maperW[ih][iw] = maperW[ih][iw+1]
#--H方向を調べる--#
for iw in range(W):
    for ih in range(H):
        if s[ih][iw]=='#':
            maperH[ih][iw]=0
        elif s[ih][iw]=='.' and ih == 0:
            maperH[ih][iw]=1
        else:
            maperH[ih][iw]=1+maperH[ih-1][iw]
    for ih in range(H-2,-1,-1):
        if maperH[ih+1][iw] == 0 or maperH[ih][iw]==0:
            continue
        else:
            maperH[ih][iw] = maperH[ih+1][iw]
ans = 0
for iw in range(W):
    for ih in range(H):
        ans = max(ans,maperW[ih][iw]+maperH[ih][iw]-1)
print(ans)

Submission status: Time Limit Exceeded

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


#left
left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0

#right
right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0
#top
top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0
#down
down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    if g[i][j] =="#":
      continue
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)

Submission status: Time Limit Exceeded

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


#left
left = [[0]*w for i in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if g[i][j] == ".":
            cnt += 1
            left[i][j] =cnt
        else:
            cnt = 0

#right
right = [[0]*w for i in range(h)]
for i in range(h-1,-1,-1):
    cnt = 0
    for j in range(w-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            right[i][j] =cnt
        else:
            cnt = 0
#top
top = [[0]*w for i in range(h)]
for j in range(w):
    cnt = 0
    for i in range(h):
        if g[i][j] == ".":
            cnt += 1
            top[i][j] =cnt
        else:
            cnt = 0
#down
down = [[0]*w for i in range(h)]
for j in range(w-1,-1,-1):
    cnt = 0
    for i in range(h-1,-1,-1):
        if g[i][j] == ".":
            cnt += 1
            down[i][j] =cnt
        else:
            cnt = 0

maxans = -1
for i in range(h):
  for j in range(w):
    ans = left[i][j]+right[i][j]+top[i][j]+down[i][j]-3
    maxans = max(ans,maxans)
    
print(maxans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = []
s.append("#" * (w + 2))
for i in range(h):
    s.append("#" + input() + "#")
s.append("#" * (w + 2))

num = [[-1 for i in range(w + 2)] for i in range(h + 2)]
for i in range(1, h + 1):
    l = 0
    m = 0
    while l < w + 2:
        if s[i][l] == "#":
            l += 1
            continue
        else:
            m = l
            while s[i][m] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[i][j] += m - l
                l = m
for i in range(1, w + 1):
    l = 0
    m = 0
    while l < h + 2:
        if s[l][i] == "#":
            l += 1
            continue
        else:
            m = l
            while s[m][i] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[j][i] += m - l
                l = m
print(max([max([num[i][j] for j in range(w + 2)]) for i in range(h + 2)]))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
a = [[0]*w for i in range(h)]
b = [[0]*w for i in range(h)]

for i in range(h):
    tmp = 0
    for j in range(w):
        if s[i][j] == '.':
            tmp += 1
            a[i][j] = tmp
        else:
            tmp = 0
    tmp = 0
    for j in range(w-1, -1, -1):
        if s[i][j] == '.':
            tmp = max(tmp, a[i][j])
            a[i][j] = tmp
        else:
            tmp = 0

for j in range(w):
    tmp = 0
    for i in range(h):
        if s[i][j] == '.':
            tmp += 1
            b[i][j] = tmp
        else:
            tmp = 0
    tmp = 0
    for i in range(h-1, -1, -1):
        if s[i][j] == '.':
            tmp = max(tmp, b[i][j])
            b[i][j] = tmp
        else:
            tmp = 0

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, a[i][j]+b[i][j]-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys


    def input(): return sys.stdin.readline().rstrip()

    h, w = map(int, input().split())
    g = [[] for _ in range(h)]
    for i in range(h):
        g[i] = input()
    
    L = [[0]*w for _ in range(h)]
    R = [[0]*w for _ in range(h)]
    U = [[0]*w for _ in range(h)]
    D = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if g[i][j] == '#':
                continue
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j]+1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1]+1
    
    for i in range(h-1, -1, -1):
        for j in range(w-1, -1, -1):
            if g[i][j] == '#':
                continue
            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
    
    ans = 0
    for i in range(h):
        for j in range(w):
            tmp = L[i][j]+U[i][j]+D[i][j]+R[i][j]-3
            ans = max(tmp, ans)
    print(ans)
            
                


            

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
G=[input() for _ in range(H)]
A_u=[[0 for _ in range(W)] for _ in range(H)]
A_d=[[0 for _ in range(W)] for _ in range(H)]
A_r=[[0 for _ in range(W)] for _ in range(H)]
A_l=[[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(1,W):
    if G[h][w-1] == '.':
      A_r[h][w] = A_r[h][w-1]+1
  for w in range(W-2,-1,-1):
    if G[h][w+1] == '.':
      A_l[h][w] = A_l[h][w+1]+1
for w in range(W):
  for h in range(1,H):
    if G[h-1][w] == '.':
      A_d[h][w] = A_d[h-1][w]+1
  for h in range(H-2,-1,-1):
    if G[h+1][w] == '.':
      A_u[h][w] = A_u[h+1][w]+1
ans=0
for h in range(H):
  for w in range(W):
    if G[h][w] == '.':
      ans = max(ans,A_r[h][w]+A_l[h][w]+A_d[h][w]+A_u[h][w]+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
G=[input() for _ in range(H)]
A=[[[0,0,0,0] for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(1,W):
    if G[h][w-1] == '.':
      A[h][w][0] = A[h][w-1][0]+1
  for w in range(W-2,-1,-1):
    if G[h][w+1] == '.':
      A[h][w][1] = A[h][w+1][1]+1
for w in range(W):
  for h in range(1,H):
    if G[h-1][w] == '.':
      A[h][w][2] = A[h-1][w][2]+1
  for h in range(H-2,-1,-1):
    if G[h+1][w] == '.':
      A[h][w][3] = A[h+1][w][3]+1
ans=0
for h in range(H):
  for w in range(W):
    if G[h][w] == '.':
      ans = max(ans,sum(A[h][w])+1)
print(ans)

Submission status: Time Limit Exceeded

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

G = []
for _ in range(H):
    g = []
    line = input()
    for i in range(W):
        g.append(line[i])
    G.append(g)

# 左に何マス行けるか
G_left = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W):
        if G[h][w] == "#":
            cnt = 0
            G_left[h][w] = 0
        elif G[h][w] == ".":
            cnt += 1
            G_left[h][w] = cnt
# print(G_left)

# 右に何マス行けるか
G_right = [[0] * W for _ in range(H)]
for h in range(H):
    cnt = 0
    for w in range(W - 1, -1, -1):
        if G[h][w] == "#":
            cnt = 0
            G_right[h][w] = 0
        elif G[h][w] == ".":
            cnt += 1
            G_right[h][w] = cnt
# print(G_right)

# 上に何マス行けるか
G_up = [[0] * W for _ in range(H)]
for w in range(W):
    cnt = 0
    for h in range(H):
        if G[h][w] == "#":
            cnt = 0
            G_up[h][w] = 0
        elif G[h][w] == ".":
            cnt += 1
            G_up[h][w] = cnt
# print(G_up)

# 下に何マス行けるか
G_down = [[0] * W for _ in range(H)]
for w in range(W):
    cnt = 0
    for h in range(H - 1, -1, -1):
        if G[h][w] == "#":
            cnt = 0
            G_down[h][w] = 0
        elif G[h][w] == ".":
            cnt += 1
            G_down[h][w] = cnt
# print(G_down)
ans = 0
for h in range(H):
    for w in range(W):
        tmp = G_left[h][w] + G_right[h][w] + G_up[h][w] + G_down[h][w] - 3
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

grid = []
for _ in range(H):
    line = input()
    # 後で都合が良いので末尾に足しておく
    line += "#"
    grid.append(line)

# 後で都合が良いので末尾に足しておく
grid.append("#" * W)
# print(grid)

G_h = []
for h in range(H):
    g = [-1] * W
    lamp_start = -1
    lamp = 0
    line = grid[h]
    for w in range(W):
        if line[w] == "#":
            g[w] = 0
        elif line[w] == ".":
            lamp += 1
            if lamp_start == -1:
                lamp_start = w
                # print("lampstart", w)
            if line[w + 1] == "#":
                # print("lampend", w)
                for i in range(lamp_start, w + 1):
                    g[i] = lamp
                lamp_start = -1
                lamp = 0
    G_h.append(g)

# print(G_h)

G_v = []
for w in range(W):
    g = [-1] * H
    lamp_start = -1
    lamp = 0
    line = []
    for hi in range(H):
        line.append(grid[hi][w])
    line.append("#")
    # line = grid[w]
    for h in range(H):
        if line[h] == "#":
            g[h] = 0
        elif line[h] == ".":
            lamp += 1
            if lamp_start == -1:
                lamp_start = h
                # print("lampstart", w)
            if line[h + 1] == "#":
                # print("lampend", w)
                for i in range(lamp_start, h + 1):
                    g[i] = lamp
                lamp_start = -1
                lamp = 0
    G_v.append(g)

# print(G_v)

ans = 0
for h in range(H):
    for w in range(W):
        tmp_ans = G_h[h][w] + G_v[w][h] - 1
        ans = max(ans, tmp_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W = map(int, input().split())
G = [sys.stdin.readline() for _ in range(H)]

counts = [[[-1] * 4 for _ in range(W + 1)] for _ in range(H + 1)]
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
            counts[h][w][0] = counts[h][w-1][0] + 1
            counts[h][w][1] = counts[h-1][w][1] + 1
        dih = H - h - 1
        diw = W - w - 1
        if G[dih][diw] == ".":
            counts[dih][diw][2] = counts[dih][diw+1][2] + 1
            counts[dih][diw][3] = counts[dih+1][diw][3] + 1
ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
            ans = max(ans, sum(counts[h][w]) + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [[*map(lambda c:c == ".", input())] for _ in [0] * h]
for i in "LRUD":
    exec(i + "= [[0] * w for _ in [0] * h]")
for i in range(h):
    for j in range(w):
        L[i][j]    = L[i][j-1] + 1 if s[i][j]    else 0
        R[i][-j-1] = R[i][-j]  + 1 if s[i][-j-1] else 0
for j in range(w):
    for i in range(h):
        U[i][j]    = U[i-1][j] + 1 if s[i][j]    else 0
        D[-i-1][j] = D[-i][j]  + 1 if s[-i-1][j] else 0
print(max(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(h) for j in range(w)))

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s =["#"*(w+2)] + ["#"+input()+"#" for i in range(h)] + ["#"*(w+2)]
# print(s)
ans = 0
opt = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == ".":
            cnt = 1
            for k in opt:
                tempy = i
                tempx = j
                while s[tempy+k[0]][tempx+k[1]] == ".":
                    cnt += 1
                    tempy += k[0]
                    tempx += k[1]
            ans = max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

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

l = [[0]*w for i in range(h)]
r = [[0]*w for i in range(h)]
u = [[0]*w for i in range(h)]
d = [[0]*w for i in range(h)]

for i in range(h):
    c = 0
    for j in range(w):
        if x[i][j] == '.':
            l[i][j] = c
            c += 1
        else: c=0


for i in range(h):
    c = 0
    for j in range(w):
        if x[i][w-1-j] == '.':
            r[i][w-1-j] = c
            c += 1
        else: c=0

for i in range(w):
    c = 0
    for j in range(h):
        if x[j][i] == '.':
            u[j][i] = c
            c += 1
        else: c=0

for i in range(w):
    c = 0
    for j in range(h):
        if x[h-1-j][i] == '.':
            d[h-1-j][i] = c
            c += 1
        else: c=0

ans = 0
for i in range(h):
    for j in range(w):
        c = l[i][j]+r[i][j]+u[i][j]+d[i][j]
        if x[i][j]=='.':c+=1
        ans = max(ans,c)

print(ans)

Submission status: Time Limit Exceeded

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

cnt_l, cnt_r, cnt_u, cnt_d = [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if data[i][j] == "#":
            cnt_l[i][j] = 0
        else:
            cnt_l[i][j] = cnt_l[i][j - 1] + 1
    
        if data[i][w - j - 1] == "#":
            cnt_r[i][w - j - 1] = 0
        else:
            if j == 0:
                cnt_r[i][w - j - 1] = 1
            else:
                cnt_r[i][w - j - 1] = cnt_r[i][w - j] + 1

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

        if data[h - i - 1][j] == "#":
            cnt_d[h - i - 1][j] = 0
        else:
            if i == 0:
                cnt_d[h - i - 1][j] = 1
            else:
                cnt_d[h - i - 1][j] = cnt_d[h - i][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        total= cnt_l[i][j] + cnt_r[i][j] + cnt_u[i][j] + cnt_d[i][j] - 3
        ans = max(ans, total)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
data = []
for i in range(h):
    s = input()
    data.append(s)
cnt_l, cnt_r, cnt_u, cnt_d = [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)], [[0] * w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if data[i][j] == "#":
            cnt_l[i][j] = 0
        else:
            cnt_l[i][j] = cnt_l[i][j - 1] + 1
    
        if data[i][w - j - 1] == "#":
            cnt_r[i][w - j - 1] = 0
        else:
            if j == 0:
                cnt_r[i][w - j - 1] = 1
            else:
                cnt_r[i][w - j - 1] = cnt_r[i][w - j] + 1

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

        if data[h - i - 1][j] == "#":
            cnt_d[h - i - 1][j] = 0
        else:
            if i == 0:
                cnt_d[h - i - 1][j] = 1
            else:
                cnt_d[h - i - 1][j] = cnt_d[h - i][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        total= cnt_l[i][j] + cnt_r[i][j] + cnt_u[i][j] + cnt_d[i][j] - 3
        ans = max(ans, total)

print(ans)

Submission status: Time Limit Exceeded

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

L = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            L[h][w] = 0
        elif w == 0:
            L[h][w] = 1
        else:
            L[h][w] = L[h][w-1] + 1
        
        if S[h][w] == "#":
            U[h][w] = 0
        elif h == 0:
            U[h][w] = 1
        else:
            U[h][w] = U[h-1][w] + 1

R = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] == "#":
            R[h][w] = 0
        elif w == W-1:
            R[h][w] = 1
        else:
            R[h][w] = R[h][w+1] + 1

        if S[h][w] == "#":
            D[h][w] = 0
        elif h == H-1:
            D[h][w] = 1
        else:
            D[h][w] = D[h+1][w] + 1

ans = 0
for h in range(H):
    for w in range(W):
        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 = []
for _ in range(H):
    S.append(input())


yoko, tate = [], []
for h in range(H):
    now = []
    
    w, cnt = 0, 0
    while True:
        if not w < W:
            for _ in range(cnt): now.append(cnt) 
            break

        if S[h][w] == "#":
            for _ in range(cnt): now.append(cnt)
            now.append(0)
            cnt = 0
        else:
            cnt += 1

        w += 1

    yoko.append(now)

for w in range(W):
    now = []
    
    h, cnt = 0, 0
    while True:
        if not h < H:
            for _ in range(cnt): now.append(cnt) 
            break

        if S[h][w] == "#":
            for _ in range(cnt): now.append(cnt)
            now.append(0)
            cnt = 0
        else:
            cnt += 1

        h += 1
    
    tate.append(now)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, yoko[h][w]+tate[w][h]-1)
    
print(ans)