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
input = sys.stdin.readline

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

ww=[[0]*w for i in range(h)]
www=[0]*w
for i in range(h):
    jsum=0
    jcnt=1
    jj=[0]*w
    for j in range(w):
        if s[i][j]==".":
            www[j]=jcnt
            if j<w-1 and s[i][j+1]=="#":
                jcnt+=1
            jsum+=1
        else:
            if jsum!=0:
                jj[jcnt-1]=jsum
            jsum=0
    jcnt+=1
    jj[jcnt-1]=jsum
            
    for j in range(w):
        if s[i][j]==".":
            ww[i][j]=jj[www[j]]
                
hh=[[0]*w for i in range(h)]
hhh=[0]*h
for j in range(w):
    isum=0
    icnt=1
    ii=[0]*h
    for i in range(h):
        if s[i][j]==".":
            hhh[i]=icnt
            if i<h-1 and s[i+1][j]=="#":
                icnt+=1
            isum+=1
        else:
            if isum!=0:
                ii[icnt-1]=isum
            isum=0
    icnt+=1
    ii[icnt-1]=isum
            
    for i in range(h):
        if s[i][j]==".":
            hh[i][j]=ii[hhh[i]]
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    si=input()
    s[i]=si
"""
h,w=4,6
s=[['#', '.', '.', '#', '.', '.'], ['.', '.', '.', '.', '.', '#'], ['.', '.', '.', '.', '#', '.'], ['#', '.', '#', '.', '.', '.']]    
"""
ww=[[0]*w for i in range(h)]
#www=[[0]*w for i in range(h)]
www=[0]*w
for i in range(h):
    jsum=0
    jcnt=1
    jj=[0]*w
    for j in range(w):
        if s[i][j]==".":
#            www[i][j]=jcnt
            www[j]=jcnt
            if j<w-1 and s[i][j+1]=="#":
                jcnt+=1
            jsum+=1
        else:
#            print(jsum,jst,jed)
            if jsum!=0:
                jj[jcnt-1]=jsum
            jsum=0
    jcnt+=1
    jj[jcnt-1]=jsum
            
    for j in range(w):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            ww[i][j]=jj[www[j]]
#    print(jj)
                
hh=[[0]*w for i in range(h)]
hhh=[0]*h
for j in range(w):
    isum=0
    icnt=1
    ii=[0]*w
    for i in range(h):
        if s[i][j]==".":
#            www[i][j]=jcnt
            hhh[i]=icnt
            if i<h-1 and s[i+1][j]=="#":
                icnt+=1
            isum+=1
        else:
#            print(jsum,jst,jed)
            if isum!=0:
                ii[icnt-1]=isum
            isum=0
    icnt+=1
    ii[icnt-1]=isum
            
    for i in range(h):
        if s[i][j]==".":
#            ww[i][j]=jj[www[i][j]]
            hh[i][j]=ii[hhh[i]]
#    print(jj)
            
ijmax=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ijmax=max(ijmax,ww[i][j]+hh[i][j]-1)

print(ijmax)

Submission status: Runtime Error

Solution code:
import numpy as np

# H,W = [3,4]
H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
	D = list(input_[1+h])
    for w in range(W):
        if D[w] =='#':
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h =  np.zeros((H,W))

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_h[d_h][o_st+1:o_ed] = o_ed-1 - o_st
    
Lamp_w =  np.zeros((W,H))
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_w[d_w][o_st+1:o_ed] = o_ed-1 - o_st
        
Lamp = Lamp_w.T + Lamp_h

print(int(Lamp.max()-1))

Submission status: Runtime Error

Solution code:
import numpy as np

# H,W = [3,4]
H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
	D = list(input_[1+h])
    for w in range(W):
        if D[w] =='#':
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h =  np.zeros((H,W))

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_h[d_h][o_st+1:o_ed] = o_ed-1 - o_st
    
Lamp_w =  np.zeros((W,H))
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_w[d_w][o_st+1:o_ed] = o_ed-1 - o_st
        
Lamp = Lamp_w.T + Lamp_h

print(int(Lamp.max()-1))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  int h,w;
  cin >> h >> w;
  vector<vector<int>> maze(h,vector<int>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      char c;
      cin >> c;
      if(c == '.'){
        maze[i][j] = 1;
      }else{
        maze[i][j] = 0;
      }
    }
  }
  
  vector<vector<int>> right(h,vector<int>(w));
  vector<vector<int>> left(h,vector<int>(w));
  vector<vector<int>> up(h,vector<int>(w));
  vector<vector<int>> down(h,vector<int>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(maze[i][j] == 0) continue;
      if(j==0){
        left[i][j] = 1;
      }else{
        left[i][j] = left[i][j-1] + 1;
      }
      if(i==0){
        up[i][j] = 1;
      }else{
        up[i][j] = up[i-1][j] + 1;
      }
    }
  }
  
  for(int i=h-1;i>=0;i--){
    for(int j=w-1;j>=0;j--){
      if(maze[i][j] == 0) continue;
      if(j==w-1){
        right[i][j] = 1;
      }else{
        right[i][j] = right[i][j+1] + 1;
      }
      if(i==h-1){
        down[i][j] = 1;
      }else{
        down[i][j] = down[i+1][j] + 1;
      }
    }
  }
  
  //vector<vector<int>> dp(h,vector<int>(w));
  int ans=0;
  
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      int light=right[i][j]+left[i][j]+up[i][j]+down[i][j]-3;
      if(ans < light){
        ans = light;
      }
    }
  }
  
  cout << ans << endl;
  
  return(0);
}

Submission status: Runtime Error

Solution code:
from collections import deque
f = open("/Users/naoki/Documents/Atcoder/input.txt")

H,W = map(int,f.readline().split())
Ss = [str(f.readline()) for _ in range(H)]

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

for i in range(H):
    for j in range(W):
        if Ss[i][j] == "#" or yoko[i][j] != 0:
            continue
        else:
            paths = [[i,j]]
            temp = 1
            for k in range(j+1, W):
                if Ss[i][k] == ".":
                    temp+=1
                    paths.append([i,k])
                else:
                    break
            for path in paths:
                yoko[path[0]][path[1]] = temp

for i in range(H):
    for j in range(W):
        if Ss[i][j] == "#" or tate[i][j] != 0:
            continue
        else:
            paths = [[i,j]]
            temp = 1
            for k in range(i+1, H):
                if Ss[k][j] == ".":
                    temp+=1
                    paths.append([k,j])
                else:
                    break
            for path in paths:
                tate[path[0]][path[1]] = temp

answer = 0
for i in range(H):
    for j in range(W):
        if answer < tate[i][j]+yoko[i][j]-1:
            answer = tate[i][j]+yoko[i][j]-1
print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque
f = open("/Users/naoki/Documents/Atcoder/input.txt")

H,W = map(int,f.readline().split())
Ss = [str(f.readline()) for _ in range(H)]

directions = [[-1,0],
              [0,-1],
              [1,0],
              [0,1]]

answer = 0
import copy
for i in range(H):
    for j in range(W):
        if Ss[i][j]==".":
            todo = deque([[i,j]])
        else:
            continue
        candidate = 0
        while len(todo) > 0:
            base = todo.pop()
            candidate += 1
            
            for direction in directions:
                checking = copy.deepcopy(base)
                for k in range(max(H,W)):
                    checking = [checking[0]+direction[0],checking[1]+direction[1]]
                    if checking[0] < 0 or checking[0] >= H or checking[1] < 0 or checking[1] >= W:
                        break
                    if Ss[checking[0]][checking[1]] == "#":
                        break
                    candidate += 1
        if candidate > answer:
            answer = candidate
print(answer)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
s=[]
d=[]
for i in range(h):
    s.append(list(input()))
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            d.append((i,j))
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            l,r=-1,w-1
            t,u=-1,h-1
            tmp=0
            for x,y in d:
                if x==i:
                    if l<y<j:
                        l=y
                    if j<y<r:
                        r=y
                if y==j:
                    if t<x<i:
                        t=x
                    if i<x<u:
                        u=x
            tmp=r-l+u-t-1
            if tmp>ans:
                ans=tmp
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np


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


def main():
    h, w = map(int, read().split())
    s = np.array([[i == "." for i in read()] for _ in range(h)], dtype=int)
    left = s.copy()
    right = s.copy
    up = s.copy
    down = s.copy
    for i in range(w - 1):
        left[:, i + 1] = (left[:, i] + 1) * s[:, i + 1]
        right[:, -i - 2] = (right[:, -i - 1] + 1) * s[:, -i - 2]
    for i in range(h - 1):
        up[i + 1] = (up[i] + 1) * s[i + 1]
        down[-i - 2] = (down[-i - 1] + 1) * s[-i - 2]
    print((left + right + up + down).max() - 3)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
S = []
for i in range(H):
    S.append(list(input()))
L = [[] for _ in range(H)]
R = L.copy
D = L.copy
U = L.copy
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            L[i].append(0)
        elif j == 0:
            L[i].append(1)
        else:
            L[i].append(L[i][-1] + 1)
for i in range(H):
    for j in range(-1,-W-1,-1):
        if S[i][j] == '#':
            R[i].insert(0,0)
        elif j == -1:
            R[i].append(1)
        else:
            R[i].insert(0,R[i][0] + 1)
for i in range(W):
    for j in range(H):
        if S[j][i] == '#':
            U[j].append(0)
        elif j == 0:
            U[j].append(1)
        else:
            U[j].append(U[j-1][-1] + 1)
for i in range(W):
    for j in range(-1,-H-1,-1):
        if S[j][i] == '#':
            D[j].append(0)
        elif j == -1:
            D[j].append(1)
        else:
            D[j].append(D[j+1][-1] + 1)
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,U[i][j]+D[i][j]+L[i][j]+R[i][j]-3)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
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())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]

imos1 = [[0 for j in range(w + 1)] for i in range(h)]
imos2 = [[0 for j in range(w)] for i in range(h + 1)]

cnt1 = 0
start1 = None
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j == 0 or s[i][j - 1] == "#":
                start1 = j
                cnt1 = 1
            else:
                cnt1 += 1
        elif j == 0 or s[i][j - 1] == "#":
            continue
        else:
            imos1[i][start1] = cnt1
            imos1[i][j] = -cnt1
            cnt1 = 0
    if s[i][-1] == ".":
        imos1[i][start1] = cnt1
        imos1[i][-1] = -cnt1
    start1 = None
    cnt1 = 0
for i in range(h):
    for j in range(1, w):
        imos1[i][j] += imos1[i][j - 1]
# for i in range(h):
    # print(*imos1[i][:-1])
# print(imos1)
# print()

cnt2 = 0
start2 = None
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            if j == 0 or s[j - 1][i] == "#":
                start2 = j
                cnt2 = 1
            else:
                cnt2 += 1
        elif j == 0 or s[j][i - 1] == "#":
            continue
        else:
            imos2[start2][i] = cnt2
            imos2[j][i] = -cnt2
            cnt2 = 0
    if s[h - 1][i] == ".":
        imos2[start2][i] = cnt2
        imos2[h][i] -= cnt2
    start2 = None
    cnt2 = 0
for i in range(w):
    for j in range(1, h):
        imos2[j][i] += imos2[j - 1][i]
# for i in range(h):
    # print(*imos2[i])
# print(imos2)

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        ans = max(ans, imos1[i][j] + imos2[i][j] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
u = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if g[i][j] == '.':
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1]+1
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j]+1
for i in reversed(range(h)):
  for j in reversed(range(w)):
    if g[i][j] == '.':
      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):
    ans = max(l[i][j]+r[i][j]+u[i][j]+d[i][j]-3,ans)
print(ans)

Submission status: Runtime Error

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)]

l1 = [[0 for i in range(w)] for i in range(h)]
for i in range(h):
  for j in range(w):
    c = s[i][j]
    if c==".":
      l1[i][j] = ko(s[i],w,j)
      
l2 = [[0 for i in range(h)] for i in range(w)]
for i in range(w):
  for j in range(h):
    c = s[i][j]
    if c==".":
      l2[i][j] =  ko(s1[j],h,i)
      

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

Submission status: Runtime Error

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

maze = [[] for _  in range(H)]
for i in range(H):
    maze[i] = np.array(list(input())) == "."
maze = np.array(maze)

up = np.zeros((H,W),dtype=int)
down = np.zeros((H,W),dtype=int)
right = np.zeros((H,W),dtype=int)
left = np.zeros((H,W),dtype=int)

for i in range(H):
    down[i] = (down[i-1] + 1) *maze[i] 
    up[-(i+1)] = (up[-i]+1)*maze[-(i+1)]
    
for j in range(W):
    left[j] = (left[j-1]+1)*maze[:,j]
    right[-(j+1)] = (right[-j]+1)*maze[:,-(j+1)]
print(np.max(up+down+right+left)-3)

Submission status: Runtime Error

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

maze = [[] for _  in range(H)]
for i in range(H):
    maze[i] = np.array(list(input())) == "."
maze = np.array(maze)

up = np.zeros((H,W),dtype=int)
down = np.zeros((H,W),dtype=int)
right = np.zeros((H,W),dtype=int)
left = np.zeros((H,W),dtype=int)

for i in range(H):
    down[i] = (down[i-1] + 1) *maze[i] 
    up[-(i+1)] = (up[-i]+1)*maze[-(i+1)]
for j in range(W):
    left[j] = (left[j-1]+1)*maze[j]
    right[-(j+1)] = (right[-j]+1)*maze[-(j+1)]
print(np.max(up+down+right+left)-3)

Submission status: Runtime Error

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

maze = [[] for _  in range(H)]
for i in range(H):
    maze[i] = np.array(list(input())) == "."
maze = np.array(maze)

up = np,zeros((H,W),dtype=int)
down = np,zeros((H,W),dtype=int)
right = np,zeros((H,W),dtype=int)
left = np,zeros((H,W),dtype=int)

for i in range(H):
    down[i] = (down[i-1] + 1) *maze[i] 
    up[-(i+1)] = (up[-i]+1)*maze[-(i+1)]
for j in range(W):
    left[j] = (left[j-1]+1)*maze[j]
    right[-(j+1)] = (right[-j]+1)*maze[-(j+1)]
print(np.max(up+down+right+left)-3)

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)


def f(n):
    if memo[n] > 0:
        return memo[n]
    memo[n] = f(n - 1) + f(n - 2)
    return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [1, 1] + [-1] * N
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)

Submission status: Runtime Error

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

maze = [[] for _ in range(H)]
for i in range(H):
    maze[i] = np.array(list(input())) == "."
maze = np.array(maze)

up = np.zeros((H, W), dtype=int)
down = np.zeros((H, W), dtype=int)
right = np.zeros((H, W), dtype=int)
left = np.zeros((H, W), dtype=int)

for i in range(H):
    up[i] = (up[i-1] + 1)*maze[i]
    down[-i] = (down[-(i-1)] + 1)*maze[-i] 
    
#print(up)
#print(down)

for i in range(W):
    right[:, i] = (right[:, i-1] + 1)*maze[:, i]
    left[:, -i] = (left[:, -(i-1)] + 1)*maze[:, -i]

print(np.max(up+down+right+left)-4)

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
matrix = [list(raw_input()) for _ in range(n)]
dpleft = [[0 for j in range(m)] for i in range(n)]
dpright = [[0 for j in range(m)] for i in range(n)]
dpup = [[0 for j in range(m)] for i in range(n)]
dpdown = [[0 for j in range(m)] for i in range(n)]

for i in range(n):
	cumul = 0
	for j in range(m):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpleft[i][j] = cumul
			cumul +=1

	cumul = 0
	for j in range(m-1,-1,-1):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpright[i][j] = cumul
			cumul +=1

for j in range(m):
	cumul = 0
	for i in range(n):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpup[i][j] = cumul
			cumul +=1

	cumul = 0
	for i in range(n-1,-1,-1):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpdown[i][j] = cumul
			cumul +=1
r = 0
for i in range(len(matrix)):
	for j in range(len(matrix)):
		if matrix[i][j] != '#':
			r = max(r, 1 + dpleft[i][j] + dpright[i][j] + dpdown[i][j] + dpup[i][j])
print r

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
matrix = [list(raw_input()) for _ in range(n)]
dpleft = [[0 for j in range(m)] for i in range(n)]
dpright = [[0 for j in range(m)] for i in range(n)]
dpup = [[0 for j in range(m)] for i in range(n)]
dpdown = [[0 for j in range(m)] for i in range(n)]
for l in matrix:
	print l
for i in range(n):
	cumul = 0
	for j in range(m):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpleft[i][j] = cumul
			cumul +=1

	cumul = 0
	for j in range(m)[::-1]:
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpright[i][j] = cumul
			cumul +=1

for j in range(m):
	cumul = 0
	for i in range(n):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpup[i][j] = cumul
			cumul +=1

	cumul = 0
	for i in range(n)[::-1]:
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpdown[i][j] = cumul
			cumul +=1
r = 0
for i in range(len(matrix)):
	for j in range(len(matrix)):
		if matrix[i][j] == '.':
			r = max(r, 1 + dpleft[i][j] + dpright[i][j] + dpdown[i][j] + dpup[i][j])
print r

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
matrix = [raw_input() for _ in range(n)]
dpleft = [[0 for j in range(m)] for i in range(n)]
dpright = [[0 for j in range(m)] for i in range(n)]
dpup = [[0 for j in range(m)] for i in range(n)]
dpdown = [[0 for j in range(m)] for i in range(n)]

for i in range(len(matrix)):
	cumul = 0
	for j in range(len(matrix[i])):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpleft[i][j] = cumul
			cumul +=1

	cumul = 0
	for j in range(len(matrix[i]))[::-1]:
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpright[i][j] = cumul
			cumul +=1

for j in range(len(matrix[0])):
	cumul = 0
	for i in range(len(matrix)):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpup[i][j] = cumul
			cumul +=1

	cumul = 0
	for i in range(len(matrix))[::-1]:
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpdown[i][j] = cumul
			cumul +=1
r = 0
for i in range(len(matrix)):
	for j in range(len(matrix)):
		if matrix[i][j] == '.':
			r = max(r, 1 + dpleft[i][j] + dpright[i][j] + dpdown[i][j] + dpup[i][j])
print r

Submission status: Runtime Error

Solution code:
import collections
n,m = map(int, raw_input().split(' '))
matrix = [raw_input() for _ in range(n)]
dpleft = [[0 for j in range(m)] for i in range(n)]
dpright = [[0 for j in range(m)] for i in range(n)]
dpup = [[0 for j in range(m)] for i in range(n)]
dpdown = [[0 for j in range(m)] for i in range(n)]

for i in range(len(matrix)):
	cumul = 0
	for j in range(len(matrix[i])):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpleft[i][j] = cumul
			cumul +=1

	cumul = 0
	for j in range(len(matrix[i]))[::-1]:
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpright[i][j] = cumul
			cumul +=1

for j in range(len(matrix[0])):
	cumul = 0
	for i in range(len(matrix)):
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpup[i][j] = cumul
			cumul +=1

	cumul = 0
	for i in range(len(matrix))[::-1]:
		if matrix[i][j] == '#':
			cumul = 0
		else:
			dpdown[i][j] = cumul
			cumul +=1
for i in range(len(matrix)):
	for j in range(len(matrix)):
		if matrix[i][j] == '.':
			m = max(m, 1 + dpleft[i][j] + dpright[i][j] + dpdown[i][j] + dpup[i][j])
print m

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    h, w = map(int, input().split())
    col = [[0, w + 1] for _ in range(h)]
    row = [[0, h + 1] for _ in range(w)]
    for i in range(h):
        s = list(input()[:-1].decode())
        for j in range(w):
            if s[j] == '#':
                col[i].append(j + 1)
                row[j].append(i + 1)

    cc = [[0] * (w + 2) for _ in range(h)]
    rc = [[0] * (h + 2) for _ in range(w)]

    for i in range(h):
        col[i].sort()
        for j in range(len(col[i]) - 1):
            cc[i][col[i][j] + 1:col[i][j + 1]] = [col[i][j + 1] - col[i][j] - 1] * (col[i][j + 1] - col[i][j] - 1)

    for i in range(w):
        row[i].sort()
        for j in range(len(row[i]) - 1):
            rc[i][row[i][j] + 1:row[i][j + 1]] = [row[i][j + 1] - row[i][j] - 1] * (row[i][j + 1] - row[i][j] - 1)

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

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

tile = [0 for i in range(H)]
cnt = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    tile[i] = readline().decode().strip()

for i in range(H):
    done = [False for _ in range(W)]
    for j in range(W):
        if tile[i][j] == '#':
            continue
        if done[j]:
            continue
        l = 0
        while (j + l < W):
            if tile[i][j + l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j + k] += l
            done[j + k] = True

for j in range(W):
    done = [False for _ in range(H)]
    for i in range(H):
        if tile[i][j] == '#':
            continue
        if done[i]:
            continue
        l = 0
        while (i + l < W):
            if tile[i + l][j] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i + k][j] += l
            done[i + k] = True

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