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: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [0 for i in range(n)]
for i in range(n):
  a[i] = input()
print(n, m)
print(a)
num = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
  for j in range(m):
    if a[i][j] == ".":
      num[i][j] += 1
      # 下
      i_2 = i+1
      j_2 = j
      if 0 <= i_2 and i_2 < n:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 += 1
          if 0 <= i_2 and i_2 < n:
            1
          else:
            break
      # 上
      i_2 = i-1
      j_2 = j
      if 0 <= i_2 and i_2 < n:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 -= 1
          if 0 <= i_2 and i_2 < n:
            1
          else:
            break
      # 上
      i_2 = i
      j_2 = j-1
      if 0 <= j_2 and j_2 < m:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 -= 1
          if 0 <= j_2 and j_2 < m:
            1
          else:
            break
      # 下
      i_2 = i
      j_2 = j+1
      if 0 <= j_2 and j_2 < m:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 += 1
          if 0 <= j_2 and j_2 < m:
            1
          else:
            break
print(max([max(i) for i in num]))

Submission status: Wrong Answer

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

us = [[0] * w for i in range(h)]
ds = [[0] * w for i in range(h)]
ls = [[0] * w for i in range(h)]
rs = [[0] * w for i in range(h)]

for x in range(w):
    u_cnt = 0
    for y in range(h):
        us[y][x] = u_cnt
        if cells[y][x] == '.':
            u_cnt += 1
        else:
            u_cnt = 0
    d_cnt = 0
    for y in range(h - 1, -1, -1):
        ds[y][x] = d_cnt
        if cells[y][x] == '.':
            d_cnt += 1
        else:
            d_cnt = 0
for y in range(h):
    l_cnt = 0
    for x in range(w):
        ls[y][x] = l_cnt
        if cells[y][x] == '.':
            l_cnt += 1
        else:
            l_cnt = 0

    r_cnt = 0
    for x in range(w - 1, -1, -1):
        rs[y][x] = r_cnt
        if cells[y][x] == '.':
            r_cnt += 1
        else:
            r_cnt = 0

maxv = 0
for y in range(h):
    for x in range(w):
        maxv = max(maxv, us[y][x] + ds[y][x] + ls[y][x] +
                   rs[y][x] + (1 if cells[y][x] == '.' else 0))
print(maxv)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j in range(w-1):
        if s[i][j]=='.':
            l[i][j+1] = l[i][j]+1

for i in range(h):
    for j in range(1,w):
        if s[i][w-j]=='.':
            r[i][w-j-1] = r[i][w-j]+1

for i in range(h-1):
    for j in range(w):
        if s[i][j]=='.':
            u[i+1][j] = u[i][j]+1

for i in range(1,h):
    for j in range(w):
        if s[i][j]=='.':
            d[h-i-1][j] = d[h-i][j]+1

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

print(ans)

Submission status: Wrong Answer

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

for i in range(H):
    Si = list(input())
    for j in range(W):
        if Si[j] == '#':
            S[i][j] = 1

# row
S_row = [[0]*W for _ in range(H)]
for i in range(H):
    c = 0
    for j in range(W):
        if S[i][j] == 1:
            c = 0
        else:
            c += 1
        S_row[i][j] = c
    # reverse
    for j in range(W-2, -1, -1):
        if S_row[i][j+1] > 0:
            S_row[i][j] = S_row[i][j+1]

# col
S_col = [[0]*W for _ in range(H)]
for j in range(W):
    c = 0
    for i in range(H):
        if S[i][j] == 1:
            c = 0
        else:
            c += 1
        S_col[i][j] = c
    # reverse
    for i in range(H-2, -1, -1):
        if S_col[i+1][j] > 0:
            S_col[i][j] = S_col[i+1][j]

# res
res = max([max([S_row[i][j] + S_col[i][j] - 1 for j in range(W)]) for i in range(H)])
print(res)

Submission status: Wrong Answer

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

# あるマスから（右・下・左・上）にいくつ障害物ないマスが続くか
right_space = [[-1] * (W + 2) for i in range(H + 2)]
down_space = [[-1] * (W + 2) for i in range(H + 2)]
left_space = [[-1] * (W + 2) for i in range(H + 2)]
up_space = [[-1] * (W + 2) for i in range(H + 2)]

# 左上から更新（上・左に対応）
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if G[h - 1][w - 1] == '.':
            up_space[h][w] = up_space[h - 1][w] + 1
            left_space[h][w] = left_space[h][w - 1] + 1

# 右下から更新（下・右に対応）
for h in reversed(range(1, H + 1)):
    for w in reversed(range(1, W + 1)):
        if G[h - 1][w - 1] == '.':
            down_space[h][w] = down_space[h + 1][w] + 1
            right_space[h][w] = right_space[h][w + 1] + 1


ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == '.':
            tmp_ans = right_space[h][w] + down_space[h][w] + left_space[h][w] + up_space[h][w] + 1
            ans = max(ans, tmp_ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W = map(int,input().split())
S=[]
ans = 0
for i in range(H):
    Si = list(input())
    S.append(Si)
r = [0]*(H)
c = [0]*(W)
for i in range(H):
    r[i] = S[i].count(".")
for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == ".":
            cnt += 1
    c[j] = cnt

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans,r[i]+c[j]-2)
        else:
            ans = max(ans,r[i]+c[j])
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(h):
    count = 0
    start = 0
    end = 0
    for j in range(w):
        if s[i][j] != "#":  # 　#じゃなければおけ
            count += 1
        else:
            for z in range(start, end):
                s[i][z] = count
            start = end+1
            count = 0
        end += 1
    for z in range(start, end):
        s[i][z] = count
    # print(s[i])
ans = 0

for i in range(w):
    count = 0
    start = 0
    end = 0
    for j in range(h):
        if s[j][i] != "#":  # 　#じゃなければおけ
            count += 1
        else:
            for z in range(start, end):
                s[z][i] += count
            start = end+1
            count = 0
        end += 1
    for z in range(start, end):
        s[z][i] += count
# print()
for i in range(h):
    # print(s[i])
    for j in range(w):

        if s[i][j] != "#":
            ans = max(ans, s[i][j])
print(ans-1)

Submission status: Time Limit Exceeded

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

cnt = [[0]*w for _ in range(h)]

yStarts = [-1] * w
yStrks = [0] * w

for y in range(h):
    xStart = -1
    xStrk = 0

    for x in range(w):
        if grid[y][x] == ".":
            if xStart == -1:
                xStart = x
            xStrk += 1

            if yStarts[x] == -1:
                yStarts[x] = y
            yStrks[x] += 1

        if grid[y][x] == "#" or x == w-1:
            if xStart != -1:
                xEnd = x if grid[y][x] == "." else x-1

                for x2 in range(xStart, xEnd+1):
                    cnt[y][x2] += (xEnd-xStart)+1

            xStart = -1
            xStrk = 0

        if grid[y][x] == "#" or y == h-1:
            if yStarts[x] != -1:
                yEnd = y if grid[y][x] == "." else y-1

                for y2 in range(yStarts[x], yEnd+1):
                    cnt[y2][x] += (yEnd-yStarts[x])+1

            yStarts[x] = -1
            yStrks[x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, cnt[y][x]-1)

print(ans)

Submission status: Time Limit Exceeded

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

w1=[[]for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            w1[i].append(j)
    w1[i].append(W)

w2=[[0]*W for _ in range(H)]
for i in range(H):
    k=0
    L=-1
    R=w1[i][k]
    for j in range(W):
        if S[i][j]=='#':
            L=w1[i][k]
            k+=1
            R=w1[i][k]
            continue
        w2[i][j]=R-L-1

h1=[[]for _ in range(W)]
for j in range(W):
    for i in range(H):
        if S[i][j]=='#':
            h1[j].append(i)
    h1[j].append(H)

h2=[[0]*W for _ in range(H)]
for j in range(W):
    k=0
    L=-1
    R=h1[j][k]
    for i in range(H):
        if S[i][j]=='#':
            L=h1[j][k]
            k+=1
            R=h1[j][k]
            continue
        h2[i][j]=R-L-1

print(max(w2[i][j]+h2[i][j]-1 for i in range(H)for j in range(W)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
h, w = [int(x) for x in input().split()]
g = [input() for i in range(h)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
hit = [[[0 for j in range(w)] for i in range(h)] for dire in dirs]
for d, dire in enumerate(dirs):
    di, dj = dire
    for i in range(h) if di < 0 else reversed(range(h)):
        for j in range(w) if dj < 0 else reversed(range(w)):
            if g[i][j] != '#':
                hit[d][i][j] = (hit[d][i + di][j + dj] if 0 <= i + di < h and 0 <= j + dj < w else 0) + 1
print(max(sum(hit[d][i][j] for d in range(len(dirs))) - 3 for i in range(h) for j in range(w) if g[i][j] != '#'))

Submission status: Time Limit Exceeded

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ban=[]
    h,w=INTM()
    for i in range(h):
        s=STR()
        ban.append(s)
    left =np.zeros((h,w),dtype=np.int16)
    right=np.zeros((h,w),dtype=np.int16)
    up   =np.zeros((h,w),dtype=np.int16)
    down =np.zeros((h,w),dtype=np.int16)
    #print(up)
    for i1 in range(h):
        for i2 in range(w):
            i3=(w-1)-i2
            i4=(h-1)-i1
            if ban[i1][i2]=="#":
                left[i1][i2]=0
                up[i1][i2]=0
            else:
                if i1==0:
                    up[i1][i2]=1
                else:
                    up[i1][i2]=up[i1-1][i2]+1

                if i2==0:
                    left[i1][i2]=1
                else:
                    left[i1][i2]=left[i1][i2-1]+1
            if ban[i1][i3]=="#":
                right[i1][i3]=0
            else:
                if i2==0:
                    right[i1][i3]=1
                else:
                    right[i1][i3]=right[i1][i3+1]+1    

            if ban[i4][i2]=="#":
                down[i4][i2]=0
            else:
                if i1==0:
                    down[i4][i2]=1
                else:
                    down[i4][i2]=down[i4+1][i2]+1
    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ban=[]
    h,w=INTM()
    for i in range(h):
        s=STR()
        ban.append(s)
    left =np.zeros((h,w),dtype='int')
    right=np.zeros((h,w),dtype='int')
    up   =np.zeros((h,w),dtype='int')
    down =np.zeros((h,w),dtype='int')
    #print(up)
    for i1 in range(h):
        for i2 in range(w):
            i3=(w-1)-i2
            i4=(h-1)-i1
            if ban[i1][i2]=="#":
                left[i1][i2]=0
                up[i1][i2]=0
            else:
                if i1==0:
                    up[i1][i2]=1
                else:
                    up[i1][i2]=up[i1-1][i2]+1

                if i2==0:
                    left[i1][i2]=1
                else:
                    left[i1][i2]=left[i1][i2-1]+1
            if ban[i1][i3]=="#":
                right[i1][i3]=0
            else:
                if i2==0:
                    right[i1][i3]=1
                else:
                    right[i1][i3]=right[i1][i3+1]+1    

            if ban[i4][i2]=="#":
                down[i4][i2]=0
            else:
                if i1==0:
                    down[i4][i2]=1
                else:
                    down[i4][i2]=down[i4+1][i2]+1
    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
#MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ban=[]
    h,w=INTM()
    for i in range(h):
        s=STR()
        ban.append(s)
    left =np.zeros((h,w),dtype='int')
    right=np.zeros((h,w),dtype='int')
    up   =np.zeros((h,w),dtype='int')
    down =np.zeros((h,w),dtype='int')
    #print(up)
    for i1 in range(h):
        for i2 in range(w):
            i3=(w-1)-i2
            i4=(h-1)-i1
            if ban[i1][i2]=="#":
                left[i1][i2]=0
            else:
                if i2==0:
                    left[i1][i2]=1
                else:
                    left[i1][i2]=left[i1][i2-1]+1
            if ban[i1][i3]=="#":
                right[i1][i3]=0
            else:
                if i2==0:
                    right[i1][i3]=1
                else:
                    right[i1][i3]=right[i1][i3+1]+1
            
            if ban[i1][i2]=="#":
                up[i1][i2]=0
            else:
                if i1==0:
                    up[i1][i2]=1
                else:
                    up[i1][i2]=up[i1-1][i2]+1

            if ban[i4][i2]=="#":
                down[i4][i2]=0
            else:
                if i1==0:
                    down[i4][i2]=1
                else:
                    down[i4][i2]=down[i4+1][i2]+1
    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
maps = [[None]*(W+2) for _ in range(H+2)]
maps[0] = ['#']*(W+2)
for i in range(H):
    maps[i+1] = ['#']+list(input())+['#']
maps[H+1] = ['#']*(W+2)
# pprint.pprint(maps)
# L[i][j]:それぞれ該当マスから上下左右に'.'が続く数
ans = 0
L = [[[0]*4 for _ in range(W+2)] for _ in range(H+2)]
for i in range(1, H+1):
    for j in range(1, W+1):
        if maps[i][j] == '.':
            L[i][j][0] = L[i-1][j][0]+1
            L[i][j][2] = L[i][j-1][2]+1
        if maps[H+1-i][W+1-j] == '.':
            L[H+1-i][W+1-j][1] = L[H+2-i][W+1-j][1]+1
            L[H+1-i][W+1-j][3] = L[H+1-i][W+2-j][3]+1
for i in range(H+2):
    for j in range(W+2):
        ans = max(ans, sum(L[i][j])-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
maps=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            maps[i][j]=-1
    
maps_l=[[0]*w for i in range(h)]
maps_r=[[0]*w for i in range(h)]
maps_u=[[0]*w for i in range(h)]
maps_d=[[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if maps[i][j]==-1:
            maps_l[i][j]=0
        elif j==0:
            maps_l[i][j]=1
        else:
            maps_l[i][j]=maps_l[i][j-1]+1

for i in range(h):
    for j in range(w-1,-1,-1):
        if maps[i][j]==-1:
            maps_r[i][j]=0
        elif j==w-1:
            maps_r[i][j]=1
        else:
            maps_r[i][j]=maps_r[i][j+1]+1

for j in range(w):
    for i in range(h):
        if maps[i][j]==-1:
            maps_d[i][j]=0
        elif i==0:
            maps_d[i][j]=1
        else:
            maps_d[i][j]=maps_d[i-1][j]+1

for j in range(w):
    for i in range(h-1,-1,-1):
        if maps[i][j]==-1:
            maps_u[i][j]=0
        elif i==h-1:
            maps_u[i][j]=1
        else:
            maps_u[i][j]=maps_u[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        if maps[i][j]!=-1:
            ans=max(ans,maps_u[i][j]+maps_d[i][j]+maps_r[i][j]+maps_l[i][j]-3)

print(ans)

Submission status: Time Limit Exceeded

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

tab=[[0 for i in range(w)] for q in range(h)]

cnt=0
for i in range(h):
    cnt=0
    for q in range(w):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for i in range(h):
    cnt=0
    for q in range(w-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt

print(max([max(col) for col in tab])-3)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces



H, W = na()
S = [ns() for _ in range(H)]
tmp = [[0] * W for _ in range(H)]

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

for j in range(W):
    ct = 0
    for i in range(H):
        if S[i][j] == '#':
            if ct != 0:
                for k in range(ct):
                   tmp[i-(k+1)][j] += ct - 1
            ct = 0
        else:
            ct += 1
    if ct != 0:
        for k in range(ct):
            tmp[i-k][j] += ct - 1

ans = -1
for i in range(H):
    for j in range(W):
        ans = max(ans, tmp[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

yoko = [[0]*W for _ in range(H)]
tate = [[0]*W for _ in range(H)]

def f(l):
    print("\n".join("".join(map(str, row)) for row in l))

for h in range(H):
    if S[h][0] == ".":
        yoko[h][0] = 1
    else:
        yoko[h][0] = 0

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

for h in range(H):
    for w in range(W-2, -1, -1):
        if S[h][w]=="." and S[h][w+1]==".":
            yoko[h][w] = yoko[h][w+1]

for w in range(W):
    if S[0][w] == ".":
        tate[0][w] = 1
    else:
        tate[0][w] = 0

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

for w in range(W):
    for h in range(H-2, -1, -1):
        if S[h][w]=="." and S[h+1][w]==".":
            tate[h][w] = tate[h+1][w]

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
b = ["#"*(W+2)]+["#"+input()+"#" for _ in range(H)]+["#"*(W+2)]

ans = 0

for rh in range(1, H+1):
    for rw in range(1, W+1):
        if b[rh][rw] == "#":
            continue

        x = 0

        i = 1
        while True:
            if b[rh-i][rw] == "#":
                x += i-1
                break
            i += 1
        
        i = 1
        while True:
            if b[rh+i][rw] == "#":
                x += i-1
                break
            i += 1
        
        i = 1
        while True:
            if b[rh][rw-i] == "#":
                x += i-1
                break
            i += 1
        
        i = 1
        while True:
            if b[rh][rw+i] == "#":
                x += i-1
                break
            i += 1
        
        ans = max(x, ans)

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(i, j):
  global S
  global H
  global W
  a = 1
  u, d, l, r = i, i, j, j
  while u > 0:
    u -= 1
    if S[u][j] == '.':
      a += 1
    else:
      break
  while d < H-1:
    d += 1
    if S[d][j] == '.':
      a += 1
    else:
      break
  while l > 0:
    l -= 1
    if S[i][l] == '.':
      a += 1
    else:
      break
  while r < W-1:
    r += 1
    if S[i][r] == '.':
      a += 1
    else:
      break
  return a
  
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      ans = max(ans, main(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
l1 = []
for i in range(H):
  s = str(input())
  S.append(s)
  tmp = []
  cnt = 0
  flag = False
  for j in s:
    if flag:
      if j == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if j == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l1.append(tmp)

l2 = []
for i in range(W):
  tmp = []
  cnt = 0
  flag = False
  for j in range(H):
    x = S[j][i]
    if flag:
      if x == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if x == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l2.append(tmp)

ans = [[0]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if (l1[i][j]>0) and (l2[j][i]>0):
      ans[i][j] = l1[i][j] + l2[j][i] - 1
    else:
      ans[i][j] = l1[i][j] + l2[j][i]
print(max(list(map(lambda x: max(x), ans))))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(i, j):
  global S
  global H
  global W
  a = 1
  u, d, l, r = i, i, j, j
  while u > 0:
    u -= 1
    if S[u][j] == '.':
      a += 1
    else:
      break
  while d < H-1:
    d += 1
    if S[d][j] == '.':
      a += 1
    else:
      break
  while l > 0:
    l -= 1
    if S[i][l] == '.':
      a += 1
    else:
      break
  while r < W-1:
    r += 1
    if S[i][r] == '.':
      a += 1
    else:
      break
  return a
  
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      ans = max(ans, main(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

rowGroups=UnionFind(H*W)
colGroups=UnionFind(H*W)

for i in range(H):
  for j in range(W):
    if j-1>=0 and S[i][j-1]=='.' and S[i][j]=='.':
      rowGroups.union(i*W+j,i*W+j-1)
    if i-1>=0 and S[i-1][j]=='.' and S[i][j]=='.':
      colGroups.union(i*W+j,(i-1)*W+j)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(rowGroups.size(W*i+j)+colGroups.size(W*i+j)-1,ans)
print(ans)

Submission status: Time Limit Exceeded

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

d = ((-1, 0), (1, 0), (0, -1), (0, 1))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        c = 1
        for dy, dx in d:
            y, x = i, j
            while True:
                y += dy
                x += dx
                if not(0 <= y < h) or not(0 <= x < w):
                    break
                if s[y][x] == '#':
                    break
                c += 1
        ans = max(ans, c)
print(ans)

Submission status: Time Limit Exceeded

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

S = [input() for _ in range(H)]

a = [[0] * W for _ in range(H)] # 右
b = [[0] * W for _ in range(H)] # 左
c = [[0] * H for _ in range(W)] # 上
d = [[0] * H for _ in range(W)] # 下

for x in range(H):
    for y in range(W):
        if S[x][y] == '#':
            a[x][y] = -1
        elif y > 0:
            a[x][y] = a[x][y-1] + 1
            
for x in range(H):
    for y in range(W-1,-1,-1):
        if S[x][y] == '#':
            b[x][y] = -1
        elif y < W-1:
            b[x][y] = b[x][y+1] + 1

for y in range(W):
    for x in range(H):
        if S[x][y] == '#':
            c[y][x] = -1
        elif x > 0:
            c[y][x] = c[y][x-1] + 1

for y in range(W):
    for x in range(H-1,-1,-1):
        if S[x][y] == '#':
            d[y][x] = -1
        elif x < H-1:
            d[y][x] = d[y][x+1] + 1

ans = 0

for x in range(H):
    for y in range(W):
        if S[x][y] != '#':
            ans = max(ans,a[x][y]+b[x][y]+c[y][x]+d[y][x]+1)

print(ans)

Submission status: Time Limit Exceeded

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

S = [input() for _ in range(H)]

a = [[0] * W for _ in range(H)] # 右
b = [[0] * W for _ in range(H)] # 左
c = [[0] * W for _ in range(H)] # 上
d = [[0] * W for _ in range(H)] # 下

for x in range(H):
    for y in range(W):
        if S[x][y] == '#':
            a[x][y] = -1
        elif y > 0:
            a[x][y] = a[x][y-1] + 1
            
for x in range(H):
    for y in range(W-1,-1,-1):
        if S[x][y] == '#':
            b[x][y] = -1
        elif y < W-1:
            b[x][y] = b[x][y+1] + 1

for y in range(W):
    for x in range(H):
        if S[x][y] == '#':
            c[x][y] = -1
        elif x > 0:
            c[x][y] = c[x-1][y] + 1

for y in range(W):
    for x in range(H-1,-1,-1):
        if S[x][y] == '#':
            d[x][y] = -1
        elif x < H-1:
            d[x][y] = d[x+1][y] + 1

ans = 0

for x in range(H):
    for y in range(W):
        if S[x][y] != '#':
            ans = max(ans,a[x][y]+b[x][y]+c[x][y]+d[x][y]+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
HW = [0] * H
for i in range(H):
  HW[i] = str(input())
  
#縦  
T = [[0] * W for i in range(H)]  
for i in range(H):#4000000
  now = 0
  for j in range(W):
    if HW[i][j] == "#":
      T[i][j] = 0
      now = 0
    else:
      now += 1
      T[i][j] = now
      
  now = 0    
  for j in range(1, W + 1):
    if T[i][-j] == 0:
      now = 0
    elif now == 0:
      now = T[i][-j]
    else:
      T[i][-j] = now
    #print(i, now)  
  
#print(T)

#横
Y = [[0] * W for i in range(H)]  
for j in range(W):#4000000
  now = 0
  for i in range(H):
    if HW[i][j] == "#":
      Y[i][j] = 0
      now = 0
    else:
      now += 1
      Y[i][j] = now
      
  now = 0    
  for i in range(1, H + 1):
    if Y[-i][j] == 0:
      now = 0
    elif now == 0:
      now = Y[-i][j]
    else:
      Y[-i][j] = now
    #print(i, now)      
#print(Y)

ans = 0
for i in range(H):
  for j in range(W):
    if T[i][j] != 0 and Y[i][j] != 0:
      ans = max(ans, T[i][j] + Y[i][j] - 1)
      
print(ans)