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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
field = [[0]*w for _ in range(h)]


for i in range(h):
    obs = []
    for x in range(w):
        if s[i][x] == '#':
            obs.append(x)
    if not obs:
        for x in range(w):
            field[i][x] += w
    for j in range(obs[0]):
        field[i][j] += obs[0]
    for x in range(len(obs)-1):
        for j in range(obs[x]+1, obs[x+1]):
            field[i][j] += obs[x+1]-obs[x]-1
    for j in range(obs[-1]+1, w):
        field[i][j] += w-obs[-1]-1


for j in range(w):
    obs = []
    for y in range(h):
        if s[y][j] == '#':
            obs.append(y)
    if not obs:
        for y in range(h):
            field[y][j] += h
    else:
        for i in range(obs[0]):
            field[i][j] += obs[0]
        for y in range(len(obs)-1):
            for i in range(obs[y]+1, obs[y+1]):
                field[i][j] += obs[y+1]-obs[y]-1
        for i in range(obs[-1]+1, h):
            field[i][j] += h-obs[-1]-1

# print(field)
print(max([max(field[i]) for i in range(h)])-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
field = [[0]*w for _ in range(h)]


for i in range(h):
    obs = []
    for x in range(w):
        if s[i][x] == '#':
            obs.append(x)
    for j in range(obs[0]):
        field[i][j] = obs[0]
    for x in range(len(obs)-1):
        for j in range(obs[x]+1, obs[x+1]):
            field[i][j] = obs[x+1]-obs[x]-1
    for j in range(obs[-1]+1, w):
        field[i][j] = w-obs[-1]-1


for j in range(w):
    obs = []
    for y in range(h):
        if s[y][j] == '#':
            obs.append(y)
    if not obs:
        for y in range(h):
            field[y][j] += h
    else:
        for i in range(obs[0]):
            field[i][j] += obs[0]
        for y in range(len(obs)-1):
            for i in range(obs[y]+1, obs[y+1]):
                field[i][j] += obs[y+1]-obs[y]-1
        for i in range(obs[-1]+1, h):
            field[i][j] += h-obs[-1]-1

# print(field)
print(max([max(field[i]) for i in range(h)])-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
LR=[[-2]*w for i in range(h)]
L=[[-2]*w for i in range(h)]
FB=[[-2]*w for i in range(h)]
B=[[-2]*w for i in range(h)]
ans=0



for i in range(h):
    start=0
    j = 0
    while j<w:
        if s[i][j]==".":
            start=j
            f=0
            tmp=w-1
            for k in range(j+1,w):
                if s[i][k]=="#":
                    tmp=k
                    f=1
                    break
            LRsize=k-j if f else k-j+1
            goal=k if f else k+1
            for t in range(j,goal):
                LR[i][t]=LRsize
            j=tmp+1
        else:
            j+=1
        # print(j)


for j in range(w):
    start=0
    i = 0
    while i<h:
        if s[i][j]==".":
            start=i
            f=0
            tmp=h-1
            for k in range(i+1,h):
                if s[k][j]=="#":
                    f=1
                    tmp=k
                    break

            LRsize=k-i if f else k-i+1
            goal=k if f else k+1
            for t in range(i,goal):
                FB[t][j]=LRsize
            i=tmp+1
        else:
            i+=1

for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans=max(ans,LR[i][j]+FB[i][j])
print(ans-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

def find(LI,i,j,p):
    data=[(0,1),(0,-1),(1,0),(-1,0)]
    if not (0<=i<h and 0<=j<w):
        LI[i][j]=-1
        return LI[i][j]

    if s[i][j]=="#":
        LI[i][j] = -1
        return LI[i][j]
        
    if LI[i][j]!=-2:
        return LI[i][j]
    else:
        LI[i][j]= find(LI, i+data[p][0], j+data[p][1], p)+1
        return LI[i][j]
    

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
R=[[-2]*w for i in range(h)]
L=[[-2]*w for i in range(h)]
F=[[-2]*w for i in range(h)]
B=[[-2]*w for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        find(R,i,j,0)
        find(L,i,j,1)
        find(F,i,j,2)
        find(B,i,j,3)
        if s[i][j]!="#":
            ans = max(ans, sum((R[i][j], L[i][j], F[i][j], B[i][j]))+1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import copy
import numpy as np

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

    data = [[[0, 0, 0, 0] for j in range(w)] for i in range(h)]
    # left = [[0 for j in range(w)] for i in range(h)]
    # right = copy.deepcopy(left)
    # up = copy.deepcopy(left)
    # down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] != "#":
                data[i][j][0] = (data[i][j-1][0] if j > 0 else 0) + 1
            if s[i][w-j-1] != "#":
                data[i][w-j-1][1] = (data[i][w-j][1] if j > 0 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] != "#":
                data[i][j][2] = (data[i-1][j][2] if i > 0 else 0) + 1
            if s[h-i-1][j] != "#":
                data[h-i-1][j][3] = (data[h-i][j][3] if i > 0 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = sum(data[i][j]) - 3
            # t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Runtime Error

Solution code:
import sys
import math
import numpy as np
import copy

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

    left = [[0 for j in range(w)] for i in range(h)]
    right = copy.deepcopy(left)
    up = copy.deepcopy(left)
    down = copy.deepcopy(left)

    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            left[i][j] = (left[i][j-1] if j > 0 else 0)+ 1

    for i in range(h):
        for j in range(w-1, -1, -1):
            if s[i][j] == "#":
                continue
            right[i][j] = (right[i][j+1] if j < w-1 else 0) + 1
    
    for j in range(w):
        for i in range(h):
            if s[i][j] == "#":
                continue
            up[i][j] = (up[i-1][j] if i > 0 else 0) + 1

    for j in range(w):
        for i in range(h-1, -1, -1):
            if s[i][j] == "#":
                continue
            down[i][j] = (down[i+1][j] if i < h-1 else 0) + 1

    maxx = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            maxx = max(maxx, t)

    print(maxx)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Runtime Error

Solution code:
import numpy as np

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

R = np.zeros((H, W), dtype=int)
L = 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):
    U[i] = (U[i-1] + 1) * S[i]
    D[-i-1] = (D[-i] + 1) * S[-i-1]

for i in range(W):
    L[:, i] = (L[:, i-1] + 1) * S[:, i]
    R[:, -i-1] = (R[:, -i] + 1) * S[-i-1]

print(np.max(R+L+U+D) - 3)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

int main(){
    int h,w;
    char maze[2000][2000];

    cin >> h >> w;

    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            cin >> maze[i][j];
        }
    }

    int h_li[2000];
    int w_li[2000];

    int memo1,memo_max;
 
    for (int i=0; i<h; i++){       //横列探索
        memo1 = 0;
        memo_max = 0;
        for (int j=0; j<w; j++){
            if (maze[i][j]=='#'){
                memo_max = max(memo1,memo_max);
                memo1 = 0;
            }
            if (maze[i][j]=='.'){
              memo1 += 1;  
            }
        }
        memo_max = max(memo1,memo_max);
        h_li[i] = memo_max;
    }

    for (int i=0; i<w; i++){       //縦列探索
        memo1 = 0;
        memo_max = 0;
        for (int j=0; j<h; j++){
            if (maze[j][i]=='#'){
                memo_max = max(memo1,memo_max);
                memo1 = 0;
            }
            if (maze[j][i]=='.'){
              memo1 += 1;  
            }
        }
        memo_max = max(memo1,memo_max);
        w_li[i] = memo_max;
    }

    int ans = 0;
    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            int ans_memo = w_li[j] + h_li[i] -1;
            ans = max(ans,ans_memo);
        }
    }


    cout << ans << endl;

/*
    for (int i=0; i<h; i++){
            cout << h_li[i] << endl;
        }
        cout << endl;
    for (int i=0; i<w; i++){
            cout << w_li[i] << endl;
        }
        cout << endl;
*/
    

    return 0;
}

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
lists=[]
for i in range(h):
    s=input()
    lists.append(s)
ylists=[]
for some in lists:
    some=some+"#"
    cnt=0
    add=[]
    for i in range(w+1):
        if some[i]=="#":
            if cnt==0:
                add.append(0)
                cnt=0
            else:
                add.extend([cnt]*cnt)
                add.append(0)
                cnt=0
                
        elif some[i]!="#":
            cnt+=1
    del add[-1]
    ylists.append(add)
    

            
lists1=[]
for i in range(w):
    for j in range(h):
        lists1[i][j]=lists[j][i]

    

tlists=[]
for some in lists1:
    some=some+"#"
    cnt=0
    add=[]
    for i in range(h+1):
        if some[i]=="#":
            if cnt==0:
                add.append(0)
                cnt=0
            else:
                add.extend([cnt]*cnt)
                add.append(0)
                cnt=0
                
        elif some[i]!="#":
            cnt+=1
    del add[-1]
    tlists.append(add)


listss=[]
for i in range(h):
    for j in range(w):
        if ylists[i][j]==0 or  tlists[j][i]==0:
            continue
        else:
            listss.append(ylists[i][j]+tlists[j][i]-1)
print(max(listss))

Submission status: Runtime Error

Solution code:
#129d
H,W = map(int, input().split()) #H,W<=2000≒2*10^3
#∴最大で4*10^6…シンプルな処理でないと死ぬ。

input_2d = [[None] * W for _ in range(H)]

processed_input_2d_w = [[None] * W for _ in range(H)]
processed_input_2d_h = [[None] * H for _ in range(W)]

ans = 0

def cont_quantificate(seq_list):
    stored_char = seq_list[0]
    stored_index = 0
    stored_count = 1
    
    ans = []
    
    if len(seq_list)!=1:
        for i in range(1,len(seq_list)):
            
            if seq_list[i] == stored_char:
                stored_count += 1
                
            else:
                if stored_char != "#":
                    ans.extend([stored_count for _ in range(stored_count)])
                    stored_count = 1
                    stored_char = seq_list[i]
                else:
                    ans.extend([0 for _ in range(stored_count)])
                    stored_count = 1
                    stored_char = seq_list[i]
                    
        if stored_char != "#":
            ans.extend([stored_count for _ in range(stored_count)])
        else:
            ans.extend([0 for _ in range(stored_count)]) 
            
        return ans
    else:
        if stored_char != "#":
            ans = [1]
        else:
            ans = [0]
        return ans

#読み込みつつ、横方向の処理
for i in range(H):
    #読み込み
    input_row = str(input())
    input_2d[i] = [input_row[i] for i in range(len(input_row))]
    #横方向で連続している数を求める
    processed_input_2d_w[i] = cont_quantificate(input_row)

print("input")
print(input_2d)
print("横方向")
print(processed_input_2d_w)
    
#縦方向に処理する
for i in range(W):
    #縦方向で連続している数を求める
    processed_input_2d_h[i] = cont_quantificate([row[i] for row in input_2d])
    
print("縦方向")
print(processed_input_2d_h)

#回答を求める
for i in range(H):
    for j in range(W):
        ans[i][j] = processed_input_2d_w[i][j] + processed_input_2d_h[j][i]
        
print(ans)

Submission status: Runtime Error

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

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

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

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

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

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)

Submission status: Runtime Error

Solution code:
import numpy as np
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
table = np.zeros((H , W))
done = np.zeros((H , W))
max = 0
print(s[0][1])

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            continue
        if done[i][j] == 1:
            continue
        l = 0
        while j + l < W:
            if s[i][j + l] == "#":
                break
            l += 1
        for k in range(l):
            table[i][j + k] += l
            done[i][j+k] = 1
print(table)
done = np.zeros((H , W))
for j in range(W):
    for i in range(H):
        if s[i][j] == "#":
            continue
        if done[i][j] == 1:
            continue
        l = 0
        while i + l < H:
            if s[i + l][j] == "#":
                break
            l += 1
        for k in range(l):
            table[i + k][j] += l
            done[i + k][j] = 1
            if table[i + k][j] > max:
                max = table[i + k][j]

print(table)
print(int(max - 1))

Submission status: Runtime Error

Solution code:
wakarimasendesitaaaaaaaaaaaa
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAA!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Submission status: Runtime Error

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

l=[[[-1,-1] for _ in range(W)] for _ in range(H)]

def xp(x,y):
  global xn
  if x>=W:
    pass
  elif field[y][x]=="#":
    l[y][x][0]=0
  else:
    xn+=1
    xp(x+1,y)
    l[y][x][0]=xn


def yp(x,y):
  global yn
  if y>=H:
    pass
  elif field[y][x]=="#":
    l[y][x][1]=0
  else:
    yn+=1
    yp(x,y+1)
    l[y][x][1]=yn


for j in range(H):
  for i in range(W):
    xn=0
    yn=0
    if l[j][i][0]==-1:
      xp(i,j)
    if l[j][i][1]==-1:
      yp(i,j)

print(max([max([i[0]+i[1]-1 for i in j]) for j in l]))

Submission status: Runtime Error

Solution code:
from itertools import groupby

H, W = map(int,input().split())
S = []

max_row_range = [[None, None], [None, None]]
max_row_num = -float('inf')
for j in range(H):
  row = [0 if s=='.' else 1 for s in input()]
  S.append(row)
  
  i = 0
  for key, value in groupby(row):
    value_len = len(list(value))
    if key == 0 and max_row_num < value_len:
      max_row_range = [[i,j],[i+value_len,j]]
      max_row_num = value_len
    i += value_len

max_col_range = [[None, None], [None, None]]
max_col_num = -float('inf')
for i, col in enumerate(zip(*S)):
  if i < max_row_range[0][0] or i < max_row_range[0][1]: continue 
    
  j = 0
  for key, value in groupby(col):
    value_len = len(list(value))
    if key == 0 and max_col_num < value_len:
      max_col_range = [[i,j],[i+value_len,j]]
      max_col_num = value_len
    j += value_len
    
print(max_row_range[1][0]-max_row_range[0][0]+max_col_range[1][0]-max_col_range[0][0]-1)

Submission status: Runtime Error

Solution code:
from functools import reduce
import sys
import numpy as np


mod = 10 ** 9 + 7
buffer = sys.stdin.buffer
h, w = map(int, buffer.readline().split())
s = np.frombuffer(buffer.read(h*(w+1)), dtype='B') == ord('.')
s = s.reshape((h, w+1))[:, :-1]
l = np.empty((h, w), dtype='i4')
r = np.empty((h, w), dtype='i4')
u = np.empty((h, w), dtype='i4')
d = np.empty((h, w), dtype='i4')
l[:, 0] = s[:, 0]
for i in range(1, w):
    l[:, i] = (l[:, i-1] + 1) * s[:, i]
r[:, -1] = s[:, -1]
for i in range(1, w):
    r[:, -1-i] = (r[:, -i] + 1) * s[:, -1-i]
u[0] = s[0]
for i in range(a, h):
    u[i] = (u[i-1] + 1) * s[i]
d[-1] = s[-1]
for i in range(1, h):
    d[-1-i] = (d[-i] + 1) * s[-1-i]
score = l + r + u + d - 3
print(int(score.max()))

Submission status: Runtime Error

Solution code:
from functools import reduce
import sys
import numpy as np


mod = 10 ** 9 + 7
buffer = sys.stdin.buffer
h, w = list(map(int, buffer.readline().split()))
s = np.frombuffer(buffer.read(h*(w+1)), dtype='B') == ord('.')
s = s.reshape((h, w+1))[:, :-1]
l = np.empty((h, w), dtype='i4')
r = np.empty((h, w), dtype='i4')
u = np.empty((h, w), dtype='i4')
d = np.empty((h, w), dtype='i4')
l[:, 0] = s[:, 0]
for i in range(1, w):
    l[:, i] = (l[:, i-1] + 1) * s[:, i]
r[:, -1] = s[:, -1]
for i in range(1, w):
    r[:, -1-i] = (r[:, -i] + 1) * s[:, -1-i]
u[0] = s[0]
for i in range(a, h):
    u[i] = (u[i-1] + 1) * s[i]
d[-1] = s[-1]
for i in range(1, h):
    d[-1-i] = (d[-i] + 1) * s[-1-i]
score = l + r + u + d - 3
print(int(score.max()))

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
d=[]
field=[]
fie=[]
for _ in range(h):
	s=input()
	d.append(s)
	cnt=0
	yoko=[]
	for i in range(w):
		if s[i]=="#":
			yoko.append(cnt)
			cnt=0
		else:
			cnt+=1
	if cnt>0:
		yoko.append(cnt)
	yoko.append(0)
	yoko.append(0)
	field.append(yoko)
for i in range(w):
	tate=[]
	cnt=0
	for j in range(h):
		if d[j][i]=="#":
			tate.append(cnt)
			cnt=0
		else:
			cnt+=1
	if cnt>0:
		tate.append(cnt)
	tate.append(0)
	tate.append(0)
	fie.append(tate)
for i in range(h):
	for j in range(len(field[i])-2):
		if field[i][j]>0 and field[i][j+1]>0:
			field[i].insert(j+1,0)
		elif field[i][j]>=0 and field[i][j+1]==0 and field[i][j+2]==0:
			field[i].insert(j+1,0)
for i in range(w):
	for j in range(len(fie[i])-2):
		if fie[i][j]>0 and fie[i][j+1]>0:
			fie[i].insert(j+1,0)
		elif fie[i][j]>=0 and fie[i][j+1]==0 and fie[i][j+2]==0:
			fie[i].insert(j+1,0)
ans=[[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
	k=0
	cn=0
	for j in range(w):
		if field[i][k]==0:
			k+=1
			continue
		else:
			ans[i][j]+=field[i][k]
			cn+=1
		if cn==field[i][k]:
			cn=0
			k+=1
for i in range(w):
	k=0
	cn=0
	for j in range(h):
		if fie[i][k]==0:
			k+=1
			continue
		else:
			ans[j][i]+=fie[i][k]
			cn+=1
		if cn==fie[i][k]:
			cn=0
			k+=1
M=0
for i in range(h):
	for j in range(w):
		M=max(ans[i][j],M)
print(M-1)

Submission status: Runtime Error

Solution code:
import numpy as np
H, W = map(int, input().split())
S = []
ij = np.zeros((H,W), dtype=int)    # .の連続数を格納用

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-h - 1] = (D[-h] + 1) * S[-h - 1]
for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -w - 1] = (R[:, -w] + 1) * S[: -w - 1]#print(L)
print(np.max(U + D + L + R) - 3)

Submission status: Runtime Error

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

S = [input() for _ in range(H)]
memo = [[[-1] * 4 for _ in range(W)] for _ in range(H)]

D = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def walk(h, w, d):
    if not (0 <= h < H and 0 <= w < W):
        return 0

    if memo[h][w][d] >= 0:
        return memo[h][w][d]

    if S[h][w] == '#':
        for i in range(4):
            memo[h][w][i] = 0
        return 0
    v = walk(h + D[d][0], w + D[d][1], d)
    memo[h][w][d] = v + 1
    return memo[h][w][d]


def solve():
    ans = 0
    for h in range(H):
        for w in range(W):
            tmp = 0
            for d in range(4):
                tmp += walk(h, w, d)
            ans = max(ans, tmp - 3)
    print(ans)

    # for i in range(H):
    #     print(memo[i])


solve()

Submission status: Runtime Error

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

dp=[[[-1 for i in range(4)] for j in range(w)] for k in range(h)]
  
def cnt_l(i,j):
  if dp[i][j][0]>=0:
    return dp[i][j][0]
  elif j==0:
    dp[i][j][0]=0
    return 0
  elif s[i][j-1]=='.':
    dp[i][j][0]=cnt_l(i,j-1)+1
    return cnt_l(i,j-1)+1
  else:
    dp[i][j][0]=0
    return 0

def cnt_r(i,j):
  if dp[i][j][1]>=0:
    return dp[i][j][1]
  elif j==w-1:
    dp[i][j][1]=0
    return 0
  elif s[i][j+1]=='.':
    dp[i][j][1]=cnt_r(i,j+1)+1
    return cnt_r(i,j+1)+1
  else:
    dp[i][j][1]=0
    return 0  

def cnt_u(i,j):
  if dp[i][j][2]>=0:
    return dp[i][j][2]
  elif i==0:
    dp[i][j][2]=0
    return 0
  elif s[i-1][j]=='.':
    dp[i][j][2]=cnt_u(i-1,j)+1
    return cnt_u(i-1,j)+1
  else:
    dp[i][j][2]=0
    return 0

def cnt_d(i,j):
  if dp[i][j][3]>=0:
    return dp[i][j][3]
  elif i==h-1:
    dp[i][j][3]=0
    return 0
  elif s[i+1][j]=='.':
    dp[i][j][3]=cnt_d(i+1,j)+1
    return cnt_d(i+1,j)+1
  else:
    dp[i][j][3]=0
    return 0
  
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      ans=max(ans,cnt_l(i,j)+cnt_r(i,j)+cnt_u(i,j)+cnt_d(i,j)+1)
print(ans)

Submission status: Runtime Error

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

max_light = 0


def search(x, y, dir):
    if x < 0 or y < 0 or y >= h or x >= w:
        return 0
    if s[y][x] == '#':
        return 0
    if dir == 0:
        return 1 + search(x, y - 1, dir)
    if dir == 1:
        return 1 + search(x + 1, y, dir)
    if dir == 2:
        return 1 + search(x, y + 1, dir)
    if dir == 3:
        return 1 + search(x - 1, y, dir)


def light_search(x, y):
    return search(x, y, 0) + search(x, y, 1) + search(x, y, 2) + search(x, y, 3)


for i in range(w):
    for j in range(h):
        max_light = max(max_light, light_search(i, j))


print(max_light-3)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = [[0,1], [0,-1],[1,0], [-1,0]]

def bfs(b, a):
  light = [[0 for _ in range(w)] for _ in range(h)]
  q = deque([(b, a, (0, 1, 2, 3))])
  ans = 0
  while q:
    y, x, direction= q.popleft()
    light[y][x] = 1
    ans += 1
    
    for i in direction:
      next_y = y + moves[i][0]
      next_x = x + moves[i][1]
      if 0 <= next_y < h and 0 <= next_x < w and s[next_y][next_x] == '.' and light[next_y][next_x] == 0:
        q.append([next_y, next_x, [i]])
  return ans
bfs(2, 5)
final_ans = 0
for i in range(h):
  for j in range(w):
    final_ans = max(final_ans, bfs(i, j))

print(final_ans)

Submission status: Runtime Error

Solution code:
#00:27
h,w = map(int,input().split())
raw = []
for _ in range(h):
  raw.append(input())
ver = [[] for _ in range(w)]
hrz = [[] for _ in range(w)]
for x in range(h):
  st = 0
  for y in range(w):
    if raw[x][y] == '#':
      for k in range(st,y):
        ver[x].append(y-st)
      ver[x].append(0)
      st = y + 1
  for k in range(st,w):
    ver[x].append(w-st)
#print(ver)
for y in range(w):
  st = 0
  for x in range(h):
    if raw[x][y] == '#':
      for k in range(st,x):
        hrz[k].append(x-st)
      hrz[x].append(0)
      st = x + 1
  for k in range(st,h):
    hrz[k].append(h-st)
#print(hrz)
ans = 0
for x in range(h):
  for y in range(w):
    ans = max(ans,ver[x][y]+hrz[x][y]-1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1 = np.full((2000,2000),-1)
dp2 = np.full((2000,2000),-1)
dp3 = np.full((2000,2000),-1)
dp4 = np.full((2000,2000),-1)





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

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

dp1 = dp1+dp2+dp3+dp4

max = max(1,np.max(dp1)-3)

print(int(max))

Submission status: Runtime Error

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

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

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

ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)

Submission status: Runtime Error

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [str(input().rstrip('\n')) for _ in range(h)]
    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 s[i][j] == "#":
                L[i][j] = 0
            else:
                if i == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i - 1][j] + 1
            if s[-i-1][j] == "#":
                R[-i-1][j] = 0
            else:
                if i == 0:
                    R[-i-1][j] = 1
                else:
                    R[-i-1][j] = R[-i][j] + 1
            if s[i][j] == "#":
                U[i][j] = 0
            else:
                if j == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i][j-1] + 1
            if s[i][-j-1] == "#":
                D[i][-j-1] = 0
            else:
                if j == 0:
                    D[i][-j-1] = 1
                else:
                    Ds
        for j in range(w):
            mn = max(mn, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)
    print(mn)


if __name__ == '__main__':
    slove()

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
S = np.array([list(input().rstrip()) for _ in range(H)]) == '.'
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
for h in range(1, H):
    U[h] = (U[h - 1] + 1) * S[h - 1]
for h in reversed(range(H - 1)):
    D[h] = (D[h + 1] + 1) * S[h + 1]
for w in range(1, W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w - 1]
for w in reversed(range(W - 1)):
    R[:, w] = (R[:, w + 1] + 1) * S[:, w + 1]
print(max((U+D+L+R) * S) + 1)